社区检测:Louvain 与标签传播
社区检测把图划分成内部稠密、外部稀疏的组。Louvain 是模块度增益驱动的两阶段迭代,标签传播是最小形式的邻居多数投票,两者都以「聚合」为骨架。
Louvain:两阶段迭代
第一阶段把每个顶点移动到使模块度增益最大的邻居社区,反复直到不再提升;第二阶段把社区聚合成超顶点、重跑第一阶段。每轮计算量 ∝ 边数,分布式下跨分区移动要同步邻居社区计数与总边数。
标签传播:连通分量式投票
标签传播把顶点标记为邻居中出现最多的标签,迭代收敛后同一连通分量共享标签。algo 用例 50:连通分量 {0,1,2} 收敛到最小 id 0,顶点 1 并入分量 0;用例 51:孤链 {3,4} 分量 id 3。它不优化目标函数,只传播多数,是社区检测的简化基准。
社区聚合示意
flowchart TD
A["顶点 0/1/2 标签收敛到 0"]
B["顶点 3/4 标签收敛到 3"]
C["按标签聚合:两个社区"]
D["Louvain 超顶点一轮再移动"]
A --> C
B --> C
C --> D
验证
从卷十一实验包 解包,algo 用例 50 验证连通分量 {0,1,2} 收敛到最小 id 0、顶点 1 并入分量 0;用例 51 验证孤链 {3,4} 分量 id 3——标签传播收敛口径与社区聚合结果可核算。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。