Top Leaders社区发现算法(top leaders community detection approach in information networks)

一、概念

复杂网络:现实生活中各种系统都可以看做成复杂网络,复杂网络构成包括节点和边,节点是网络中的基本组成单元,节点之间的联系或者关系是网络中的边。例如

电力网络:基站代表节点,基站之间是否互通表示边;

社交网络:用户代表节点,用户的关注关系表示边;

万维网络:网页代表节点,网页的链接关系代表边;

交通运输网络,神经网络,经济贸易网络,科学家合作网络等等

社区发现:社区发现在数据挖掘领域有重要的作用,在一个网络中,如果一个团体有共同的爱好或者特征,并紧密联系在一起,那么我们称网络中这个小集体为一个社区。更为广泛的定义是NewMan(2004)提出,社区内部的节点紧密连接,而社区之间的节点连接稀疏。可用一个公式量化。后文再补。

社区发现分为重叠社区发现和非重叠社区发现。一个节点在现实生活中不可能只属于一个社区,例如社交网络中一个节点有可能同时活跃在多个社交圈中

二、Top Leaders

top leaders认为一个社区是由一个核心领导节点和它的跟随节点形成的,所以我们首先需要找到网络中的核心节点,且这个算法需要事先知道社区的个数k

流程:(1)计算每个节点的全局(整个大网络)中心性DC值,按大小排序,取前k个节点作为核心节点,注意的是前k个节点首先要不相连,若相连他们的共同邻居个数要小于5

DC=deg(n,C)/(N-1)

deg(n,C)表示节点n在社区C中边的条数,N是社区C的size即社区中节点数量

(2)归属度等于节点和其他k个leaders节点重叠邻居节点数量,取节点最大归属度的top leaders进行站队

(3)网络中所有节点都划分完毕后,重新结算每个社区的中节点DC值,取每个社区中最大的DC值作为该社区的topleaders,再次重复计算步骤(1)和步骤(2),直至每个社区的top leaders不再发生变化

参考文献:

Top Leaders Community Detection Approach in Information Networks

上一篇:杭电1171 Big Event in HDU(母函数+多重背包解法)


下一篇:2018年Java生态行业报告