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

doi:10.1587/transinf.2018EDP7205

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

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information 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

Authors

Zhixiao WANG
  China University of Mining and Technology
Mengnan HOU
  China University of Mining and Technology
Guan YUAN
  China University of Mining and Technology
Jing HE
  China University of Mining and Technology
Jingjing CUI
  Baidu Online Network Technology (Beijing) Co., Ltd
Mingjun ZHU
  China University of Mining and Technology

Keyword

social network analysis, hierarchical community detection, micro-community, minimum spanning tree

Cite this

Copy

Zhixiao WANG, Mengnan HOU, Guan YUAN, Jing HE, Jingjing CUI, Mingjun ZHU, "Hierarchical Community Detection in Social Networks Based on Micro-Community and Minimum Spanning Tree" in IEICE TRANSACTIONS on Information, vol. E102-D, no. 9, pp. 1773-1783, September 2019, doi: 10.1587/transinf.2018EDP7205.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7205/_p

Copy

@ARTICLE{e102-d_9_1773,
author={Zhixiao WANG, Mengnan HOU, Guan YUAN, Jing HE, Jingjing CUI, Mingjun ZHU, },
journal={IEICE TRANSACTIONS on Information},
title={Hierarchical Community Detection in Social Networks Based on Micro-Community and Minimum Spanning Tree},
year={2019},
volume={E102-D},
number={9},
pages={1773-1783},
abstract={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.},
keywords={},
doi={10.1587/transinf.2018EDP7205},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - Hierarchical Community Detection in Social Networks Based on Micro-Community and Minimum Spanning Tree
T2 - IEICE TRANSACTIONS on Information
SP - 1773
EP - 1783
AU - Zhixiao WANG
AU - Mengnan HOU
AU - Guan YUAN
AU - Jing HE
AU - Jingjing CUI
AU - Mingjun ZHU
PY - 2019
DO - 10.1587/transinf.2018EDP7205
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2019
AB - 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.
ER -