Label Propagation浅析
Label Propagation算法概述
Label Propagation算法是一种基于标签传播的局部社区划分算法。对于网络中的每一个节点，在初始阶段，Label Propagation算法对每一个节点一个唯一的标签，在每一个迭代的过程中，每一个节点根据与其相连的节点所属的标签改变自己的标签，更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这便是标签传播的含义。随着社区标签的不断传播，最终紧密连接的节点将有共同的标签。
Label Propagation算法最大的优点是其算法过程比较简单，想比较于优化模块度的过程，算法速度非常快。Label Propagation算法利用网络的结构指导标签的传播过程，在这个过程中无需优化任何函数。在算法开始前我们不必要知道社区的个数，随着算法的迭代，在最终的过程中，算法将自己决定社区的个数。
Label Propagation算法原理
对于Label Propagation算法，假设对于节点x，其邻居节点为x1,x2,⋯,xk，对于每一个节点，都有其对应的标签，标签代表的是该节点所属的社区。在算法迭代的过程中，节点x根据其邻居节点更新其所属的社区。更新的规则是选择节点x的邻居节点中，所属社区最多的节点对应的社区为其新的社区。
上述便是Label Propagation算法的核心概念。在初始节点，令每一个节点都属于唯一的社区，当社区的标签在节点间传播的过程中，紧密相连的节点迅速地取得一致的标签。具体过程如下图所示：
这样的过程不断地持续下去，直到所有可能聚集到一起的节点都具有了相同的社区标签。在传播过程的最终，具有相同社区标签的节点被划到相同的社区中称为一个个独立的社区。
在标签传播的过程中，节点的标签的更新过程可以分为两种，即：
- 同步更新(synchronous updating)
- 异步更新(asynchronous updating)
同步更新是指对于节点x，在第t代时，根据其所有邻居节点在第t−1代时的社区标签对其标签进行更新。即：
$$Cx(t) = f(Cx1 (t −1), ...,Cxk (t − 1))$$
其中，Cx(t)表示的是节点x在第t代时的社区标签。函数f表示的取的参数节点中所有社区个数最大的社区。同步更新的方法存在一个问题，即对于一个二分或者近似二分的网络来说，这样的结构会导致标签的震荡，如下图所示：
在上图中，两边的标签会在社区标签a和社区标签b不停地震荡。
对于异步更新方式，其更新公式为：
$$Cx(t) = f(Cxi1 (t), ...,Cxim(t),Cxi(m+1) (t−1), ...,Cxik(t−1))$$
其中，邻居节点$$xi1,⋯,xim$$的社区标签在第t代已经更新过，则使用其最新的社区标签。而邻居节点$$xi(m+1),⋯,xik$$在第$$t$$代时还没有更新，则对于这些邻居节点还是用其在第$$t−1$$代时的社区标签。
对于整个迭代过程，理想的情况下是图中节点的社区标签不再改变，此时迭代过程便可以停止。但是这样的定义方式存在一个问题，即对于某个节点，其邻居节点中存在两个或者多个最大的社区标签。对于这样的节点，其所属的社区是随机选取的，这样，按照上述的定义，此过程会一直执行下去。对上述的迭代终止条件重新修改：
迭代的终止条件是：对于每一个节点，在其所有的邻居节点所属的社区中，其所属的社区标签是最大的。
上述的定义可以表示为：如果用$$C1,⋯,Cp$$表示社区标签，$$dCji$$表示是节点i的所有邻居节点中社区标签为$$Cj$$的个数，则算法终止的条件为：对于每一个节点$$i$$，有：
If $$i $$ has label $$Cm$$ then $$diCm ≥ diCj $$ $$∀j$$
这样的停止条件可以使得最终能够获得强壮的社区(Strong Community)，但是社区并不是唯一的。对于Strong Community，其要求对于每一个节点，在其社区内部的邻居节点严格大于社区外部的邻居节点，然而Label Propagation算法能够保证对于每一个节点，在其所属的社区内有足够多的邻居节点。
Label Propagation算法过程
构造图graph。为graph中的每个顶点，分配一个唯一的label。一般可以考虑用node的id当成它的label id;
开始计算每个node新的label。规则是，统计node周围所有邻居的label，出现次数最多的label将被设置成这个node的新label;
如果邻居中出现次数最多的label有多个，那么随机的选择其中的一个label (例如在起始计算中，因为每个node的label都是唯一的，所以每个node周围所有的label出现次数都是1，这时候相当于随机的选择一个邻居的label作为自己的label);
计算所有node之后，判断是否达到了终止条件，如果没有，回到第2步继续计算;
经过几次迭代，到达终止条件，算法完成。现在图中，具有相同label的node属于同一个community。
算法终止条件：它要求所有的node都满足: node的label一定是它的邻居label中出现次数最多的(或最多的之一)，这意味着，每个node的邻居中，和它处于同一个community的数量一定大于等于处于其它community的数量。
GraphX实现
object LabelPropagation {
def run[VD, ED: ClassTag](graph: Graph[VD, ED], maxSteps: Int): Graph[VertexId, ED] = {
require(maxSteps > 0, s"Maximum of steps must be greater than 0, but got ${maxSteps}")
val lpaGraph = graph.mapVertices { case (vid, _) => vid }
//社区发现一般为无向图，在GraphX里面无向图的表示为有向图，即两个顶点之间有两条有向边。
def sendMessage(e: EdgeTriplet[VertexId, ED]): Iterator[(VertexId, Map[VertexId, Long])] = {
Iterator((e.srcId, Map(e.dstAttr -> 1L)), (e.dstId, Map(e.srcAttr -> 1L)))
}
def mergeMessage(count1: Map[VertexId, Long], count2: Map[VertexId, Long]): Map[VertexId, Long] = {
(count1.keySet ++ count2.keySet).map { i =>
val count1Val = count1.getOrElse(i, 0L)
val count2Val = count2.getOrElse(i, 0L)
i -> (count1Val + count2Val)
}.toMap
}
def vertexProgram(vid: VertexId, attr: Long, message: Map[VertexId, Long]): VertexId = {if (message.isEmpty) attr else message.maxBy(_._2)._1}
val initialMessage = Map[VertexId, Long]()
Pregel(lpaGraph, initialMessage, maxIterations = maxSteps)(
vprog = vertexProgram,
sendMsg = sendMessage,
mergeMsg = mergeMessage)
}
}