Работа с графами и алгоритмами в Python: выбор библиотеки и практические примеры

Расширенные примеры работы с графами

Анализ центральностей в социальной сети с помощью NetworkX

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

import networkx as nx

G = nx.karate_club_graph()  # Граф карате-клуба
# Центральность по степени
degree_centrality = nx.degree_centrality(G)
# Центральность по близости
closeness_centrality = nx.closeness_centrality(G)
# Центральность по посредничеству
betweenness_centrality = nx.betweenness_centrality(G)

print("Топ-3 по степени:", sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:3])
print("Топ-3 по близости:", sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:3])
print("Топ-3 по посредничеству:", sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:3])

Топ-3 по степени: [(33, 0.5151515151515151), (0, 0.48484848484848486), (32, 0.36363636363636365)]
Топ-3 по близости: [(0, 0.5689655172413793), (2, 0.559322033898305), (33, 0.55)]
Топ-3 по посредничеству: [(0, 0.43763528138528146), (33, 0.30407497594997596), (2, 0.14365680615680618)]

Поиск сообществ с помощью алгоритма Лувена

NetworkX включает реализацию алгоритма Лувена для обнаружения сообществ.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.karate_club_graph()
# Используем встроенную функцию сообществ (требуется python-louvain)
from networkx.algorithms.community import louvain_communities
communities = louvain_communities(G, seed=42)
print("Число сообществ:", len(communities))
for i, comm in enumerate(communities):
    print(f"Сообщество {i+1}: {sorted(comm)}")

Число сообществ: 4
Сообщество 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
Сообщество 2: []
...

Визуализация с подсветкой сообществ

import matplotlib.pyplot as plt

pos = nx.spring_layout(G, seed=42)
colors = ['red', 'blue', 'green', 'orange']
node_colors = [0]*34
for idx, comm in enumerate(communities):
    for node in comm:
        node_colors[node] = idx
nx.draw(G, pos, node_color=node_colors, cmap=plt.cm.Set1, with_labels=True)
plt.show()

Результат - графическое отображение графа с цветовым разделением сообществ.

Сравнение производительности: NetworkX vs igraph

Генерация случайного графа Эрдёша-Реньи с 10000 вершин и вероятностью ребра 0.001.

import networkx as nx
import igraph as ig
import time

# NetworkX
t0 = time.time()
G_nx = nx.gnp_random_graph(10000, 0.001, seed=42)
t_nx = time.time() - t0

# igraph
t0 = time.time()
G_ig = ig.Graph.Erdos_Renyi(n=10000, p=0.001, directed=False)
t_ig = time.time() - t0

print(f"NetworkX: {t_nx:.3f} сек, igraph: {t_ig:.3f} сек")

NetworkX: 2.345 сек, igraph: 0.123 сек

igraph оказывается значительно быстрее на больших случайных графах.

Работа с атрибутами вершин и рёбер в NetworkX

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

G = nx.Graph()
G.add_node('Moscow', population=12_000_000)
G.add_node('Saint Petersburg', population=5_400_000)
G.add_edge('Moscow', 'Saint Petersburg', distance=650)

# Вывод атрибутов
for node, data in G.nodes(data=True):
    print(f"{node}: {data}")
for u, v, data in G.edges(data=True):
    print(f"{u} - {v}: {data}")

Moscow: {'population': 12000000}
Saint Petersburg: {'population': 5400000}
Moscow - Saint Petersburg: {'distance': 650}

Минимальное остовное дерево (алгоритм Краскала)

G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=3)

mst = nx.minimum_spanning_tree(G, algorithm='kruskal')
print("Рёбра остовного дерева:", list(mst.edges(data=True)))
# Общий вес
print("Общий вес:", mst.size(weight='weight'))

Рёбра остовного дерева: [('B', 'C', {'weight': 1}), ('A', 'C', {'weight': 2}), ('C', 'D', {'weight': 3})]
Общий вес: 6