Multi-Label Propagation Algorithm for Overlapping Community Detection Based on LeaderRank and Node Similarity
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [16]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    The defects of overlapping community detection algorithm COPRA based on multi-label propagation include instability and pre-parameter limits, this study proposed a multi-label propagation algorithm for overlapping community detection based on LeaderRank and the node similarity. The algorithm uses the LeaderRank algorithm to sort the nodes in the network to determine the order of nodes updating. Then, re-design the label update strategy according to the similarity of nodes to improve the stability of the algorithm. The algorithm is applied to the artificial network and the real networks. The experimental results show that the proposed algorithm has high accuracy and stability for detecting overlapping communities.

    Reference
    [1] Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3-5):75-174.[DOI:10.1016/j.physrep.2009.11.002]
    [2] 罗明伟, 姚宏亮, 李俊照, 等. 一种基于节点相异度的社团层次划分算法. 计算机工程, 2014, 40(1):275-279.
    [3] Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.[DOI:10.1073/pnas.122653799]
    [4] Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(6):066133.[DOI:10.1103/PhysRevE.69.066133]
    [5] Blondel VD, Guillaume JL, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks. Journal of Statistical Mechanics:Theory and Experiment, 2008.[DOI:10.1088/1742-5468/2008/10/P10008]
    [6] Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2007, 76(3):036106.[DOI:10.1103/PhysRevE.76.036106]
    [7] Gregory S. Finding overlapping communities in networks by label propagation. New Journal of Physics, 2010, 12(10):103018.[DOI:10.1088/1367-2630/12/10/103018]
    [8] Xie J, Szymanski BK, Liu X. SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. Proceedings of the IEEE 11th International Conference on Data Mining Workshops. Vancouver, Canada. 2011. 344-349.
    [9] Lü LY, Zhang YC, Yeung CH, et al. Leaders in social networks, the Delicious case. PLoS One, 2011, 6(6):e21202.[DOI:10.1371/journal.pone.0021202]
    [10] Wu ZH, Lin YF, Gregory S, et al. Balanced multi-label propagation for overlapping community detection in social networks. Journal of Computer Science and Technology, 2012, 27(3):468-479.[DOI:10.1007/s11390-012-1236-x]
    [11] Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2):026113.[DOI:10.1103/PhysRevE.69.026113]
    [12] Shen HW, Cheng XQ, Guo JF. Quantifying and identifying the overlapping community structure in networks. Journal of Statistical Mechanics:Theory & Experiment, 2009, (7):07042.
    [13] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 2009, 11(3):033015.[DOI:10.1088/1367-2630/11/3/033015]
    [14] Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4):452-473.[DOI:10.1086/jar.33.4.3629752]
    [15] Lusseau D, Schneider K, Boisseau OJ, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003, 54(4):396-405.[DOI:10.1007/s00265-003-0651-y]
    [16] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, Covering Statistical, Nonlinear, Biological, and Soft Matter Physics, 2008, 78(4):046110.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王林,饶仁杰.基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.计算机系统应用,2018,27(6):146-150

Copy
Share
Article Metrics
  • Abstract:1672
  • PDF: 2928
  • HTML: 1916
  • Cited by: 0
History
  • Received:October 09,2017
  • Revised:November 01,2017
  • Online: May 29,2018
Article QR Code
You are the first992292Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063