NetworkX Girvan-Newman聚类异常：g4未与高权重g3归为一类

Girvan-Newman算法是通过迭代移除边介数最高的边划分社区的，它默认不直接将你的“连接强度权重”纳入核心计算——或者说，算法默认把weight参数当作路径的长度（成本），而非节点间的连接紧密程度。你的权重代表“值越大连接越强”，这和算法默认的权重含义完全相反，导致权重高的边可能被错误优先移除。

以你的数据为例：g4与g3的权重是2，g4与g1的权重是1，但默认情况下算法计算最短路径时不区分权重，所有边的路径长度都视为1。此时g3仅与g4相连，所有从g3到g1、g2的路径都必须经过g3-g4这条边，导致它的边介数远高于其他边，被优先移除，最终g3被单独划分出来。

优化方案 #

方案1：修正Girvan-Newman的权重处理逻辑 #

将你的“连接强度权重”转换为路径成本（比如取倒数），让权重越高的边路径成本越低。这样算法计算最短路径时会优先选择高权重边，降低它们的介数，避免被优先移除。

修正后的代码：

import pandas as pd
import networkx as nx
from networkx.algorithms.community import girvan_newman

# 修正：将group列设为索引，保证节点名是g1-g4而非数字
matrix = pd.DataFrame({
    'group': ['g1', 'g2', 'g3', 'g4'],
    'g1': [2, 1, 0, 1],
    'g2': [1, 2, 0, 0],
    'g3': [0, 0, 2, 2],
    'g4': [1, 0, 2, 3]
}).set_index('group')

G = nx.Graph()
for group1 in matrix.index:
    for group2 in matrix.index:
        if group1 == group2:
            continue
        weight = matrix.loc[group1, group2]
        if weight > 0:
            # 连接强度权重转路径成本：权重越高，成本越低
            G.add_edge(group1, group2, weight=1/weight)

# 自定义介数计算函数，使用路径成本权重
def weighted_edge_betweenness(G):
    return nx.edge_betweenness_centrality(G, weight='weight')

# 传入自定义介数函数运行Girvan-Newman
communities = girvan_newman(G, edge_betweenness_centrality=weighted_edge_betweenness)
first_communities = tuple(sorted(c) for c in next(communities))
print("修正后的Girvan-Newman结果:", first_communities)

运行后会得到符合预期的聚类：(['g1', 'g2'], ['g3', 'g4'])

方案2：换用原生支持权重的Louvain算法 #

Louvain算法基于模块度优化，原生支持边权重，能直接利用你的“连接强度”信息，是更适合这类场景的选择。

代码示例：

import pandas as pd
import networkx as nx
from networkx.algorithms.community import louvain_communities

matrix = pd.DataFrame({
    'group': ['g1', 'g2', 'g3', 'g4'],
    'g1': [2, 1, 0, 1],
    'g2': [1, 2, 0, 0],
    'g3': [0, 0, 2, 2],
    'g4': [1, 0, 2, 3]
}).set_index('group')

G = nx.Graph()
for group1 in matrix.index:
    for group2 in matrix.index:
        if group1 == group2:
            continue
        weight = matrix.loc[group1, group2]
        if weight > 0:
            G.add_edge(group1, group2, weight=weight)

# Louvain直接使用权重计算模块度
communities = louvain_communities(G, weight='weight', resolution=1)
sorted_communities = tuple(sorted(c) for c in communities)
print("Louvain聚类结果:", sorted_communities)

该算法会优先将高权重连接的节点归为一类，输出结果同样为(['g1', 'g2'], ['g3', 'g4'])。

方案3：调整Girvan-Newman的迭代次数（仅作补充） #

如果坚持使用Girvan-Newman，可以多迭代几次查看后续划分，但此方法无法直接得到你想要的两类划分，仅作参考：

communities = girvan_newman(G)
# 获取第2次迭代的结果
for i in range(2):
    current_communities = tuple(sorted(c) for c in next(communities))
print("第2次迭代结果:", current_communities)

输出为(['g1', 'g2'], ['g3'], ['g4'])，显然不符合需求，因此不推荐。

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