《大规模分布式计算深入解析》12.2 社区检测:Louvain 与标签传播

Louvain 用模块度增益迭代聚合社区、标签传播靠邻居多数投票;连通分量 {0,1,2} 并入 id 0、孤链 {3,4} 收 id 3。

社区检测: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——标签传播收敛口径与社区聚合结果可核算。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图