GenPerm: A Unified Method for Detecting Non-Overlapping and Overlapping Communities

Tanmoy Chakraborty, Suhansanu Kumar, Niloy Ganguly, Animesh Mukherjee, Sanjukta Bhowmick

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Detection of non-overlapping and overlapping communities are essentially the same problem. However, current algorithms focus either on finding overlapping or non-overlapping communities. We present a generalized framework that can identify both non-overlapping and overlapping communities, without any prior input about the network or its community distribution. To do so, we introduce a vertex-based metric, GenPerm, that quantifies by how much a vertex belongs to each of its constituent communities. Our community detection algorithm is based on maximizing the GenPerm over all the vertices in the network. We demonstrate, through experiments over synthetic and real-world networks, that GenPerm is more effective than other metrics in evaluating community structure. Further, we show that due to its vertex-centric property, GenPerm can be used to unfold several inferences beyond community detection, such as core-periphery analysis and message spreading. Our algorithm for maximizing GenPerm outperforms six state-of-the-art algorithms in accurately predicting the ground-truth labels. Finally, we discuss the problem of resolution limit in overlapping communities and demonstrate that maximizing GenPerm can mitigate this problem.

Original languageEnglish (US)
Article number7452622
Pages (from-to)2101-2114
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number8
StatePublished - Aug 1 2016


  • GenPerm
  • algorithm
  • community scoring metric
  • non-overlapping communities
  • overlapping communities

ASJC Scopus subject areas

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


Dive into the research topics of 'GenPerm: A Unified Method for Detecting Non-Overlapping and Overlapping Communities'. Together they form a unique fingerprint.

Cite this