Enumeration of Maximal Cliques from an Uncertain Graph

Arko Provo Mukherjee; Pan Xu; Srikanta Tirthapura

doi:10.1109/TKDE.2016.2527643

Enumeration of Maximal Cliques from an Uncertain Graph

Arko Provo Mukherjee, Pan Xu, Srikanta Tirthapura

Research output: Contribution to journal › Article › peer-review

32 Scopus citations

Abstract

We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < α < 1, we define 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 language	English (US)
Article number	7404027
Pages (from-to)	543-555
Number of pages	13
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	29
Issue number	3
DOIs	https://doi.org/10.1109/TKDE.2016.2527643
State	Published - Mar 1 2017
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Keywords

Graph mining
dense substructure
maximal clique
uncertain graph

Access to Document

10.1109/TKDE.2016.2527643

Cite this

@article{607cedb14a344a44b236e8d210e56b3d,

title = "Enumeration of Maximal Cliques from an Uncertain Graph",

abstract = "We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < α < 1, we define 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.",

keywords = "Graph mining, dense substructure, maximal clique, uncertain graph",

author = "Mukherjee, {Arko Provo} and Pan Xu and Srikanta Tirthapura",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/TKDE.2016.2527643",

language = "English (US)",

volume = "29",

pages = "543--555",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - Enumeration of Maximal Cliques from an Uncertain Graph

AU - Mukherjee, Arko Provo

AU - Xu, Pan

AU - Tirthapura, Srikanta

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < α < 1, we define 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.

AB - We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < α < 1, we define 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.

KW - Graph mining

KW - dense substructure

KW - maximal clique

KW - uncertain graph

UR - http://www.scopus.com/inward/record.url?scp=85012267458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012267458&partnerID=8YFLogxK

U2 - 10.1109/TKDE.2016.2527643

DO - 10.1109/TKDE.2016.2527643

M3 - Article

AN - SCOPUS:85012267458

SN - 1041-4347

VL - 29

SP - 543

EP - 555

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 3

M1 - 7404027

ER -

Enumeration of Maximal Cliques from an Uncertain Graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this