Large-scale Graph的closeness centrality计算

之前的blog提到过closeness centrality(后面简称CC)的定义。要计算一个节点的CC,需要计算这个节点到所有节点的距离,然后求平均。

对于一个百万级节点甚至更大的图来说,计算所有节点的CC几乎是件不可能的事情。

Paper:”Centralities in Large Networks: Algorithms and Observations“给出了一个近似的算法。大概思想是这样的:
Let N(r, v) be the number of neighbors of node v within r steps, and Nv(r) be the number of nodes whose shortest distances to v is r. Notice that Nv(r)= N(r, v) – N(r-1, v). Based on these quantities, standard closeness can be defined by

image

我再简单举例描述一下思路:
你可以假设每个节点上都有一个hashset,比如节点A,初始状态下,节点A的hashset包含了自己的id(a);
第一步,A将邻接节点的hashset拷贝过来,放入自己的hashset中。这时候A的hashset除了包括id a,还包括了距离为1的节点id。所以:
到A距离为1的节点数量=sizeof(hashset) – 1;
第一步之后图中所有节点的hashset都包含了到自身距离为1的节点的id;
第二步,A再将邻接节点的hashset拷贝过来。这时候,相当于A的hashset中不仅包含了距离为1的节点id,还包含了到它的邻接节点距离为1的id。而到邻接节点距离为1相当于到节点A的距离为2。所以:
到A距离为2的节点数量=sizeof(hashset) – sizeof(hashset in step 1);
如此循环,一直到hashset包含了图中所有的节点。
然后就可以计算出节点A的CC。
上述的步骤可以同时对所有的节点并行操作,所以可以同时计算出所有节点的CC。

当然,上述算法还存在一个问题,即每个节点都需要有一个hashset,总的空间就是sizeof(hashset) * sizeofNode。而到最后,sizeof(hashset) = sizeofNode。所以空间复杂度是O(n^2)。当图很大的时候,空间复杂度呈指数级增长。
同时需要注意到,在上面的算法中,我们并不需要遍历hashset中的每个元素,或者说我们不需要知道hashset中具体存了哪些id,我们感兴趣的,是每一步迭代完成后,hashset的size的变化。

为了解决这个问题,作者提出了用Flajolet-Martin algorithm算法近似计算hashset的size。FM算法之前的blog写过,这里不详细介绍了。当采用FM算法后,每个节点所对应的就不再是一个hashset,而是几十个64bit长度的二进制串。空间复杂度变成了O(n)。当然,代价就是得到的结果是一个近似结果。但是如果你时间比较充足,多算几遍,结果的精度还是很高的。

算法的伪代码:

image

整个算法我用Hadoop实现了一遍,然后在一个将近千万节点的网络中测试了一下。效果还是很好的。因为算CC一般是为了找到网络的中心节点,所以其实并不需要知道每个节点太精确的数值。只要计算结果中排名前列的节点确实是网络的中心节点,就算达到目的了。

PS: 这篇paper除了提出CC的一个近似算法外,还提出了一个Betweenness Closeness的大规模近似算法,但我不太认为这个算法。因为这个算法基本上是改变了Betweenness Closeness本来的定义。

— END. —

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

发表评论

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