为什么 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)

我的问题是：

1. NetworkX 的 girvan_newman() 只接受无向图吗？
2. 如果networkx中的girvan-newman确实能够处理这么多数据，我应该修改什么以使其更快？

Answer 1

Girvan-Newman 算法的计算量非常昂贵。正如 NetworkX 中的 docs 中提到的：

Girvan-Newman 算法通过逐步删除原始图中的边来检测社区。该算法在每一步都会删除“最有价值”的边缘，传统上是具有最高介数中心性的边缘。

通过查看源码，调用如下：

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

因此，在每一步中，都会删除“最有价值的边”，将其定义为具有最高介数中心性的边，并找到连接的组件。因此，粗略地讲，复杂度的数量级是边数乘以连通分量算法的复杂度和最高介数中心性。 文档

提到了一些对返回的生成器进行切片并保留社区的第一个

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()

，所以是的，它仅适用于无向图。