A game-theoretic approach to graph clustering

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The last decade has witnessed an explosion in the modeling of complex systems. Predominantly, graphs are used to represent these systems. The problem of detecting overlapping clusters in graphs is of utmost importance. We present a novel definition of overlapping clusters. A noncooperative game is proposed such that the equilibrium conditions of the game correspond to the clusters in the graph. Several properties of the game are analyzed and exploited to show the existence of a pure Nash equilibrium (NE) and compute it effectively We present two algorithms to compute NE and prove their convergence. Empirically, the running times of both algorithms are nearly linear in the number of edges. Also, one of the algorithms can be readily parallelized, making it scalable. Finally, our approach is compared with existing overlapping cluster detection algorithms and validated on several artificial and real data sets.

Original languageEnglish (US)
Pages (from-to)629-643
Number of pages15
JournalINFORMS Journal on Computing
Issue number3
StatePublished - 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'A game-theoretic approach to graph clustering'. Together they form a unique fingerprint.

Cite this