刘功申 孟 魁 郭弘毅 苏 波 李建华



基于贡献函数的重叠社区划分算法

刘功申 孟 魁*郭弘毅 苏 波 李建华

(上海交通大学电子信息与电气工程学院 上海 200240)

现实世界中的网络结构呈现出重叠社区的特征。在研究经典的标签算法的基础上，该文提出基于贡献函数的重叠社区发现算法。算法将每个节点用三元组(阈值、标签、从属系数)集合来表示。节点的阈值是每次迭代过程中标签淘汰的依据，该值由多元线性方程自动计算而来。从属系数用于衡量当前节点与标签所标识社区的相关度，从属系数的值越大说明该节点与标签所标识社区的关联性越强。在每一次迭代的过程中，算法依据贡献函数计算每个节点的从属系数，并生成新的三元组集合。然后依据标签决策规则淘汰标签，进行从属系数规范化。通过对真实的复杂网络和LFR(Lancichinetti Fortunato Radicchi)自动生成的网络进行测试可知，该算法的社区划分准确率高，而且划分结果稳定。

复杂网络；社区发现；重叠社区

1 引言

经典的社区发现算法假设某个节点仅仅属于一个特定社区，这种假设显然和现实不完全相符。在现实世界的复杂网络系统中，存在一些节点同时属于不同的社区，这便是所谓的重叠社区结构[1]。针对重叠社区的挖掘问题，Palla等人[2]提出了针对重叠社区的派系过滤(Clique Percolation Method, CPM)算法，该算法将社区视作由一些互相连通的完全子图构成的集合。将节点数目为的完全子图定义为-clique，当两个-clique之间拥有个公共节点时，则认为这两个-clique是相邻的。……