Анализ процессов, Графы

Немного о графах

Время прочтения: 3 мин.

Networkx — это свободно-распространяемая библиотека для языка Python, которая была создана для изучения графиков и сетей.

Устанавливается она крайне просто, при помощи команды:

pip install networkx

а для использования необходимо добавить строку:

import networkx as nx

Теперь, когда мы готовы работать, давайте попробуем применить два простых, но полезных инструмента графовых алгоритмов.

Первый из них: поиск минимального пути между узлами. Этот алгоритм будет нам крайне полезен для того, чтобы понять, сколько промежуточных узлов нам надо преодолеть для прохождения пути между заданными узлами. Реальным примером является поиск количества посредников в цепочке, которая «обеляла» денежные средства.

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

Для работы, кроме самой библиотеки, необходимо будет указать узлы или связи между узлами.

Узлами у нас будут являться имена людей, а связь между узлами – это список кортежей. Загрузка будет реализована следующим образом:

import pandas as pd
df = pd.read_excel('Список.xlsx')
elist = []
for index, row in df.iterrows():
    elist.append((row['Имя1'], row['Имя2']))

Для построения графа связей между людьми мы будем использовать библиотеку networkx. 

import networkx as nx
G = nx.Graph()
G.add_edges_from(elist)

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

Теперь при помощи команды:

nx.shortest_path(G)

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

Читается результат следующим образом: от узла «Алина» до узла «Алина» путь проходит через узел «Алина». От узла «Алина» до узла «Наталия» путь «Алина» + «Наталья». Таким простым образом мы можем найти минимальные пути. Данная функция реализовывает алгоритм Дейкстры, который уже является классическим для поиска кратчайших путей.

Теперь давайте рассмотрим еще один алгоритм – алгоритм обнаружения групп. Иногда он также встречается под названием алгоритм обнаружения сообществ. Он позволяет разбить наши узлы на заданное количество групп-сообществ.

Для этого нам необходимо импортировать еще два модуля:

from networkx.algorithms import community
import itertools

Первый модуль отвечает за загрузку метода community, а второй отвечает за быстрый перебор наших узлов.

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

k = 1
comp = community.girvan_newman(G)

Для примера поделим наши узлы по наиболее явному признаку – связи между узлами и общими узлами. Для этого мы укажем k =1 – один проход для поиска групп. При этом чем больше будет значение k, тем на большее количество групп будет проходить деление.  А дальше простым циклом мы выведем все наши группы.

for communities in itertools.islice(comp, k):
    print(tuple(sorted(c) for c in communities))

Результат работы будет следующим:

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

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

Советуем почитать