Hierarchical Community Detection in Social Networks Based on Micro-Community and Minimum Spanning Tree

Zhixiao WANG  Mengnan HOU  Guan YUAN  Jing HE  Jingjing CUI  Mingjun ZHU  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.9   pp.1773-1783
Publication Date: 2019/09/01
Publicized: 2019/06/05
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7205
Type of Manuscript: PAPER
Category: Data Engineering, Web Information Systems
social network analysis,  hierarchical community detection,  micro-community,  minimum spanning tree,  

Full Text: PDF(1.1MB)>>
Buy this Article

Social networks often demonstrate hierarchical community structure with communities embedded in other ones. Most existing hierarchical community detection methods need one or more tunable parameters to control the resolution levels, and the obtained dendrograms, a tree describing the hierarchical community structure, are extremely complex to understand and analyze. In the paper, we propose a parameter-free hierarchical community detection method based on micro-community and minimum spanning tree. The proposed method first identifies micro-communities based on link strength between adjacent vertices, and then, it constructs minimum spanning tree by successively linking these micro-communities one by one. The hierarchical community structure of social networks can be intuitively revealed from the merging order of these micro-communities. Experimental results on synthetic and real-world networks show that our proposed method exhibits good accuracy and efficiency performance and outperforms other state-of-the-art methods. In addition, our proposed method does not require any pre-defined parameters, and the output dendrogram is simple and meaningful for understanding and analyzing the hierarchical community structure of social networks.