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

Question

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

Answer 1

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

Answer 2

То, что вы хотите, называется минимальный охват трех . Используя 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.

Результат