Campus Units

Electrical and Computer Engineering

Document Type

Conference Proceeding

Conference

2015 IEEE 31st International Conference Data Engineering (ICDE)

Publication Version

Accepted Manuscript

Link to Published Version

https://doi.org/10.1109/ICDE.2015.7113288

Publication Date

2015

Journal or Book Title

2015 IEEE 31st International Conference Data Engineering (ICDE)

First Page

243

Last Page

254

DOI

10.1109/ICDE.2015.7113288

Conference Date

April 13-17, 2015

City

Seoul, South Korea

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

Comments

This is a manuscript of a proceeding published as Mukherjee, Arko Provo, Pan Xu, and Srikanta Tirthapura. "Mining maximal cliques from an uncertain graph." In Data Engineering (ICDE), 2015 IEEE 31st International Conference on, pp. 243-254. IEEE, 2015. 10.1109/ICDE.2015.7113288. Posted with permission.

Rights

© 2015 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

Article Location

 
COinS