Что такое графы, и как их применять в аналитике

Графы — это способ аналитики данных, который был известен ещё с древних времён. С увеличением вычислительных мощностей процессоров и развитием компьютерных алгоритмов удалось приспособить их для решения современных сложных задач. Рассказываем о графовой аналитике, практических решениях и первых шагах для новичков.

Владимир Ловцов

Эксперт-аналитик Группы «Иннотех»

Графы — одна из самых древних структур представления информации. Как только люди научились рисовать кружочки и проводить между ними линии, стало понятно, что таким образом можно представлять связи объектов друг с другом.

Графы позволяют находить взаимосвязи и предсказывать вероятные связи в сложных взаимосвязанных структурах. Например, в социальных сетях мы можем предположить, что Иван Иванович знаком с Иваном Васильевичем, потому что у них один и тот же круг общения. Графы помогают строить маршруты в навигаторах, а также выявлять фрод.

Что такое графы?

Если углубиться в научные изыскания, то графы — это математические структуры, используемые для изучения парных отношений между объектами. Но гораздо проще представить граф на наглядном примере. Представим, что вам нужно разнести документы по девяти разным кабинетам. Каждый кабинет — это вершина графа, а расстояние между ними — рёбра графа определённой длины (величину длины можно записать цифрой для удобства).

Построив такую схему, можно найти оптимальный маршрут между кабинетами. А ещё у графа может быть направление, например, когда у нас есть строго определённый порядок посещения кабинетов. Такое направление ещё называется дугой.

Рёбра графа могут иметь вес, который характеризует силу связей между вершинами. Например, сколько раз пришлось возвращаться в определённый кабинет, чтобы переделать неправильно заполненные документы. В итоге, можно предсказать, по каким оптимальным маршрутам пройти по кабинетам и сколько времени понадобится для того, чтобы разнести документы.

Несмотря на кажущуюся простоту, граф — крутая, но очень сложная структура. Он хранится либо в стандартной двумерном массиве, но так его сложно воспроизвести, либо в специфическом виде в формате json — для таких форматов нужна соответствующая база данных и графовый движок.

Что такое графовая аналитика?

Графовая аналитика — это набор методов, направленных на изучение сложных зависимостей между сущностями, которые сами по себе связаны друг с другом и представлены в виде графов.

Если по-простому, то это связь между двумя сущностями. То есть, даже если ты позвонил себе, то образовался граф. По сути, это дуга, которая ведёт сама к себе.

Под сущностями в графовой аналитике понимаются субъекты или объекты. Например, субъектами могут быть люди — когда человек звонит другому человеку. А можем рассматривать объекты в виде телефонов, на которые поступает звонок.

Где используется графовая аналитика?

Графовая аналитика используется во многих повседневных вещах. Например, в навигаторах для определения кратчайшего маршрута. Также графы помогают транспортным компаниям определить оптимальное расположение распределительных центров и складов, да и вообще, как приехать курьеру к вам также решает графовый алгоритм.

В маркетинге графовая аналитика позволяет выявить инфлюенсеров. Кстати, рекомендательные алгоритмы часто тоже работают на графах. Поэтому очередной предлагаемый для просмотра сериал на Netflix или рекламная запись во «ВКонтакте» появляются благодаря им.

В телекоммуникациях операторы сотовой связи используют диаграммы Вороного, основанные на графах, для определения покрытия вышек. Так что если где-то у вас плохой сигнал, то винить в этом можно незадачливого графового аналитика.

Некоторые медицинские и фармакологические компании могут использовать графы для описания химической структуры. Логика тут простая — между атомами всегда есть связь, которая формирует структуру вещества. И вот эти структуры или даже химические связи можно изобразить с помощью графов. По заданным критериям  производится поиск химического состава, например, нового лекарства или обезболивающего, которое может быстро действовать без вреда для организма.

Для банковского сектора графовая аналитика позволяет анализировать клиентов. Например, проверять, соответствуют ли они критериям для выдачи кредита. Графы в том числе используются для антифрода, чтобы определить мошенников и аффилированных лиц.

