# Mining Maximal Cliques from an Uncertain Graph

arXiv: https://arxiv.org/abs/1310.6780 · HTML: https://mlsanity.com/paper/1310.6780/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2013.

## Built on by (most cited first, 1 of 1)

- [Concise and interpretable multi-label rule sets](https://mlsanity.com/paper/2210.01533/) (2022)

## Abstract (arXiv)

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