Self-adaptive Louvain algorithm: Fast and stable community detection algorithm based on the principle of small probability event

Ziqiao Zhang, Peng Pu, Dingding Han and Ming Tang

Physica A: Statistical Mechanics and its Applications, 2018, vol. 506, issue C, 975-986

Abstract: Community structure is an important structure feature of complex networks. Due to its speed, effectiveness and simplicity, the Louvain algorithm is widely used to detect community structure planted in the network topology. Speeding up the Louvain algorithm, enabling the analysis of larger graphs in a shorter time and maintaining the accuracy of result, can benefit the research of networks in many fields. We here propose the Random Self-adaptive Neighbors Louvain algorithm as a new improved Louvain algorithm. The principle of small probability event is used to infer the number of neighbors to pick up randomly. The accuracy, speed and fluctuation of our method are compared with those of the original Louvain algorithm and the Random Neighbor Louvain algorithm. The results show that the RSNL can obtain as good partition as that of the original Louvain in a faster speed. On the networks without distinct community structures, the RSNL is faster and more accurate than the RNL. A new measure, equivalent computing time, is proposed to show the expectation runtime of the algorithm to obtain a relatively good partition. The comparison of this measure shows that the RSNL algorithm can make the best performance among the three algorithms in most cases.

Keywords: Community structure; Modularity; Louvain algorithm; Small probability event (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437118304734
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

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:506:y:2018:i:c:p:975-986

DOI: 10.1016/j.physa.2018.04.036

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().