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

NetworkX 中的Girvan–Newman algorithm is computationally very expensive. As mentioned in the the docs：

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

所以在每一步，最有价值的边被移除，定义为具有最高介数中心性的边，并找到连接的组件。所以大致复杂度是边数乘以连通分量算法的复杂度和最高介数中心性的量级。

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()，所以是的，它只适用于无向图。

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

Why is the Girvan-Newman algorithm in NetworkX so slow

python

graphml

networkx