基于标签传播概率的重叠社区发现算法

A Label-Propagation-Probability-Based Algorithm for Overlapping Community Detection

发现高质量的社区有助于理解真实的复杂网络,尤其是动态地分析社区重叠结构,对社区管理和演化具有重要意义.文中提出一种基于标签传播概率的LPPB(Label-Propagation-Probability-Based)重叠社区发现算法,该算法首先为每个结点赋予一个独立的标签,然后根据结点的影响力大小将结点进行排序;在标签传播的过程中,综合网络的结构传播特性和结点的属性特征计算标签传播的概率,同时利用结点的历史标签记录修正标签更新结果;最后将传播后具有相同标签的结点划分为同一社区,社区间的重叠结点构成了社区重叠结构.作者在基准数据集和带时间维度的C-DBLP网络上进行实验,结果验证了该算法具有较高的准确性和稳定性,并且通过对重叠结构的动态分析,揭示了社区重叠结点的行为特性和C-DBLP网络处于高"耦合度"的发展趋势.

Finding high quality community helps the users to understand the real complex networks,especially the dynamical analysis of overlapping community structure has the vital significance for community management and evolution.This paper proposes a novel overlapping community detection algorithm called Label-Propagation-Probability-Based（LPPB）algorithm.Each node is assigned a unique label and determined the update order according to the value of node influence.Probability of label propagation depends on the structure propagation characteristics of complex networks and properties of the nodes,meanwhile revising the results from using history information of node label in the process of propagation.Finally nodes with the same tag are divided into one community after propagation,and the overlapping community structure consists of nodes which have more than one label.Experiment results from benchmark datasets and C-DBLP network with time dimension illustrate that LPPB is accurate and stable for overlapping community detection.The dynamic analysis of overlapping structure not only reveals the behavior characteristic of the community overlapping nodes,but also proves that C-DBLP network is undergoing the high ＂coupling＂trend.