graf_ds

5 графов, которые должен знать каждый Data Scientist

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

DS
Специализация Data Science
Идет набор в группу 12 500₽ в месяц

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

Графы в Python

Граф состоит из отдельных точек (вершин) и соединяющих их линий (ребер). Вершины могут обозначать любые объекты: пользователей сайта, компьютеры корпоративной сети, населенные пункты на карте. Ребра отображают связи между этими объектами: каких пользователей тот или иной человек занес в «друзья», какие компьютеры объединяются прямым подключением, между какими городами проложены дороги. Как нетрудно догадаться, такая схема позволяет решать множество прикладных задач, и для каждой из них существует множество подходящих графов. 

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

К счастью, Python-программистам не приходится заниматься подготовительной работой. Они могут воспользоваться специальной библиотекой, которая объединяет все необходимые инструменты для создания и анализа графов — NetworkX. Мы также используем этот пакет в следующих примерах.

1. Разбивка вершин на группы

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

Граф с тремя связными компонентами

Технически алгоритм объединяет в себе два метода, с помощью которых можно найти кратчайший путь между вершинами графа: поиск по ширине (Breadth First Search, BFS) и поиск по глубине (Depth First Search, DFS). Самые старательные ученики Data Science могут подробнее прочитать о них здесь, а мы сразу перейдем к коду.

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

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

edgelist = [['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250],["Mumbai", "Delhi",400],["Delhi", "Kolkata",500],["Kolkata", "Bangalore",600],["TX", "NY",1200],["ALB", "NY",800]]

Теперь строим граф с помощью Networkx:

g = nx.Graph()
for edge in edgelist:
    g.add_edge(edge[0],edge[1], weight = edge[2])

Остается применить к полученной структуре алгоритм связных компонент:

or i, x in enumerate(nx.connected_components(g)):
    print("cc"+str(i)+":",x)
------------------------------------------------------------
cc0: {'Frankfurt', 'Kassel', 'Munchen', 'Numberg', 'Erfurt', 'Stuttgart', 'Karlsruhe', 'Wurzburg', 'Mannheim', 'Augsburg'}
cc1: {'Kolkata', 'Bangalore', 'Mumbai', 'Delhi'}
cc2: {'ALB', 'NY', 'TX'}

Готово — мы получили три группы городов, объединенных по континентальному принципу. Эту модель можно применять для самых разных целей. Если бы вместо городов у нас были, например, идентификаторы пользователей, а вместо расстояний — их траты в разных товарных категориях, алгоритм сгруппировал бы их по предпочтениям. 

Курс «Python для анализа данных»
Идет набор в группу 2 700₽ в месяц

2. Поиск кратчайшего пути

Вычисление наименьшего расстояния между двумя точками — одна из старейших задач программирования. Один из наилучших алгоритмов для ее решения еще в конце 50-х разработал нидерландский математик Эдсгер Дейкстра (Edsger Dijkstra), причем человечество может благодарить за это открытие… его невесту.

Как рассказывал сам Дейкстра, однажды его так утомили походы по магазинам вместе с молодой женой, что во время краткой передышки он задумался — как оптимизировать этот процесс? Буквально за 20 минут он разработал метод, который теперь называется алгоритмом Дейкстры.

Метод прост, как все гениальное. Для начала Data Scientist узнает расстояния от начальной точки до каждой точки в пути. Эти значения присваиваются граням графа. Далее алгоритм поочередно проходит по каждой вершине, на каждом шаге определяя наименьшее расстояние до очередной точки. Когда все точки посещены, вы получаете наименьший маршрут.

Алгоритм Дейкстры в действии

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

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

print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight'))
print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))
--------------------------------------------------------
['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']
503

Мы также можем найти кратчайшее расстояние между всеми парами:

for x in nx.all_pairs_dijkstra_path(g,weight='weight'):
    print(x)
--------------------------------------------------------
('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})

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

Анализ Данных: курс-тренажер по SQL
Идет набор в группу 1 600₽ в месяц

3. Поиск оптимального пути

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

В каждом случае помогает алгоритм минимального остовного дерева (Minimum Spanning Tree). Этот термин обозначает подграф, который объединяет ребра с минимально возможной суммой весов. Это не всегда означает, что одна вершина не может иметь больше двух ребер — главное значение имеет итоговая сумма их значений.

Пример минимального остовного дерева в графе

Чтобы построить такую структуру, используйте команду nx.minimum_spanning_tree(g):

nx.draw_networkx(nx.minimum_spanning_tree(g))

4. Рейтинг вершин графа

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

На примере социальных сетей мы и рассмотрим метод. Достаем из хранилища данных список пользователей Facebook:

fb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)

И построим граф:

pos = nx.spring_layout(fb)
import warnings
warnings.filterwarnings('ignore')
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(fb, pos, with_labels = False, node_size = 35)
plt.show()

Теперь посмотрим, у каких пользователей наибольшее влияние. Алгоритм Pagerank умеет сам это делать, опираясь на количество онлайн-друзей:

pageranks = nx.pagerank(fb)
print(pageranks)
------------------------------------------------------
{0: 0.006289602618466542,
 1: 0.00023590202311540972,
 2: 0.00020310565091694562,
 3: 0.00022552359869430617,
 4: 0.00023849264701222462,
........}

Чтобы узнать пользователей с наибольшим весом, мы используем этот код:

import operator
sorted_pagerank = sorted(pageranks.items(), key=operator.itemgetter(1),reverse = True)
print(sorted_pagerank)
------------------------------------------------------
[(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262), (698, 0.0013171153138368807), (483, 0.0012974283300616082), (3830, 0.0011844348977671688), (376, 0.0009014073664792464), (2047, 0.000841029154597401), (56, 0.0008039024292749443), (25, 0.000800412660519768), (828, 0.0007886905420662135), (322, 0.0007867992190291396),......]

А чтобы определить «самого крутого парня», можно построить подграф:

first_degree_connected_nodes = list(fb.neighbors(3437))
second_degree_connected_nodes = []
for x in first_degree_connected_nodes:
    second_degree_connected_nodes+=list(fb.neighbors(x))
second_degree_connected_nodes.remove(3437)
second_degree_connected_nodes = list(set(second_degree_connected_nodes))
subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)
pos = nx.spring_layout(subgraph_3437)
node_color = ['yellow' if v == 3437 else 'red' for v in subgraph_3437]
node_size =  [1000 if v == 3437 else 35 for v in subgraph_3437]
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(subgraph_3437, pos, with_labels = False, node_color=node_color,node_size=node_size )
plt.show()
Желтым отмечен пользователь с наибольшим количеством друзей (цвет можно выбрать любой)

5. Центральность вершин

Понятие центральности обозначает расстояние какой-либо вершины графа до его центра. Измерение центральности — это еще один способ определить влияние разных участников базы данных.

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

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

Чтобы найти такие вершины, используйте следующий код:

pos = nx.spring_layout(subgraph_3437)
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size =  [v * 10000 for v in betweennessCentrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
                 node_size=node_size )
plt.axis('off')

Чем больше диаметр круга, тем больше его степень посредничества. Если устранить эти узлы из системы, большой граф разобьется на несколько малых.

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

Текст: Помогаев Дмитрий

Поделиться:
Опубликовано в рубрике Наука о данных (Data Science)Tagged ,

SkillFactory.Рассылка