Detecting alternative graph clusterings

Supreet Mandala, Soundar Kumara, Tao Yao

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The problem of graph clustering or community detection has enjoyed a lot of attention in complex networks literature. A quality function, modularity, quantifies the strength of clustering and on maximization yields sensible partitions. However, in most real world networks, there are an exponentially large number of near-optimal partitions with some being very different from each other. Therefore, picking an optimal clustering among the alternatives does not provide complete information about network topology. To tackle this problem, we propose a graph perturbation scheme which can be used to identify an ensemble of near-optimal and diverse clusterings. We establish analytical properties of modularity function under the perturbation which ensures diversity. Our approach is algorithm independent and therefore can leverage any of the existing modularity maximizing algorithms. We numerically show that our methodology can systematically identify very different partitions on several existing data sets. The knowledge of diverse partitions sheds more light into the topological organization and helps gain a more complete understanding of the underlying complex network.

Original languageEnglish (US)
Article number016111
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume86
Issue number1
DOIs
StatePublished - Jul 23 2012

All Science Journal Classification (ASJC) codes

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics

Fingerprint

Dive into the research topics of 'Detecting alternative graph clusterings'. Together they form a unique fingerprint.

Cite this