Привет, Хабр!

Меня зовут Сергей Коньков, я Data Scientist и участник профессионального сообщества NTA.  За последние 10 лет интерес к науке Network Science неимоверно возрос, что повлекло за собой закономерное развитие всевозможных инструментов для исследований в данной области. Одним из таких инструментов является python-библиотека NetworkX, предназначенная для анализа графов или других сетевых структур. Этот пост будет направлен на объяснение и демонстрацию работы основных мер центральности, вычисляемых в графах.

Краткое описание библиотеки NetworkX с некоторыми примерами можно увидеть здесь, также тут размещена документация и множество других публикаций, в разной степени затрагивающих NetworkX.

Для начала введем основные определения, необходимые для последовательного и плавного погружения в данную область по мере изложения материала.

Простым графом

в теории графов называют совокупность двух множеств — множества вершин графа

и множества его ребер E — неупорядоченных пар различных элементов множества .

Построим с помощью библиотеки NetworkX наш первый граф

, состоящий из множества вершин

и множества ребер

import networkx as nx  # импортируем библиотеку
G = nx.Graph()         # создаем пустой граф
G.add_nodes_from([1, 2, 3, 4, 5]) # добавляем вершины в граф
G.add_edges_from([(1, 2), (3, 5), (1, 3), (1, 5), (4, 5), (3, 4), (4, 1)]) # добавляем ребра в граф
nx.draw(G, node_size=500, with_labels=True, node_color='y') # визуализация графа

Такая модель позволяет удобно работать с данными, представляющими из себя объекты, между которыми можно выделить связи. Одна из самых популярных областей, в которой используются графы является Process Mining – область, фокусирующаяся на обнаружении, анализе и оптимизации бизнес-процессов на основе данных из журналов событий.

Конечно же, область применения графов совсем не ограничивается одним только Process Mining; если данные возможно спроецировать на граф, то, сделав это, вы откроете для себя богатый спектр различных методов исследования, а библиотека NetworkX поможет в этом.

В данном посте исследуем датасет, описывающий взаимодействия героев фэнтези-романа “Песнь Льда и Огня” Джорджа Мартина. Два героя связаны ребром, если их имена появляются в тексте на расстоянии не более 15 слов в соответствующей книге. Данные находятся в открытом доступе для 5 книг. Построенная по этим данным сеть является взвешенной, где вес ребра определяется числом взаимодействий (упоминаний в тексте).

import pandas as pd
book5 = pd.read_csv('game_of_thrones_network/asoiaf-book5-edges.csv')
book5.head()

Построим сеть (граф) персонажей по первой книге и посмотрим на структуру произвольного ребра такого графа.

G1=nx.from_pandas_edgelist(book1,'Source', 'Target', edge_attr=True, create_using=nx.Graph())
nx.draw(G1, node_size=25)

print(list(G1.edges(data=True))[16])
('Jaime-Lannister', 'Loras-Tyrell', {'Source': 'Jaime-Lannister', 'Target': 'Loras-Tyrell', 'Type': 'Undirected', 'weight': 3, 'book': 1})

Видно, что в получившемся графе есть связь между Джейме Ланнистером и Лорасом Тиреллом со значением веса 3.

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

Характеристика «центральность» позволяет определить степень важности вершины графа, основываясь на ее расположении. Рассмотрим несколько способов ее вычисления.

1. Центральность по степени (degree centrality)

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

где  — индекс рассматриваемой вершины,  — вес ребра (i, j), — число вершин в графе.

Посмотрим на персонажей первой книги с наибольшим значением центральности по степени.

# топ-10 персонажей по убыванию значения центральности по степени 
characters = sorted(list(nx.degree_centrality(G1).items()), key=lambda i: i[1], reverse=True)
print(*characters[:10], sep='\n')

2. Центральность по собственному вектору (eigenvector centrality)

