Density-based shrinkage for revealing hierarchical and overlapping community structure in networks |
| |
Authors: | Jianbin Huang Heli SunJiawei Han Boqin Feng |
| |
Institution: | a School of Software, Xidian University, Xi’an, Chinab Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, Chinac Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA |
| |
Abstract: | The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods. |
| |
Keywords: | Complex networks Community detection Hierarchical clustering Overlapping communities Hubs and outliers |
本文献已被 ScienceDirect 等数据库收录! |
|