Machine Learning, Графы

Графовые методы анализа в Gephi

Время прочтения: 6 мин.

Новый тренд

Новым трендом в области машинного обучения в 2020 году стало направление, связанное с использованием графов – машинное обучение на графах (Graph Machine Learning или GML) и графовые нейронные сети (graph neural networks или GNNs), что неудивительно, поскольку мы живем в связанном мире, в котором постоянно генерируется огромное количество связанных данных, например, социальные сети, системы финансовых транзакций, биологические сети, транспортные системы и телекоммуникационные сети.

Визуализация графов

Привычный для любого аналитика инструмент MS Excel начиная с 2016 версии предоставляет бесплатный компонент GIGRAPH (его можно добавить через меню Вставка ® Надстройки ® Магазин). Этот инструмент позволяет по трем параметрам (from – to – value, то есть источник – назначение – величина) построить графы – так называемые интерактивные карты взаимосвязей (рис. 1).

Рисунок 1. GIGRAPH – средство MS Excel 2016 и выше (источник: GIGRAPH – Network Visualization (microsoft.com))

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

Инструмент визуализации Gephi

Gephi (https://gephi.org) представляет собой пакет программного обеспечения с открытым исходным кодом для визуализации и анализа связанных данных. Этот пакет написан на Java под платформу NetBeans, поэтому для корректной работы требуется установленная на компьютере пользователя версия Java Runtime Environment (пакет jre) не ниже 7-й версии (рис. 2).

Рисунок 2. Внешний вид графического интерфейса Gephi

Можно сказать, что Gephi в чем-то слегка похож на инструменты, применяемые для процесс-майнига и привычный всем Excel. Поэтому его освоение не должно вызывать слишком большие трудности у аналитика.

В качестве ключевых особенностей данного пакета можно указать следующие:

  •  Пакет поддерживает широкий спектр форматов представления входных данных, например, форматы GraphViz, GDF, GEXF, GML, GraphML, и самое главное, что исходный файл для этой системы аналогичен структуре и расширению CSV-файла, привычного для аналитиков, занимавшихся PM-анализом данных.
  •  Этот пакет имеет открытую лицензию, а это означает, что ее могут свободно использовать не только аналитики, но и программисты (на сайте программного пакета доступны исходные коды), что способствует быстрому развитию пакета и появлению дополнительных модулей для решения самых различных задач (последняя версия Gephi с исходным кодом расположена в репозитории по адресу Release Gephi 0.9.2 · gephi/gephi · GitHub).
  •  Пакет предоставляет широкий набор настроек для регулирования отображения графов. Это позволяет конечному пользователю самостоятельно настраивать отрисовку графов в процессе анализа – основным слоганом Gephi служит фраза «Gephi makes graph handy» ‑ Gephi полностью приручает графы (рис. 3).

 И самое приятное – данный пакт содержит возможность переключения интерфейса на русский язык.

Рисунок 3. Редактирование графа.

Однако важно понимать и отличия. Данный инструмент сложнее, требует освоения, исходные данные несколько детальнее, чем привычный log-файл для процесс-майнинга. Это значит, что проведение графовой аналитики потребует большей предварительной работы над исходными данными, а именно для загрузки в Gephi необходимо подготовить два файла:

  1. Файл вершин (вершины графа являются объектами), в котором обязательно должно быть поле ID. Этого файла достаточно, чтобы построить неориентированный граф.
  2. Файл ребер (ребра являются связями), в котором должны быть поля Источника (Source – исходной, отправной точки) и Назначения (Target – цели, точки, куда направлен поток информации на графе).

Загрузка исходных данных происходит в несколько этапов. На каждом этапе Gephi проверяет корректность данных. Загруженные в Gephi данные можно схожим с MS Excel образом фильтровать, а также можно фильтровать количество узлов и ребер графа с помощью регулярных выражений и логических операторов. Кроме того, для узлов/ребер графа и надписей можно задавать размер и цвет как через указание значения переменной при загрузке данных, так и генерироваться в настройках Gephi. Узлам графа можно даже придать объемный вид, как показано на рисунке 4.

Рисунок 4. Тонкая настройка отображения узлов и ребер графа

Алгоритмы кластеризации и ранжирования

Кластеризация относится к такому процессу классификации узлов или ребер графа, что узлы или ребра с аналогичными атрибутами и свойствами объединяются в один сегмент. Подобное разбиение графа и является кластеризацией (рис. 5).

Рисунок 5. Встроенная операция кластеризации графа

Ранжирование узлов или ребер в графе – еще одна операция, которая широко выполняется во время анализа графов. Ранжирование может производиться либо по узлам, либо по ребрам, в зависимости от того, что хочет найти пользователь при исследовании графа (рис. 6).

Рисунок 6. Встроенная операция ранжирования. Имеется возможность задать наглядность ранжирования с помощью настройки цветовой палитры.

Метрики и фильтры

Gephi предоставляет пользователю в распоряжение несколько готовых способов изучения статистических свойств графов. Эти свойства включают в себя как оценку графа в целом, так и свойства отдельных узлов и ребер (рис. 7).

Рисунок 7. Встроенные метрики для статтистической оценки графа и составляющих его узлов и ребер.

Исследование динамических и многослойных графов

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

В Gephi встроены инструменты анализа графов, моделирующих динамические системы (рис. 8).

Рисунок 8. Инструменты анализа динамических параметров графа

Кроме того, Gephi позволяет визуализировать динамику графа путем добавления проигрывателя, показывающего динамику изменения отношений между объектами графа во времени (рис. 9).

Рисунок 9. Временная полоса для визуализации динамических зависимостей объектов графа

В Gephi встроены инструменты обработки графа с целью ранжировать его на уровни, чтобы промоделировать иерархические зависимости в реальной системе с помощью многоуровневого графа (рис. 10).

Рисунок 10. Выделение уровней в графе

Выводы

Если вы хотите с нуля изучить графовые методы анализа данных и освоить новый инструмент визуализации графов, для вас идеально подойдет Gephi – открытый, постоянно дорабатываемый и обогащаемый новыми инструментами решения современных задач прикладного моделирования и анализа данных с помощью результатов и последних достижений современной науки о сетях (Network Science).

Советуем почитать