Mining maximal cliques from an uncertain graph

Arko Provo Mukherjee, Pan Xu, Srikanta Tirthapura

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

40 Scopus citations

Abstract

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 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.

Original languageEnglish (US)
Title of host publication2015 IEEE 31st International Conference on Data Engineering, ICDE 2015
PublisherIEEE Computer Society
Pages243-254
Number of pages12
ISBN (Electronic)9781479979639
DOIs
StatePublished - May 26 2015
Externally publishedYes
Event2015 31st IEEE International Conference on Data Engineering, ICDE 2015 - Seoul, Korea, Republic of
Duration: Apr 13 2015Apr 17 2015

Publication series

NameProceedings - International Conference on Data Engineering
Volume2015-May
ISSN (Print)1084-4627

Conference

Conference2015 31st IEEE International Conference on Data Engineering, ICDE 2015
Country/TerritoryKorea, Republic of
CitySeoul
Period4/13/154/17/15

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'Mining maximal cliques from an uncertain graph'. Together they form a unique fingerprint.

Cite this