Mining maximal cliques from an uncertain graph
- Arko Mukherjee ,
- Pan Xu ,
- Srikanta Tirthapura
2015 International Conference on Data Engineering |
Published by IEEE
PDF | Publication | Publication | Publication | Publication
Invited to a special issue of the journal IEEE TKDE for the best five papers from ICDE 2015.
Download BibTexWe 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 consider 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.