Community Detection – Label Propagation算法

在我看来,Label Propagation算法(LPA)最吸引人的地方,在于它的简单–核心思路的简洁,并且很容易实现。一个简单的算法意味着易于理解,并且容易在它之上做很多有针对性的改良。
LPA的另一个极大的优点在于scalability。LPA非常适合用来处理large graph,因为算法的实质是 vertex-centric model,所以其实是可以在Map-Reduce上实现它。
此外,和很多基于clustering算法不同的是,LPA不需要预先给定community的数量。基于clustering的算法一般都需要预先给定些seeds,而LPA不需要任何的先验知识。这点对于处理large graph也是非常重要的,你很难知道一个千万/上亿节点的graph能够被划分成多少个community。
我曾经看过一个资料,似乎新浪微博是用LPA给用户打标签。另外,刚出炉的WSDW2013的best student paper也是一个LPA的改进算法。

原始的LPA算法计算过程大致描述如下:
1. 初始整个graph。对于graph中的每个node,分配一个唯一的label。一般可以考虑用node的id当成它的label id;

2. 开始计算每个node新的label。计算的规则是,统计node周围所有邻居的label,出现次数最多的label将被设置成这个node的新label;

3. 如果邻居中出现次数最多的label有多个,那么随机的选择其中的一个label (例如在起始计算中,因为每个node的label都是唯一的,所以每个node周围所有的label出现次数都是1,这时候相当于随机的选择一个邻居的label作为自己的label);

4. 计算所有node之后,判断是否达到了终止条件,如果没有,回到第2步继续计算;

5. 经过几次迭代,到达终止条件,算法完成。现在图中,具有相同label的node属于同一个community。

算法的终止条件如下:

image

它要求所有的node都满足: node的label一定是它的邻居label中出现次数最多的(或最多的之一),这意味着,每个node的邻居中,和它处于同一个community的数量一定大于等于处于其它community的数量。

Our stop criterion characterizing the obtained communities is similar (but not identical) to the definition of strong communities proposed by Radicchi et al [15]. While strong communities require each node to have strictly more neighbors within its community than outside, the communities obtained by the label propagation process require each node to have at least as many neighbors within its community as it has with each of the other communities.

算法的这个终止条件,表明LPA最终切割成的community是有一定的质量保证的。

在每次迭代中,计算node的label有两种方式:synchronousasynchronous

所谓的synchronous,就是在当前迭代中,是基于邻居的上一次迭代中的label来更新node的新label:

In synchronous updating, node x at the t-th iteration updates its label based on the labels of its neighbors at iteration t-1.

而在asynchronous中,node的label并不区分当前迭代和上一次迭代,永远都只使用node最新的label。 原始paper中是推荐使用asynchronous方式的,主要原因在于synchronous可能出现label的交替振荡而无法达到稳定态,这种情况很容易在星状图中出现:

The problem however is that subgraphs in the network that are bi-partite or nearly bi-partite in structure lead to oscillations of labels. This is especially true in cases where communities take the form of a star graph.

label振荡的示意图:

image

我观察到的,asynchronous其实还有另外一个好处,就是它的迭代速度要比synchronous快很多。还有一点需要注意的是,使用asynchronous方式,在一次迭代中,node的更新顺序必须是随机的“The order in which all the n nodes in the network are updated at each iteration is chosen randomly”

实践中,LPA的迭代次数少的让人惊讶(asynchronous方式)。作者在paper中提到,经过5次迭代后,95%的节点就已经被正确的切分好了。在我的实验中,一个百万级的网络,3次迭代就完成了92%的节点的切分,4次迭代后完成了97.7%的节点。以至于我以为是实现的代码有bug。

另外作者还提到,如果有先验知识的话,我们可以给graph中的node标上先验的label,然后其他的节点不标label,这样也可以最后达到community detection的效果:

If we know the set of nodes in the network that are likely to act as centers of attraction for their respective communities, then it would be su?cient to initialize such nodes with unique labels, leaving the remaining nodes unlabeled. In this case when we apply the proposed algorithm the unlabeled nodes will have a tendency to acquire labels from their closest attractor and join that community.

新浪微博似乎就是走的这个套路。首先会有一些用户打上了标签,然后让这些标签在整个网络中扩散出去,最终的效果就是大部分人都被打上标签。

最后一个话题,LPA的效果如何。之前的blog已经展示了一些small graph的效果图。看着还是不错的。但是,在large graph中,效果还是有些问题。关于这点,需要再写篇blog好好说道。

— Continue. —

Advertisements
相册 | 此条目发表在Community Detection, Paper笔记, Social Network分类目录,贴了, 标签。将固定链接加入收藏夹。

2 Responses to Community Detection – Label Propagation算法

  1. Jin说道:

    请问label是怎么定义的?

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s