Используемый набор данных
В качестве источника данных использовались книги Песни льда и пламени, 1 – 5 том.
Перевод публикуется с сокращениями, автор оригинальной статьи Jamie Liu.
- Набор персонажей: каждый персонаж книги – это вершина с единственным свойством – именем.
- Набор отношений: если два персонажа соединяются в книге прямо или косвенно, между ними есть ребро. Ребро имеет одно свойство – вес, представляющий уровень близости отношений.
Набор вершин и ребер образует граф, хранящийся в графической БД – Nebula Graph.
Обнаружение сообщества: алгоритм Гирвана-Ньюмана
В материале использовался встроенный алгоритм обнаружения сообществ Girvan-Newman для разделения сообщества нашей графовой сети.
Ниже приведены пояснения к этому алгоритму.
В сетевом графе тесно связанная часть может рассматриваться как сообщество. Связи между вершинами относительно близки в пределах каждого сообщества, в то время как связи между двумя сообществами являются неполными. Обнаружение сообществ – это процесс поиска в сетевом графе. Гирван-Ньюман – алгоритм обнаружения сообщества, основанный на посредничестве. Его основная идея состоит в постепенном удалении ребер из исходной сети в соответствии с ребром между ними, пока вся сеть не будет разбита на сообщества. По мере удаления ребер группы отделяются друг от друга, и таким образом выявляется лежащая в основе сети структура сообщества – алгоритм Гирвана-Ньюмана является методом расщепления. Его шаги кратко описаны ниже:
- Вычисляется расстояние между всеми существующими в сети ребрами.
- Ребро(а) с наибольшей степенью посредничества удаляются.
- Шаги 2 и 3 повторяются до тех пор, пока ребер совсем не останется.
Пример кода NetworkX для обнаружения сообществ с помощью алгоритма Гирвана-Ньюмана выглядит следующим образом:
Добавим свойство сообщества к каждой вершине графа. Значение свойства – это номер сообщества, в котором находится вершина.
Настройка вершин: алгоритм центральности посредничества
Настроим размер для вершины и размер для имени отмеченного на ней персонажа. Для достижения наших целей будем использовать алгоритм центральности посредничества NetworkX.
Важность каждой вершины в графе можно измерить по ее центральности. Различные определения центральности используются в сетях для описания важности вершин. Центральность посредничества оценивает важность вершины на основе того, сколько кратчайших путей проходит через нее.
Вычислим значение центральности посредничества для каждой вершины.
Добавим новое свойство посредничества для каждой вершины графа.
Размер ребра
Размер ребра определяется его весом. Благодаря предыдущему коду, вершины имеют три свойства: имя, сообщество и степень посредничества, а ребра только одно – вес.
На выходе получаем такую картину:
Хотя NetworkX включает крупный набор функций визуализации, Gephi выполняет работу по визуализации качественнее.
Gephi – инструмент визуализации
Теперь экспортируем полученные данные из NetworkX в файл game.gephi и импортируем его в Gephi.
Отображение в Gephi
Откройте экспортированный файл game.gephi, а затем измените параметры в Gephi, чтобы получить красивую визуализацию.
Установите макет для Force Atlas, измените Repulsion на 500.0 и нажмите Adjust by sizes, чтобы избежать частого перекрытия вершин.
Force Atlas – это алгоритм, позволяющий получить красивую сетевую компоновку, полностью продемонстрировать общую структуру сети и ее автоморфные характеристики. Схема имитирует гравитационные и репульсивные силы и автоматически раскладывается до тех пор, пока силы не будут уравновешены.
Выберите Appearance, Nodes, Color, Partition и сообщество. Сообщество здесь – это номер, добавленный для каждой вершины.
Задайте размер вершин и свойства имен персонажей для вершин.
Выберите Appearance, Nodes, Size, Ranking и Appearance, Nodes, Size, Ranking и посредничество. Посредничество здесь – это свойство, добавленное для каждой вершины.
Размер ребра определяется свойством веса ребра. Выберите Appearance, Edges, Size, Ranking и вес.
Экспортируйте визуализированную картинку.
Мы получили график отношений в «Игре престолов», где каждая вершина – это персонаж.
Код проекта доступен на GitHub-е автора.
Заключение
В статье была рассмотрена тема визуализации данных с помощью NetworkX и Gephi. В следующей публикации вас ожидает не менее увлекательная история о том, как получить доступ к данным в БД Nebula Graph через NetworkX.
Дополнительные материалы:
А как бы вы решали эту задачу?