Campus Units

Electrical and Computer Engineering

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

3-1-2017

Journal or Book Title

IEEE Transactions on Knowledge and Data Engineering

Volume

29

Issue

3

First Page

543

Last Page

555

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.

Comments

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.

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

Language

en

File Format

application/pdf

Published Version

Share

COinS