Revealing density-based clustering structure from the core-connected tree of a network

Jianbin Huang, Heli Sun, Qinbao Song, Hongbo Deng, Jiawei Han

Research output: Contribution to journalArticlepeer-review


Clustering is an important technique for mining the intrinsic community structures in networks. The density-based network clustering method is able to not only detect communities of arbitrary size and shape, but also identify hubs and outliers. However, it requires manual parameter specification to define clusters, and is sensitive to the parameter of density threshold which is difficult to determine. Furthermore, many real-world networks exhibit a hierarchical structure with communities embedded within other communities. Therefore, the clustering result of a global parameter setting cannot always describe the intrinsic clustering structure accurately. In this paper, we introduce a novel density-based network clustering method, called graph-skeleton-based clustering (gSkeletonClu). By projecting an undirected network to its core-connected maximal spanning tree, the clustering problem can be converted to detect core connectivity components on the tree. The density-based clustering of a specific parameter setting and the hierarchical clustering structure both can be efficiently extracted from the tree. Moreover, it provides a convenient way to automatically select the parameter and to achieve the meaningful cluster tree in a network. Extensive experiments on both real-world and synthetic networks demonstrate the superior performance of gSkeletonClu for effective and efficient density-based clustering.

Original languageEnglish (US)
Article number6200274
Pages (from-to)1876-1889
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number8
StatePublished - Aug 2013


  • Density-based method
  • Hierarchical clustering
  • Network clustering
  • Parameter selection
  • Spanning tree

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Revealing density-based clustering structure from the core-connected tree of a network'. Together they form a unique fingerprint.

Cite this