Identifying Well-Connected Communities in Real-World and Synthetic Networks

Minhyuk Park, Yasamin Tabatabaee, Vikram Ramavarapu, Baqiao Liu, Vidya Kamath Pailodi, Rajiv Ramachandran, Dmitriy Korobskiy, Fabio Ayres, George Chacko, Tandy Warnow

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


Integral to the problem of detecting communities through graph clustering is the expectation that they are “well-connected”. Surprisingly, we find that the output of multiple clustering approaches–the Leiden algorithm with either the Constant Potts Model or modularity as quality function, Iterative K-Core Clustering, Infomap, and Markov Clustering–include communities that fail even a mild requirement for well-connectedness. As a remediation strategy, we have developed the “Connectivity Modifier” (CM), which iteratively removes small edge cuts and re-clusters until all communities detected are well-connected. Results from real-world networks with up to 75,025,194 nodes illustrate how CM enables additional insights into community structure within networks, while results on synthetic networks show that the CM algorithm improves accuracy in recovering true communities. Our study also raises questions about the “clusterability” of networks and mathematical models of community structure.

Original languageEnglish (US)
Title of host publicationComplex Networks and Their Applications XII - Proceedings of The 12th International Conference on Complex Networks and their Applications
Subtitle of host publicationCOMPLEX NETWORKS 2023
EditorsHocine Cherifi, Luis M. Rocha, Chantal Cherifi, Murat Donduran
Number of pages12
ISBN (Print)9783031534980
StatePublished - 2024
Event12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023 - Menton, France
Duration: Nov 28 2023Nov 30 2023

Publication series

NameStudies in Computational Intelligence
Volume1142 SCI
ISSN (Print)1860-949X
ISSN (Electronic)1860-9503


Conference12th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2023


  • citation networks
  • community detection
  • connectivity

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Identifying Well-Connected Communities in Real-World and Synthetic Networks'. Together they form a unique fingerprint.

Cite this