Хочешь уверенно проходить IT-интервью?
Мы понимаем, как сложно подготовиться: стресс, алгоритмы, вопросы, от которых голова идёт кругом. Но с AI тренажёром всё гораздо проще.
💡 Почему Т1 тренажёр — это мастхэв?
- Получишь настоящую обратную связь: где затык, что подтянуть и как стать лучше
- Научишься не только решать задачи, но и объяснять своё решение так, чтобы интервьюер сказал: "Вау!".
- Освоишь все этапы собеседования, от вопросов по алгоритмам до диалога о твоих целях.
Зачем листать миллион туториалов? Просто зайди в Т1 тренажёр, потренируйся и уверенно удиви интервьюеров. Мы не обещаем лёгкой прогулки, но обещаем, что будешь готов!
Реклама. ООО «Смарт Гико», ИНН 7743264341. Erid 2VtzqwP8vqy
Используемый набор данных
В качестве источника данных использовались книги Песни льда и пламени, 1 – 5 том.
Перевод публикуется с сокращениями, автор оригинальной статьи Jamie Liu.
- Набор персонажей: каждый персонаж книги – это вершина с единственным свойством – именем.
- Набор отношений: если два персонажа соединяются в книге прямо или косвенно, между ними есть ребро. Ребро имеет одно свойство – вес, представляющий уровень близости отношений.
Набор вершин и ребер образует граф, хранящийся в графической БД – Nebula Graph.
Обнаружение сообщества: алгоритм Гирвана-Ньюмана
В материале использовался встроенный алгоритм обнаружения сообществ Girvan-Newman для разделения сообщества нашей графовой сети.
Ниже приведены пояснения к этому алгоритму.
В сетевом графе тесно связанная часть может рассматриваться как сообщество. Связи между вершинами относительно близки в пределах каждого сообщества, в то время как связи между двумя сообществами являются неполными. Обнаружение сообществ – это процесс поиска в сетевом графе. Гирван-Ньюман – алгоритм обнаружения сообщества, основанный на посредничестве. Его основная идея состоит в постепенном удалении ребер из исходной сети в соответствии с ребром между ними, пока вся сеть не будет разбита на сообщества. По мере удаления ребер группы отделяются друг от друга, и таким образом выявляется лежащая в основе сети структура сообщества – алгоритм Гирвана-Ньюмана является методом расщепления. Его шаги кратко описаны ниже:
- Вычисляется расстояние между всеми существующими в сети ребрами.
- Ребро(а) с наибольшей степенью посредничества удаляются.
- Шаги 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.
Дополнительные материалы:
А как бы вы решали эту задачу?