Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

Jianbin Huang, Heli Sun, Jiawei Han, Boqin Feng

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)2160-2171
Number of pages12
JournalPhysica A: Statistical Mechanics and its Applications
Volume390
Issue number11
DOIs
StatePublished - Jun 1 2011

Keywords

  • Community detection
  • Complex networks
  • Hierarchical clustering
  • Hubs and outliers
  • Overlapping communities

ASJC Scopus subject areas

  • Statistics and Probability
  • Condensed Matter Physics

Fingerprint Dive into the research topics of 'Density-based shrinkage for revealing hierarchical and overlapping community structure in networks'. Together they form a unique fingerprint.

  • Cite this