5 алгоритмов для построения графов, которые вы должны знать

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

1. Связанные компоненты (Connected components)

Мы все знаем, как работает кластеризация?

Вы можете представить себе Связанные компоненты (Connected Components) в очень простых терминах как своего рода алгоритм жесткой кластеризации, который находит кластеры/острова в связанных данных.

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

Как вы этого добьетесь? Давайте немного подумаем.

Алгоритм связанных компонент, который мы используем для этого, основан на частном случае BFS/DFS. Я не буду подробно рассказывать о том, как он работает, но мы посмотрим, как запустить код с помощью Networkx.

Приложения

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

Мы можем предположить ребра (дороги) между идентификаторами клиентов на основе одинакового использования кредитной карты, или одинакового адреса, или одинакового номера мобильного телефона и т.д. Как только мы получим эти связи, мы можем запустить алгоритм связанных компонентов для создания отдельных кластеров, которым мы можем присвоить идентификатор семьи.

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

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

Возможности ограничены только вашим собственным воображением.

Код

Мы будем использовать модуль Networkx в Python для создания и анализа наших графиков.

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

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

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])

Теперь мы хотим найти на этом графике отдельные континенты и их города.

Теперь мы можем сделать это с помощью алгоритма связанных компонент:

for 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'}

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

. . .

2. Кратчайший путь (Shortest Path)

Продолжая рассмотренный выше пример, нам дан граф с городами Германии и соответствующим расстоянием между ними.

Вы хотите выяснить, как добраться из Франкфурта (начальный узел) в Мюнхен по кратчайшему расстоянию.

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

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

- Эдсгер Дейкстра, интервью с Филипом Л. Франа, Communications of the ACM, 2001[3].

Приложения

Вариации алгоритма Дейкстры широко используются в Google Maps для поиска кратчайших маршрутов.Вы находитесь в магазине Walmart. У вас есть различные проходы и расстояние между всеми проходами. Вы хотите предоставить покупателю кратчайший путь от прохода A до прохода D.

Код

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']})

....

…

3. Минимальное покрывающее дерево (Minimum Spanning Tree)

Теперь у нас другая проблема. Мы работаем на компанию по прокладке водопровода или интернет-волокна. Нам нужно соединить все города на имеющемся у нас графике, используя минимальное количество проводов/труб. Как нам это сделать?

Приложения

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

Код

# nx.minimum_spanning_tree(g) returns a instance of type graph
nx.draw_networkx(nx.minimum_spanning_tree(g))

Как вы можете видеть выше, это провод, который мы должны проложить.

. . .

4. PageRank

Это алгоритм сортировки страниц, который долгое время работал в Google. Он присваивает страницы баллы, основанные на количестве и качестве входящих и исходящих ссылок.

Применение

Pagerank можно использовать везде, где мы хотим оценить важность узла в какой-либо сети.

Он используется для поиска наиболее влиятельных статей с помощью цитирования.Используется Google для ранжирования страницОн может быть использован для ранжирования твитов - пользователь и твиты как узлы. Создает связь между пользователями, если пользователь А следует за пользователем Б, и связь между пользователем и твитами, если пользователь твитнул/ретвитнул твит.Рекомендательные механизмы

Код

Для этого упражнения мы будем использовать данные Facebook. У нас есть файл ребер/связей между пользователями Facebook. Сначала мы создадим граф FB, используя:

# reading the datasetfb = 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 даст более высокий балл пользователю, у которого много друзей, у которых, в свою очередь, много друзей в Facebook.

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

Мы можем получить отсортированный PageRank или самых влиятельных пользователей с помощью:

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. Показатель центральности (Centrality Measures)

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

Центральность между друзьями (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')

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

Заключение

В этой статье я рассказал о некоторых наиболее важных алгоритмах графов, которые изменили наш образ жизни.

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

И даже понять немного больше о мире.

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

. . .

Источник: m.vk.com

Комментарии: