关于Greedy Modularity Algorithm数学原理的计算疑问

你遇到的模块化度增量与全局计算结果不一致的问题，大概率是计算过程中对公式定义、边/度数计数的理解偏差导致的，可从以下几个方向排查：

1. 边数与总度数的定义混淆 #

原论文和NetworkX的模块化度公式中，m指的是无向图的总边数，而总度数是2m（每条无向边贡献2个度）。如果手动计算时误将m当成总度数，或者反过来，会直接导致结果偏差。

比如NetworkX的nx.modularity函数严格遵循公式：

Q = (1/(2*m)) * sum( [A_ij - (k_i*k_j)/(2*m)] * delta(c_i, c_j) for i,j in G.edges() )

其中m = G.number_of_edges()。

2. 增量公式的推导遗漏项 #

原论文中合并两个单节点社区的ΔQ是全局模块化度的净变化，需要覆盖无向图的双向边项：

• 初始状态下，两个节点分属不同社区，交叉边的delta(c_i,c_j)=0，不计入Q；
• 合并后，交叉边的delta=1，同时要计算(A_ij - (k_i*k_j)/(2m))和(A_ji - (k_j*k_i)/(2m))（无向图中两者相等），因此ΔQ的正确推导为：

  ΔQ = (1/(2m)) * 2*(A_uv - (k_u*k_v)/(2m)) = A_uv/m - (k_u*k_v)/(2m²)
  

如果你的增量计算只算了单向边，或者漏掉了1/(2m)的系数，就会和全局计算的Q_new产生差异。

3. 初始模块化度的计算错误 #

初始每个节点单独社区时，若没有自环，每个节点的社区内边数A_ii=0，因此初始Q_old为：

Q_old = - sum(k_i²) / (4m²)

合并后的Q_new必须等于Q_old + ΔQ，你可以用这个等式验证手动计算是否正确。

验证方法 #

用最简单的测试图（比如两个相连节点）做对比：

• 图G：两个节点v1、v2，一条边，m=1，k1=k2=1
• 初始Q_old = -(1²+1²)/(4*1²) = -0.5
• ΔQ = 1/1 - (11)/(21²) = 0.5
• Q_new = -0.5 + 0.5 = 0
• 全局计算Q_new：sum所有项后除以2m，结果也为0，完全一致。

如果你的测试用例不符合这个逻辑，就说明某个步骤的计算存在错误。

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