⚔ Анализ взаимосвязей в «Игре престолов» с помощью NetworkX, Gephi и Nebula Graph (часть первая)

В этой статье мы получим доступ к графической БД Nebula Graph с помощью NetworkX и визуализируем на Gephi сложные связи персонажей в Игре престолов.

Используемый набор данных

В качестве источника данных использовались книги Песни льда и пламени, 1 – 5 том.

Перевод публикуется с сокращениями, автор оригинальной статьи Jamie Liu.

1. Набор персонажей: каждый персонаж книги – это вершина с единственным свойством – именем.
2. Набор отношений: если два персонажа соединяются в книге прямо или косвенно, между ними есть ребро. Ребро имеет одно свойство – вес, представляющий уровень близости отношений.
   

Набор вершин и ребер образует граф, хранящийся в графической БД – Nebula Graph.

Обнаружение сообщества: алгоритм Гирвана-Ньюмана

В материале использовался встроенный алгоритм обнаружения сообществ Girvan-Newman для разделения сообщества нашей графовой сети.

Ниже приведены пояснения к этому алгоритму.

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

1. Вычисляется расстояние между всеми существующими в сети ребрами.
2. Ребро(а) с наибольшей степенью посредничества удаляются.
   
3. Шаги 2 и 3 повторяются до тех пор, пока ребер совсем не останется.
   

Пример кода NetworkX для обнаружения сообществ с помощью алгоритма Гирвана-Ньюмана выглядит следующим образом:

comp = networkx.algorithms.community.girvan_newman(G)
k = 7
limited = itertools.takewhile(lambda c: len(c) <= k, comp)
communities = list(limited)[-1]

Добавим свойство сообщества к каждой вершине графа. Значение свойства – это номер сообщества, в котором находится вершина.

community_dict = {}
community_num = 0
for community in communities:
    for character in community:
        community_dict[character] = community_num
        community_num += 1
        nx.set_node_attributes(G, community_dict, 'community')

Настройка вершин: алгоритм центральности посредничества

Настроим размер для вершины и размер для имени отмеченного на ней персонажа. Для достижения наших целей будем использовать алгоритм центральности посредничества NetworkX.

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

Вычислим значение центральности посредничества для каждой вершины.

betweenness_dict = nx.betweenness_centrality(G) # Запуск центральности посредничества

Добавим новое свойство посредничества для каждой вершины графа.

x.set_node_attributes(G, betweenness_dict, 'betweenness')

Размер ребра

Размер ребра определяется его весом. Благодаря предыдущему коду, вершины имеют три свойства: имя, сообщество и степень посредничества, а ребра только одно – вес.

import matplotlib.pyplot as plt
color = 0
color_map = ['red', 'blue', 'yellow', 'purple', 'black', 'green', 'pink']
for community in communities:
    nx.draw(G, pos = nx.spring_layout(G, iterations=200), nodelist = community, node_size = 100, node_color = color_map[color])
    color += 1
plt.savefig('./game.png')

На выходе получаем такую картину:

Хотя NetworkX включает крупный набор функций визуализации, Gephi выполняет работу по визуализации качественнее.

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

Теперь экспортируем полученные данные из NetworkX в файл game.gephi и импортируем его в Gephi.

nx.write_gexf(G, 'game.gexf')

Отображение в 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.

Дополнительные материалы:

• 13 лучших инструментов по анализу данных для хакера
• 7 книг для начинающего специалиста по анализу данных
  
• Анализируй данные с помощью одной строки на Python
  
• 5 книг, с которыми анализ данных и Scala до безобразия просты
  
• 10 лучших видео об анализе данных на YouTube
  

Источники

• https://dzone.com/articles/analyzing-relationships-in-game-of-thrones-with-ne