WANG Shi-yi, DONG Yi-hong, LI Zhi-chao, et al. The Identification of Overlapping Communities in Large-Scale Complex Networks[J]. Acta Electronica Sinica, 2015, 43(8): 1575-1582.
DOI:
WANG Shi-yi, DONG Yi-hong, LI Zhi-chao, et al. The Identification of Overlapping Communities in Large-Scale Complex Networks[J]. Acta Electronica Sinica, 2015, 43(8): 1575-1582. DOI: 10.3969/j.issn.0372-2112.2015.08.016.
The Identification of Overlapping Communities in Large-Scale Complex Networks
经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据.本文在GraphLab并行计算模型上提出了基于重要节点扩展的重叠社区识别算法DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab).算法选取网络中PageRank值大的节点作为重要节点
many classic detection algorithms of overlapping communities cannot work efficiently in large-scale complex network.Detecting the overlapping community algorithm based on vital node expanding in parallel framework GraphLab (DOCVN) is introduced to identify the overlapping communities.In this algorithm
nodes with high PageRank value are regarded as vital nodes
and then the affiliation degree of other nodes to these vital nodes are computed.After that
kernel communities and expanding communities are identified respectively.Finally
the kernel communities and expanding communities are combined into some overlapping communities by judging whether they connect tightly.And the importance weight of each node in its community is also computed.Experimental results show that the algorithm is more effective than the existing parallel algorithms like PD (Propinquity Dynamics) to identify large-scale overlapping communities.