On the detectability of node grouping in networks

Chi Wang, Hongning Wang, Jialu Liu, Ming Ji, Lu Su, Yuguo Chen, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In typical studies of node grouping detection, the grouping is presumed to have a certain type of correlation with the network structure (e.g., densely connected groups of nodes that are loosely connected in between). People have defined different fitness measures (modularity, conductance, etc.) to quantify such correlation, and group the nodes by optimizing a certain fitness measure. However, a particular grouping with desired semantics, as the target of the detection, is not promised to be detectable by each measure. We study a fundamental problem in the process of node grouping discovery: Given a particular grouping in a network, whether and to what extent it can be discovered with a given fitness measure. We propose two approaches of testing the detectability, namely ranking-based and correlation-based randomization tests. Our methods are evaluated on both synthetic and real datasets, which shows the proposed methods can effectively predict the detectability of groupings of various types, and support explorative process of node grouping discovery.

Original languageEnglish (US)
Title of host publicationProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
EditorsJoydeep Ghosh, Zoran Obradovic, Jennifer Dy, Zhi-Hua Zhou, Chandrika Kamath, Srinivasan Parthasarathy
PublisherSiam Society
Number of pages9
ISBN (Electronic)9781611972627
StatePublished - 2013
EventSIAM International Conference on Data Mining, SDM 2013 - Austin, United States
Duration: May 2 2013May 4 2013

Publication series

NameProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013


OtherSIAM International Conference on Data Mining, SDM 2013
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Science Applications
  • Software
  • Theoretical Computer Science
  • Information Systems
  • Signal Processing


Dive into the research topics of 'On the detectability of node grouping in networks'. Together they form a unique fingerprint.

Cite this