Article
Enumeration of Maximal Cliques from an Uncertain Graph
IEEE Transactions on Knowledge and Data Engineering
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
3-1-2017
DOI
10.1109/TKDE.2016.2527643
Abstract
We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter 0 ;a ;1, we define the notion of an a-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of a-maximal cliques possible within a (uncertain) graph. We present an algorithm to enumerate a-maximal cliques whose worst-case runtime is near-optimal, and an experimental evaluation showing the practical utility of the algorithm.
Rights
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Copyright Date
2017
Language
en
File Format
application/pdf
Citation Information
Srikanta Tirthapura, Pan Xu and Arko Provo Mukherjee. "Enumeration of Maximal Cliques from an Uncertain Graph" IEEE Transactions on Knowledge and Data Engineering Vol. 29 Iss. 3 (2017) p. 543 - 555 Available at: http://works.bepress.com/srikanta-tirthapura/13/
This is a manuscript of an article published as Mukherjee, Arko Provo, Pan Xu, and Srikanta Tirthapura. "Enumeration of maximal cliques from an uncertain graph." IEEE Transactions on Knowledge and Data Engineering 29, no. 3 (2017): 543-555. 10.1109/TKDE.2016.2527643. Posted with permission.