模块度的分辨率极限:最流行的社区检测算法为什么对「小社区」视而不见——不是网络里没有,是尺子看不见
【锚点】这一篇只钉一个判断:模块度 Q 不是「社区有多清晰」的度量,它内置了一个分辨率尺度(量级 √(2m))。小于这个尺度的社区,哪怕由完全连接的团构成、内部边密度 100%,也会被 Q 合并掉。这不是算法 bug,是目标函数的代数。
【显式】Q = (1/2m) Σ_ij [A_ij − k_i k_j/(2m)] δ(c_i,c_j)。前一项是实际边,后一项是「同度序列随机图」下的期望边。Q 衡量的不是边多不多,而是「比随机多多少」——它的参照系是一个全局平均场。
【隐式】关键一步:零模型 k_i k_j/(2m) 对每个节点对给出的期望只依赖两端度数,与它们是否真在同一社区无关。于是当两个候选社区各自很小、而总边数 m 很大时,合并它们带来的 Q 增益会压过分开的增益——网络越大,Q 越倾向于给出更粗的划分。
【细微】Fortunato & Barthélemy (2007, PNAS) 给了最干净的反例:n 个大小为 k 的团,团内全连接、相邻团之间连一条边、整体成环。真实结构一目了然(就是这些团)。但 Q 最大化解会把相邻团两两合并——当团的数量超过约 √m 量级时。分辨率地板约 √(2m) 条边。
【流程节点链路】起点:定义 Q 与全局零模型 → 中间:展开「合并两个社区」时 ΔQ 的符号,发现社区相对 m 足够小时 ΔQ>0 → 终点:存在一个 ~√m 的分辨率地板,低于它的真实社区不可见。
【极难发现】把 Q 读成一次有损压缩就懂了:零模型定义了码本的粒度,而码本尺度随 m 漂移。所以「在 A 网络上调好的分辨率」搬到 B 网络就失效。这和 I² 是 τ²/σ̄² 的比值、⟨k²⟩/⟨k⟩ 是测度而非网络属性,是同一个代数——读数 = 真实结构 ÷ 参照尺度,参照尺度一变,读数就变。
【修法】三条路,但都不是「消除」尺度,而是把尺度摆上台面:(1) 加分辨率参数 γ(Reichardt-Bornholdt 2006;Louvain 的 resolution 参数);(2) 换目标函数——Infomap (Rosvall-Bergstrom 2008) 用随机游走的 MDL 码长,尺度由游走本身决定;(3) 用统计显著性而非最大化,比如 OSLOM。
【结辩】如果每个社区检测目标都内置一个分辨率尺度,那么「这个网络的社区结构是什么」这个问题,是不是本身就不适定(ill-posed)?我们到底是在发现结构,还是在选一个尺度、再把它的名字改成真相?







0 Comments