Недостаток предыдущей меры заключается в том, что она учитывает только ближайших соседей рассматриваемой вершины, эта же мера учитывает “влиятельность” (центральных) ближайших соседей самих по себе. Принцип данной меры можно описать так: “если мои друзья влиятельны, то и я буду более влиятельным”.  Формула для вычисления данной меры:

где  — индекс рассматриваемой вершины,  — вес ребра (i, j),  — некоторый нормировочный коэффициент.

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

где  — вектор, состоящий из значений центральностей каждой вершины,  — матрица весов рассматриваемого графа.

Используя введенные обозначения, исходная формула преобразуется к

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

Посмотрим на топ-10 персонажей по мере центральности по собственному вектору.

# топ-10 персонажей по убыванию значения центральности по собственному вектору 
characters = sorted(list(nx.eigenvector_centrality(G1).items()), key=lambda i: i[1], reverse=True)
print(*characters[:10], sep='\n')

Видно, что Санса Старк поднялась в топ-3 по сравнению с топ-10, соответствующим центральности по степени.

3. Центральность по близости (closeness centrality)

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

 для i-ой вершины графа вычисляется по формуле

где i и j — индексы вершин рассматриваемого графа,

 — кратчайший путь от вершины i к вершине j, т. е. минимальное число ребер, через которые надо пройти, чтобы из вершины i попасть в вершину j.

Данная мера имеет простой физический смысл: чем меньше расстояния от i-ой вершины до остальных j-ых вершин графа (в экстремальном случае

, т. е. вершины i и j связаны ребром), тем меньше будет знаменатель в формуле для

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

Как обычно, вычислим значение данной меры для каждой вершины нашего графа и посмотрим, какие персонажи теперь попадут в топ-10.

# топ-10 персонажей по убыванию значения центральности по близости
characters = sorted(list(nx.closeness_centrality(G1).items()), key=lambda i: i[1], reverse=True)
print(*characters[:10], sep='\n')

4. Центральность по посредничеству (betweenness centrality)

Данная мера очень популярна, и часто в различных литературных источниках по Network Science при упоминании термина "центральность", имеется в виду как раз центральность по посредничеству. Формула для вычисления значения данной меры для i-ой вершины графа уже будет выглядеть сложнее:

где

 — число кратчайших путей от вершины j до вершины k,

 — число кратчайших путей от вершины j до вершины k, которые проходят через вершину i. Суммирование в данной формуле идет по всевозможным парам вершин

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

Посмотрим на топ-10, формируемый посредством вычисления значения данной меры.

# топ-10 персонажей по убыванию значения центральности по посредничеству
characters = sorted(list(nx.betweenness_centrality(G1).items()), key=lambda i: i[1], reverse=True)
print(*characters[:10], sep='\n')

Видим, что впервые в топе, причем достаточно высоко, появилась Дейенерис Таргариен, что говорит о том, что данный персонаж является важным с точки зрения посредника между остальными персонажами книги.

5. Page Rank

Последняя из рассматриваемых мер в данном посте является тоже довольно популярной, но стоит немного особняком относительно предыдущих мер. Интересно, что изначально данная мера вводилась для того, чтобы ранжировать страницы при поисковом запросе в браузере Google Chrome. Раньше даже можно было смотреть, чему равен page rank открытого сайта. Важно отметить, что несмотря на популярность данной меры в области ранжирования веб-страниц, такое название она приобрела не из-за слова "page" ("страница" с англ.), а благодаря ее автору Ларри Пейджу (Larry Page).

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

Воспользуемся готовой реализацией данной меры из библиотеки NetworkX и выведем топ-10 персонажей нашей книги по мере Page Rank.

# топ-10 персонажей по убыванию значения Page Rank
characters = sorted(list(nx.pagerank(G1, alpha=0.85).items()), key=lambda i: i[1], reverse=True)
print(*characters[:10], sep='\n')

Функция nx.pagerank в качестве второго параметра принимает некое

, которое отвечает за вклад каждой из компонент в формуле для вычисления Page Rank, но часто принято для этого параметра указывать именно значение

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