Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure

Caihong Mu, Yong Liu, Yi Liu, Jianshe Wu and Licheng Jiao

Physica A: Statistical Mechanics and its Applications, 2014, vol. 408, issue C, 47-61

Abstract: Community detection is one of the most important problems in complex networks. Many algorithms have been proposed in the last decade, and most of them focus on the non-overlapping community structures in the early days. Overlapping and hierarchical structures are another two important properties in complex networks, which have attracted researchers’ extensive concern in recent years. In this paper, we proposed a two-stage method which can detect the hierarchical, non-overlapping and overlapping community structures in complex networks. In this method, the CNM algorithm, a fast hierarchical agglomerative algorithm proposed by Clauset, Newman and Moore, is used in the first stage. In the second stage, a new evaluation function named as influence coefficient based on the local community structure is proposed, which can get the overlapping community structures at different overlapping levels by adjusting a tunable parameter. Besides, the proposed evaluation function can detect the wrongly classified nodes in the partition of the first stage and correct them. Finally, the computational complexity of the algorithm is low. The experimental results on both synthetic and real-world network datasets show the efficiency of our method.

Keywords: Community structure; Community detection; Overlapping structure; Hierarchical structure; Influence coefficient (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437114003343
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:408:y:2014:i:c:p:47-61

DOI: 10.1016/j.physa.2014.04.023

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 ().