Answering probabilistic reachability queries over uncertain graphs

Graph reachability queries are widely used in biological networks, social networks, ontology networks, RDF and XML databases. Meanwhile, data extracted from those applications is inherently uncertain due to noise, incompleteness and inaccuracy, and many works have been proposed to study uncertain RDF and XML databases. This paper discusses the reachability queries over uncertain graphs, specifically a probabilistic reachability (PR) query over an uncertain graph using the possible world semantics. It is proved that processing PR query is a #P-complete problem. The authors first propose a basic random algorithm to efficiently estimate the reachable probability with a high quality. To further improve the basic method, the authors introduce conditional distribution in random algorithm called conditional random algorithm(CRA), and compute the disjoint path set and cut set probabilities for the conditional distribution that is used in CRA, which helps us to find the querying results in polynomial time. Finally, the authors have verified the effectiveness of the proposed solutions for PR queries through extensive experiments on real uncertain graph datasets.