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

Ronghua Shang, Shuang Luo, Yangyang Li, Licheng Jiao, Rustam Stolkin

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)
352 Downloads (Pure)

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 View the MathML sourcefMS−NN and node-to-community membership function View the MathML sourcefMS−NC. Firstly, local potential’s complete sub-graphs are efficiently mined using the function View the MathML sourcefMS−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 View the MathML sourcefMS−NN. Additionally, by adjusting the parameters in View the MathML sourcefMS−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.
Original languageEnglish
Pages (from-to)279-294
JournalPhysica A: Statistical Mechanics and its Applications
Volume428
Early online date14 Feb 2015
DOIs
Publication statusPublished - 15 Jun 2015

Keywords

  • Large-scale network
  • Node membership function
  • Sub-communities integration
  • Overlapping community

Fingerprint

Dive into the research topics of 'Large-scale community detection based on node membership grade and sub-communities integration'. Together they form a unique fingerprint.

Cite this