Найти подграфы внутри подключенного компонента на графике NetworkX

Я построил график NetworkX, содержащий 50000 узлов и около 100 миллионов ребер. У меня есть список всех связанных компонентов этой группы, используя метод nx.connected_components (G). Этот метод приводит к тому, что у меня есть кластеры узлов, так что у каждого узла есть путь к каждому другому узлу в этом кластере. Теперь, что мне нужно, в каждом из этих соединенных компонентов, я хочу найти подграфы / подкластеры так, чтобы каждый из этих подграфов был связан ровно одним ребром. Есть ли метод в NetworkX, который я могу использовать напрямую или любым другим способом, которым я могу это сделать? Извините, я очень новичок в теории графов, поэтому мне нужно немного указаний.

Всего 2 ответа


Если я вас правильно понимаю, то для каждого подграфа вы хотите найти все разрезы графа размера 1, то есть вы хотите найти все ребра, которые, если их убрать, разбивают граф на два подграфа. Эти ребра называются мостами, и для их поиска существуют эффективные алгоритмы. Реализация в networkx доступна через networkx.algorithms.bridges.bridges .


То, что вы хотите, называется минимум три . Используя networkx вы можете сделать это так:

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (4,5), (4,6), (5,6)])
nx.draw(nx.minimum_spanning_tree(G), with_labels=True)
plt.show()

Тем не менее, я немного сомневаюсь, сможет ли networkx работать на стольких краях в соответствии с этим тестом . Я протестировал алгоритм connected components на igraph , он работал и для меня (и, конечно, намного быстрее), так что вы можете также искать решения на основе igraph .

Результат

введите описание изображения здесь


Есть идеи?

10000