2013/10/24 by Mukherjee, Arko Provo, Xu, Pan, Tirthapura, Srikanta
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1310.6780
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 present a precise definition of an α-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of α-maximal cliques possible within an uncertain graph. We present an algorithm to enumerate α-maximal cliques in an uncertain graph whose worst-case runtime is near-optimal, and an experimental evaluation showing the practical utility of the algorithm.