python - 为什么 NetworkX 中的 Girvan-Newman 算法这么慢

Question

我有大约。我的 graphml 文件中有 4000 个节点和 6000 个边，将其转换为 networkx 的有向图格式没有问题。但是，当我尝试从 networkx 运行 girvan_newman() 时，它似乎卡住了，因为我已经运行了脚本并且它在过去 10 个小时内还没有完成(我尝试了 10 个节点和边，它在 5分钟)。
这是我的片段:

import community as community_louvain
import networkx as nx
from networkx.algorithms.community.centrality import girvan_newman

G = nx.read_graphml('graph.graphml')
partition_girvan_newman = girvan_newman(G)
list(partition_girvan_newman)

我的问题是:

NetworkX 的 girvan_newman() 是否只接受无向图？

如果 networkx 中的 girvan-newman 确实能够处理这么多数据，我应该修改什么以使其更快？

Answer 1

Girvan–Newman algorithm在计算上非常昂贵。正如 docs 中提到的在 NetworkX 中:

The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph. The algorithm removes the “most valuable” edge, traditionally the edge with the highest betweenness centrality, at each step.

通过查看源代码，调用如下:

while g.number_of_edges() > 0:
    yield _without_most_central_edges(g, most_valuable_edge)

依次调用:

while num_new_components <= original_num_components:
    edge = most_valuable_edge(G)
    G.remove_edge(*edge)
    new_components = tuple(nx.connected_components(G))
    num_new_components = len(new_components)
return new_components

所以在每一步，最有值(value)的边被移除，定义为具有最高介数中心性的边，并找到连接的组件。所以粗略地说，复杂度是边数乘以连通分量算法的复杂度和最高中介中心性的数量级。
docs提到一些对返回的生成器进行切片并保留第一个 k 的方法社区元组。如果您想将算法运行到 kth，这里有一个迭代:

from itertools import islice, takewhile

G = nx.fast_gnp_random_graph(10, 0.2)
k = 2
comp = girvan_newman(G)
for communities in islice(comp, k):
    print(tuple(sorted(c) for c in communities)) 
([0, 3, 4, 8], [1, 5], [2], [6, 7, 9])
([0, 3], [1, 5], [2], [4, 8], [6, 7, 9])

或者使用 itertools.takewhile 在社区数量超过某个阈值之前采用元组，这似乎是一种有趣的方法，因为它允许您强加所需的集群数量，例如:

G = nx.fast_gnp_random_graph(10, 0.3)
k = 4
comp = girvan_newman(G)
limited = takewhile(lambda c: len(c) <= k, comp)
for communities in limited:
    print(tuple(sorted(c) for c in communities)) 

([0, 1, 2, 3, 4, 5, 6, 7, 8], [9])
([0, 2, 4, 7, 8], [1, 3, 5, 6], [9])
([0, 2, 4, 7, 8], [1], [3, 5, 6], [9])

回答您的第一个问题，您将在源代码中看到该图已复制到无向图 g = G.copy().to_undirected() ，所以是的，它仅适用于无向图。