使用自定义加权介数中心性的Girvan-Newman算法报错求助

我想将Girvan-Newman算法应用于带自定义中心性指标（基于边权重的介数中心性）的图中，按照NetworkX官方文档编写了最小可复现代码：

import math
import numpy as np
import networkx as nx
import itertools

proximity = np.random.random_integers(1, 100, (10, 10))


def build_graph(proximity):
    G = nx.Graph()
    for i in range(proximity.shape[0]):
        G.add_node(i)
        for j in range(i):
            G.add_edge(i, j, weight=math.exp(-proximity[i, j]))
    return G


def most_central_edge(G, weight="weight"):
    centrality = nx.betweenness_centrality(G, weight=weight)
    # print(centrality)
    return max(centrality, key=centrality.get)


G = build_graph(proximity[:100, :100])
comp = nx.community.girvan_newman(G, most_valuable_edge=most_central_edge)

print(tuple(sorted(c) for c in next(comp)))

运行代码时抛出错误：

TypeError: networkx.classes.graph.Graph.remove_edge() argument after * must be an iterable, not int

解决方法 #

错误根源在于你使用了nx.betweenness_centrality——这个函数计算的是节点的介数中心性，返回的字典键是节点ID（整数类型），所以max返回的是单个整数节点。但Girvan-Newman算法的most_valuable_edge参数要求函数返回一条边的元组（比如(u, v)），因为算法需要移除这条边。

正确的做法是使用nx.edge_betweenness_centrality，它专门计算边的介数中心性，返回的字典键是边的元组，值是对应的介数值。修改后的most_central_edge函数如下：

def most_central_edge(G, weight="weight"):
    # 计算边的加权介数中心性
    centrality = nx.edge_betweenness_centrality(G, weight=weight)
    # 返回介数最高的边（元组形式）
    return max(centrality, key=centrality.get)

替换原函数后，代码即可正常运行，Girvan-Newman算法会基于边的加权介数中心性逐步移除最“重要”的边，从而划分社区。

内容的提问来源于stack exchange，提问作者ginjaemocoes