IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v428y2015icp279-294.html
   My bibliography  Save this article

Large-scale community detection based on node membership grade and sub-communities integration

Author

Listed:
  • Shang, Ronghua
  • Luo, Shuang
  • Li, Yangyang
  • Jiao, Licheng
  • Stolkin, Rustam

Abstract

Community detection plays an important role in research on network characteristics and in the mining of network information. A variety of algorithms have previously been proposed, but with the continuous growth of network scale, few of them can detect community structure efficiently. Additionally, most of these algorithms only consider non-overlapping community structures in networks. This paper addresses these problems by proposing a new algorithm, based on node membership grade and sub-communities integration, to detect community structure in large-scale networks. The proposed algorithm firstly introduces two functions based on the local information of each node in networks, namely neighboring inter-nodes membership function fMS−NN and node-to-community membership function fMS−NC. Firstly, local potential’s complete sub-graphs are efficiently mined using the function fMS−NN, and then these small graphs are merged into larger ones in light of local modularity. Secondly, incorrectly divided nodes are modified according to function fMS−NN. Additionally, by adjusting the parameters in fMS−NC, we can accurately obtain both non-overlapping communities and overlapping communities. Furthermore, the proposed algorithm employs a framework resembling label propagation, which has low time complexity and is suitable for detecting communities in large-scale networks. Experimental results on both artificial networks and real networks indicate the accuracy and efficiency of the proposed algorithm.

Suggested Citation

  • Shang, Ronghua & Luo, Shuang & Li, Yangyang & Jiao, Licheng & Stolkin, Rustam, 2015. "Large-scale community detection based on node membership grade and sub-communities integration," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 428(C), pages 279-294.
  • Handle: RePEc:eee:phsmap:v:428:y:2015:i:c:p:279-294
    DOI: 10.1016/j.physa.2015.02.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437115001004
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wu, Zhihao & Lin, Youfang & Wan, Huaiyu & Tian, Shengfeng & Hu, Keyun, 2012. "Efficient overlapping community detection in huge real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(7), pages 2475-2490.
    2. Chen, Qiong & Wu, Ting-Ting & Fang, Ming, 2013. "Detecting local community structures in complex networks based on local degree central nodes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(3), pages 529-537.
    3. Shen, Huawei & Cheng, Xueqi & Cai, Kai & Hu, Mao-Bin, 2009. "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(8), pages 1706-1712.
    4. Mu, Caihong & Liu, Yong & Liu, Yi & Wu, Jianshe & Jiao, Licheng, 2014. "Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 408(C), pages 47-61.
    5. Shang, Ronghua & Bai, Jing & Jiao, Licheng & Jin, Chao, 2013. "Community detection based on modularity and an improved genetic algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(5), pages 1215-1231.
    6. Li, Junqiu & Wang, Xingyuan & Eustace, Justine, 2013. "Detecting overlapping communities by seed community in weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6125-6134.
    7. Cui, Yaozu & Wang, Xingyuan & Li, Junqiu, 2014. "Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 85-91.
    8. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    9. Cui, Yaozu & Wang, Xingyuan & Eustace, Justine, 2014. "Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 416(C), pages 198-207.
    10. Gong, Maoguo & Liu, Jie & Ma, Lijia & Cai, Qing & Jiao, Licheng, 2014. "Novel heuristic density-based method for community detection in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 403(C), pages 71-84.
    11. Liu, X. & Murata, T., 2010. "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(7), pages 1493-1500.
    12. Wang, Xingyuan & Li, Junqiu, 2013. "Detecting communities by the core-vertex and intimate degree in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(10), pages 2555-2563.
    13. Cui, Yaozu & Wang, Xingyuan, 2014. "Uncovering overlapping community structures by the key bi-community and intimate degree in bipartite networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 407(C), pages 7-14.
    14. Li, Junqiu & Wang, Xingyuan & Cui, Yaozu, 2014. "Uncovering the overlapping community structure of complex networks by maximal cliques," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 415(C), pages 398-406.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. repec:eee:phsmap:v:495:y:2018:i:c:p:418-426 is not listed on IDEAS
    2. Bilal, Saoud & Abdelouahab, Moussaoui, 2017. "Evolutionary algorithm and modularity for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 89-96.
    3. repec:eee:phsmap:v:486:y:2017:i:c:p:1-24 is not listed on IDEAS
    4. Shang, Ronghua & Zhang, Weitong & Jiao, Licheng & Stolkin, Rustam & Xue, Yu, 2017. "A community integration strategy based on an improved modularity density increment for large-scale networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 471-485.
    5. Fu, Yu-Hsiang & Huang, Chung-Yuan & Sun, Chuen-Tsai, 2016. "Using a two-phase evolutionary framework to select multiple network spreaders based on community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 840-853.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:428:y:2015:i:c:p:279-294. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.