Компания «Дататех», входящая в группу «Иннотех», разработала платформу графовой аналитики MIRION, позволяющую работать со сложной структурированной и неструктурированной информацией, которая потенциально может иметь какие-то связи. Используемые данные можно визуализировать и решать различные задачи, где можно использовать граф. Например, организовать тот же антифрод, аналитику клиентов, поиск родственников, группы связанных лиц и многое другое. Платформа гибкая и универсальная для работы с большими графами, и да там уже гиперграф.

Насколько перспективна технология?

За графовым анализом будущее. Пользователи постоянно генерируют гигантские объёмы данных. Каждую минуту по всему миру в среднем отправляются 231,4 миллиона писем электронной почты и 16 млн текстовых сообщений. За это же время пользователи Twitter отправляются 347 200 публикаций, а в Snapchat появляются и исчезают 2,43 млн снимков, на YouTube загружают 500 часов видео, в Tinder оценивают 1,1 млн потенциальных партнёров, в Google отправляются 5,9 млн поисковых запросов, а пользователи Zoom проводят 104,6 тысяч часов видеосвязи.

Так как объём данных растёт, то мы получаем множество взаимосвязей. Сервисы видят транзакции пользователя, что происходит у него  в телефоне, а это позволяет строить графы, которые дают возможность получить множество сведений о конкретном человеке, здравствуй профиль 365 градусов.

Как правило, у банков лежит множество данных в Data Lake — у кого-то это озёра данных, а у некоторых болота данных. А если к ним добавить информацию от телеком-операторов, ФНС, Мосбиржи и так далее, получается прозрачная картина интересов и потребностей конкретного пользователя.

И на этом современная графовая аналитика не останавливается. С помощью ML удаётся уже предсказывать с заданным уровнем точности поведение человека. Например, что с вероятностью 80% Иван Иванович пойдёт в конкретный магазин и с вероятностью 30% купит определённые продукты. Получается, мы можем заранее предложить Иван Ивановичу то, что нам выгодно в данный момент (берите на вооружение).

Графы также активно применяются для ML. Но этот пункт довольно обширный и достоин отдельной серии статей, которая обязательно появится на площадке.

Какие инструменты используются для графовой аналитики?

Если говорить о языках программирования, то для многих популярных из них уже созданы необходимые библиотеки для работы с графами. Например, для Java — это JGraph и JGraphT, Python — NetworkX и Plolty, С++ — Boost Graph Library.

В распространённом фреймворке Apache Spark для распределённой обработки неструктурированных и слабоструктурированных данных также имеется собственный компонент для работы с графами — GraphX.

Самой распространённой графовой СУБД считается Neo4j. Также используются для работы базы данных MongoDB, Amazon Neptune, ArangoDB, JanusGraph и другие проекты.

Что необходимо для изучения графовой аналитики?

Новички могут изучить базовую теорию графов. Например, прочитать книгу «Введение в теорию графов» авторства Робина Дж. Уилсона.

Так как мы в «Иннотех»  используем специфическую базу данных, то проходили обучение по алгоритмам графов на нашей графовой базе данных (ГБД), то есть, что графовые данные из себя представляют, как должны храниться, как обходить граф и так далее. Но это был наш внутренний курс. Всем остальным можно присмотреться к курсам от МФТИ и курсам по конкретным ГБД от их разработчиков.

Математические методы нужны больше специалистам более высокого уровня, например, архитекторам ГБД. Для новичков это сложная и, на самом деле, не нужная для начала проекта тема — хватит и парочки статей из «Википедии».

Аналитикам, которые хотят начать использовать графы, стоит задаться вопросом, а зачем это им нужно. Надо понимать, что на рынке больше востребованы аналитики широкого профиля: системные, бизнес- и фулстек-аналитики, а также дата-аналитики и Data Scientist. Графовая аналитика больше заточена под конкретные проекты и специалист по ней порой весьма узкоспециализирован. Однако обладает отличными знаниями и дорогой экспертизой, потому что может с нуля построить правильные процессы по применению графовой парадигмы в компании и на проекте.