Asymptotic bounds for clustering problems in random graphs

Eugene Lykhovyd, Sergiy Butenko, Pavlo Krokhmal

Research output: Contribution to journalArticlepeer-review


Graph clustering is an important problem in network analysis. This problem can be approached by first finding a large cluster subgraph (i.e., a subgraph in which every connected component is a complete graph), perhaps in a relaxed form (connected components may have missing edges), and then assigning each of the remaining vertices to one of the connected components of the cluster subgraph according to some optimization criteria. The more vertices can be included in the initial cluster subgraph (also referred to as independent union of clusters), the more “clusterable” the graph is. This paper proposes a framework for establishing asymptotic bounds on the cardinality of independent unions of clusters in Erdős-Rényi random graphs (Formula presented.) with constant (Formula presented.), referred to as uniform random graphs. In particular, sufficient conditions ensuring (Formula presented.) (where (Formula presented.) is the number of nodes) upper bounds with probability 1 are developed and shown to be applicable for the maximum independent union of cliques as well as some clique relaxations. In addition, it is shown that every graph must have an independent union of cliques of cardinality at least (Formula presented.). Since this bound is asymptotically tight on uniform random graphs, this suggests that these graphs can be viewed as a “least clusterable” class of graphs.

Original languageEnglish (US)
Pages (from-to)485-502
Number of pages18
Issue number3
StatePublished - Apr 2024
Externally publishedYes


  • asymptotic bounds
  • independent union of cliques
  • network analysis
  • network clusterability
  • uniform random graphs

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Asymptotic bounds for clustering problems in random graphs'. Together they form a unique fingerprint.

Cite this