Mining maximal cliques from an uncertain graph

Arko Provo Mukherjee; Pan Xu; Srikanta Tirthapura

doi:10.1109/ICDE.2015.7113288

Mining maximal cliques from an uncertain graph

Arko Provo Mukherjee, Pan Xu, Srikanta Tirthapura

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

42 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 language	English (US)
Title of host publication	2015 IEEE 31st International Conference on Data Engineering, ICDE 2015
Publisher	IEEE Computer Society
Pages	243-254
Number of pages	12
ISBN (Electronic)	9781479979639
DOIs	https://doi.org/10.1109/ICDE.2015.7113288
State	Published - May 26 2015
Externally published	Yes
Event	2015 31st IEEE International Conference on Data Engineering, ICDE 2015 - Seoul, Korea, Republic of Duration: Apr 13 2015 → Apr 17 2015

Publication series

Name	Proceedings - International Conference on Data Engineering
Volume	2015-May
ISSN (Print)	1084-4627

Conference

Conference	2015 31st IEEE International Conference on Data Engineering, ICDE 2015
Country/Territory	Korea, Republic of
City	Seoul
Period	4/13/15 → 4/17/15

All Science Journal Classification (ASJC) codes

Software
Signal Processing
Information Systems

Access to Document

10.1109/ICDE.2015.7113288

Cite this

@inproceedings{c17d1b7e42cd49c4b482513c33fb9ee8,

title = "Mining maximal cliques from an uncertain graph",

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

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

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 2015 31st IEEE International Conference on Data Engineering, ICDE 2015 ; Conference date: 13-04-2015 Through 17-04-2015",

year = "2015",

month = may,

day = "26",

doi = "10.1109/ICDE.2015.7113288",

language = "English (US)",

series = "Proceedings - International Conference on Data Engineering",

publisher = "IEEE Computer Society",

pages = "243--254",

booktitle = "2015 IEEE 31st International Conference on Data Engineering, ICDE 2015",

address = "United States",

}

Mukherjee, AP, Xu, P & Tirthapura, S 2015, Mining maximal cliques from an uncertain graph. in 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015., 7113288, Proceedings - International Conference on Data Engineering, vol. 2015-May, IEEE Computer Society, pp. 243-254, 2015 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, Korea, Republic of, 4/13/15. https://doi.org/10.1109/ICDE.2015.7113288

Mining maximal cliques from an uncertain graph. / Mukherjee, Arko Provo; Xu, Pan; Tirthapura, Srikanta.
2015 IEEE 31st International Conference on Data Engineering, ICDE 2015. IEEE Computer Society, 2015. p. 243-254 7113288 (Proceedings - International Conference on Data Engineering; Vol. 2015-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Mining maximal cliques from an uncertain graph

AU - Mukherjee, Arko Provo

AU - Xu, Pan

AU - Tirthapura, Srikanta

PY - 2015/5/26

Y1 - 2015/5/26

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

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

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

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

U2 - 10.1109/ICDE.2015.7113288

DO - 10.1109/ICDE.2015.7113288

M3 - Conference contribution

AN - SCOPUS:84940868869

T3 - Proceedings - International Conference on Data Engineering

SP - 243

EP - 254

BT - 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015

PB - IEEE Computer Society

T2 - 2015 31st IEEE International Conference on Data Engineering, ICDE 2015

Y2 - 13 April 2015 through 17 April 2015

ER -

Mining maximal cliques from an uncertain graph

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this