SUN Liping, LIU Jun, ZHENG Xiaoyao, LUO Yonglong. An Efficient and Adaptive Method for Overlapping Community Detection in Real-World Networks[J]. Chinese Journal of Electronics, 2018, 27(6): 1126-1132. doi: 10.1049/cje.2017.09.012
Citation: SUN Liping, LIU Jun, ZHENG Xiaoyao, LUO Yonglong. An Efficient and Adaptive Method for Overlapping Community Detection in Real-World Networks[J]. Chinese Journal of Electronics, 2018, 27(6): 1126-1132. doi: 10.1049/cje.2017.09.012

An Efficient and Adaptive Method for Overlapping Community Detection in Real-World Networks

doi: 10.1049/cje.2017.09.012
Funds:  This work is supported by the National Natural Science Foundation of China (No.61602009, No.61672039), the Anhui Provincial Natural Science Foundation (No.1608085MF145), and the University Natural Science Research Project of Anhui Province (No.KJ2015A067).
More Information
  • Corresponding author: LUO Yonglong (corresponding author) was born in 1972. He received the Ph.D. degree in computer science and technology from University of Science and Technology of China. Currently, he is a professor and Ph.D. supervisor at Anhui Normal University. His research interests include information security and spatial data processing. (Email:ylluo@ustc.edu.cn)
  • Received Date: 2017-05-16
  • Rev Recd Date: 2017-07-14
  • Publish Date: 2018-11-10
  • In real-world networks, nodes may belong to more than one community simultaneously. Overlapping community detection in complex networks is a challenging task. An adaptive overlapping community detection method based on seed selection and expansion is proposed. Depending on the restrictions on the seed selection stage, a set of seeds is generated without specified set size. The personalized PageRank algorithm is used to evaluate the community for seed expansion. The uncovered nodes could be adaptively allocated to the appropriate clusters. A thorough comparison between the proposed method and other overlapping community detection methods considered is provided to indicate the effectiveness of the former. The experimental results demonstrate that the presented method is effective.
  • loading
  • Z. Ye, S. Hu and J. Yu, “Adaptive clustering algorithm for community detection in complex networks”, Physical Review E Statistical Nonlinear and Soft Matter Physics, Vol.78, Article ID 046115, 6 pages, 2008.
    P.J. Mucha, T. Richardson, K. Macon, et al., “Community structure in time-dependent, multiscale, and multiplex networks”, Science, Vol.328, No.5980, pp.876-878, 2010.
    J.C. Devi and E. Poovammal, “An analysis of overlapping community detection algorithms in social networks”, Procedia Computer Science, Vol.89, pp.349-358, 2016.
    M. Hajiabadi, H. Zare and H. Bobarshad, “IEDC: An integrated approach for overlapping and non-overlapping community detection”, Knowledge-Based Systems, Vol.123, pp.188-199, 2017.
    G. Palla, I. Derényi, I. Farkas, et al., “Uncovering the overlapping community structure of complex networks in nature and society”, Nature, Vol.435, No.7043, pp.814-818, 2005.
    D. Suthers, “Applications of cohesive subgraph detection algorithms to analyzing socio-technical networks”, Proceedings of the 50th Hawaii International Conference on System Sciences, Hawaii, USA, pp.2128-2137, 2017.
    C. Lee, F. Reid, A. Mcdaid, et al., “Detecting highly overlapping community structure by greedy clique expansion”, The 4th ACM SNA-KDD Workshop on Social Network Mining and Analysis, Washington, DC, USA, 10 pages, 2010.
    E. Galbrun, A. Gionis and N. Tatti, “Overlapping community detection in labeled graphs”, Data Mining and Knowledge Discovery, Vol.28, No.5-6, pp.1586-1610, 2014.
    R. Badie, A. Aleahmad, M. Asadpour, et al., “An efficient agent-based algorithm for overlapping community detection using nodes closeness”, Physica A Statistical Mechanics and Its Applications, Vol.392, No.20, pp.5231-5247, 2013.
    S.Y. Bhat and M. Abulaish, “HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks”, IEEE Transactions on Knowledge and Data Engineering, Vol.27, No.4, pp.1019-1032, 2014.
    M. Chen and B.K. Szymanski, “Fuzzy overlapping community quality metrics”, Social Network Analysis and Mining, Vol.5, No.1, pp.1-14, 2015.
    T. Nepusz, A. Petróczi, L. Négyessy, et al., “Fuzzy communities and the concept of bridgeness in complex networks”, Physical Review E Statistical Nonlinear and Soft Matter Physics, Vol.77, No.1, Article ID 016107, 13 pages, 2008.
    J. Eustace, X. Wang and Y. Cui, “Community detection using local neighborhood in complex networks”, Physica A Statistical Mechanics and Its Applications, Vol.436, pp.665-677, 2015.
    H. Tao, Y. Wang, Z. Wu, et al., “Discovering overlapping communities by clustering local link structures”, Chinese Journal of Electronics, Vol.26, No.2, pp.430-434, 2017.
    F. Moradi, T. Olovsson and P. Tsigas, “A local seed selection algorithm for overlapping community detection”, The 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Beijing, China, pp.1-8, 2014.
    J.J Whang, D.F. Gleich and I.S. Dhillon, “Overlapping community detection using neighborhood-inflated seed expansion”, IEEE Transactions on Knowledge and Data Engineering, Vol.28, No.5, pp.1272-1284, 2016.
    M. Coscia, G. Rossetti, F. Giannotti, et al., “DEMON: A localfirst discovery method for overlapping communities”, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, pp.615-623, 2012.
    U.N. Raghavan, R. Albert and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks”, Physical Review E Statistical Nonlinear and Soft Matter Physics, Vol.76, No.3, Article ID 036106, 11 pages, 2007.
    R. Andersen, F. Chung and K. Lang, “Local graph partitioning using PageRank vectors”, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, USA, 20 pages, 2006.
    R.R. Khorasgani, J. Chen and O.R. Zaïane, “Top leaders community detection approach in information networks”, The 4th SNA-KDD Workshop on Social Network Mining and Analysis, Washington, DC, USA, pp.597-605, 2010.
    U. Gargi, W. Lu, V.S. Mirrokni, et al., “Large-scale community detection on YouTube for topic discovery and exploration”, Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media, Barcelona, Catalonia, Spain, pp.486-489, 2011.
    H.H. Song, B. Savas, T.W. Cho, et al., “Clustered embedding of massive social networks”, ACM Sigmetrics/performance Joint International Conference on Measurement and Modeling of Computer Systems, London, England, UK, Vol.40, No.1, pp.331-342, 2012.
    A. Mislove, H.S. Koppula, K.P. Gummadi, et al., “Growth of the flickr social network”, Proceedings of the first workshop on Online social networks, Seattle, Washington, USA, pp.25-30, 2008.
    “Stanford Network Analysis Project” http://snap.stanford.edu/, 2014.
    H. Shen, X. Cheng, K. Cai, et al., “Detect overlapping and hierarchical community structure in networks”, Physica A Statistical Mechanics and Its Applications, Vol.388, No.8, pp.1706-1712, 2009.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (195) PDF downloads(237) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return