Algorithms For Extracting Representative Possible Worlds Of Uncertain Graphs

Data in a vast number of applications like social networks and biological networks can be expressed by uncertain graphs, of which edges are labeled by a existence probability. Query and mining problems on uncertain graphs have many applications. Recently, there are many challenges in query and mining problems on uncertain graph data, among which the most important challenge is that the computation cost is very high. As exact query evaluation on uncertain graphs has to involve the exponential number of possible worlds, even a simple query problem on uncertain graphs becomes #P-complete problem. Existing query and mining algorithms are usually based on sampling techniques. Sampling techniques has to pick up many samples from possible worlds of the input uncertain graph, and conducts query processing on each samples, which makes computation cost very high. In order to improve the efficiency of query and mining problem, we study the discovery algorithms of representative possible worlds of uncertain graphs, which is to find one or more possible worlds that can represent the structure characteristics of an uncertain graph to a large degree. In this way, queries can be evaluated on these representative possible worlds, which improves query efficiency.The main contribution of this paper are as follows. We propose the concept of triangle-based representative possible world, the goal of which is to preserve node degree distribution and triangle degree distribution. This concept introduces the structure characteristic measurement of triangle degree, and overcomes the shortcomings of existing methods only considering arbitary node degree. We prove that the problem of extracting triangle-based representative possible world is NP complete problem. We propose algorithm to extract triangle-based representative possible world. Based on random edge rewiring, this algorithm can extract a triangle-based representative possible world efficiently and solve the problem of low efficiency of existing methods. We propose an algorithm framework to extract multiple representative possible worlds. Base on stratified sampling, this framework divide the set of all possible worlds of the input uncertain graph into multiple disjoint subsets with our proposed stratification strategies and edge selection strategies. We propose four algorithms to extract multiple triangle-based representative possible world through the combination of the framework and TRPW algorithm. This algorithm overcomes the problem that single representative possible world can not achieve satisfactoty results on probabilistic queries. We propose a series of uncertain graph query processing algorithms based on representative possible worlds, including node degree distributions, triangle degree distributions, triangle counts, clustering coefficients, shortest path distances and reachability. Extensive experimental results comfirm that single triangle-based representative possible world can accurately and efficiently solve a lot of query problems on uncertain graphs, such as clustering coefficient and shortest path distance. Besides these, multiple triangle-based representative possible worlds can still effectively solve the problem probabilistic query problems, like reachability.