Chapter13-Label-Propagation.md

Label Propagation(标签传播)

社区内部连接比较紧凑, 社区与社区之间的连接较为稀疏.

• 模块度(Modularity)能够度量社区划分的质量, 是一个在[-1, 1]区间上的实数, 其通过比较每一个社区内部的连接密度和社区与 社区之间的连接密度, 去度量社区划分的质量.模块度最大的划分就是最优的社区划分.

社区划分算法

• 非重叠社区划分: 一个样本只能属于一个社区, 典型的方法有:
  • 基于模块度优化的社区划分算法
    • 基本思想是将社区划分问题转化为对模块度函数的优化, 模块度是度量社区划分质量的重要标准.由于模块度函数 不能直接求解, 通常采用近似方式求解, 主要有以下方法:
      • 凝聚方法(Agglomerative Method): 通过不断合并不同的社区, 实现对整个网络的社区划分, 典型的方法有 Newman快速算法、CNM算法和MSG-MV算法
      • 分裂方法(Divisive Method): 通过不断删除网络中边来实现对整个网络的社区划分, 典型的方法有Newman 剔除的GN算法
      • 直接近似求解模块度函数(Optimization Method): 通过优化算法直接对模块度函数进行求解, 典型的方法有EO算法.
  • 基于谱分析的社区划分算法
  • 基于信息论的社区划分算法
  • 基于标签传播的社区划分算法

Label Propagation算法原理

Label Propagation算法是一种基于标签传播的局部社区划分算法.大致步骤为:

• 初始阶段, Label Propagation算法对每个节点初始化一个唯一的标签
• 迭代: 每个节点根据与其相连的节点所属的标签改变自己的标签, 更改的原则是选择与其相连的节点中所属标签最多的社区标签为 自己的社区标签(标签传播的意义)
• 最终, 连接紧密的节点将有共同的标签

标签传播

• 同步更新: 在第t次迭代时, 根据第t-1代时的标签对标签进行更新. 但是同步更新存在一个标签震荡的问题(针对一个二分 或者近似二分的网络来说)
• 异步更新: 更新公式为
  其中, 邻居节点 x_i1,..., x_im的社区标签在第t代已经更新过, 则使用其最新的社区标签. 而邻居节点 x_i(m+1),..., x_ik在第t时还没有更新, 则对于这些邻居节点还是使用其在第(t-1)代时的社区标签.

迭代终止条件

通常当网络中的每个节点所属的社区不再改变时, 迭代终止. 但是, 对于某个节点的邻居节点中存在两个或者多个最大的社区标签时, 其所属标签会一直改变, 这时可以更换迭代终止条件为, 所有节点的社区标签最大.

算法过程

• 对网络中的每个节点初始化其所属社区标签, 且每个节点所属的社区是唯一的
• 设置代数t
• 对于每个节点x∈X, 其中X是所有节点的集合, 令
• 判断是否可以迭代结束, 如果否, 则设置t = t + 1, 重新遍历.

杂谈

• 标签传播笔记