Enumeration of Maximal Cliques from an Uncertain Graph

Arko Provo Mukherjee, Pan Xu, Srikanta Tirthapura

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < α < 1, we define the notion of an α-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of α-maximal cliques possible within a (uncertain) graph. We present an algorithm to enumerate α-maximal cliques whose worst-case runtime is near-optimal, and an experimental evaluation showing the practical utility of the algorithm.

Original languageEnglish (US)
Article number7404027
Pages (from-to)543-555
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number3
StatePublished - Mar 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Graph mining
  • dense substructure
  • maximal clique
  • uncertain graph


Dive into the research topics of 'Enumeration of Maximal Cliques from an Uncertain Graph'. Together they form a unique fingerprint.

Cite this