Answering threshold-based reachability queries over probabilistic graphs

Graph reachability queries are widely used in biological networks, social networks, ontology networks and RDF networks. Meanwhile, data extracted from those applications is inherently uncertain due to noise, incompleteness and inaccuracy, and traditional certain reachability queries cannot effectively express semantics of such uncertain graph data. Therefore, in this paper, the authors study the reachability queries over uncertain graphs under the probabilistic semantics. Specifically, they study a threshold-based probabilistic reachability (T-PR) query over an uncertain graph using the possible world semantics (called probabilistic graph). Firstly, to avoid enumerating all possible worlds, the authors propose a basic algorithm that can exactly compute T-PR query. To further speed up the basic algorithm, they develop three improved approaches, that is, u-event bounds, isomorphic graph reduction, and disjoint path/cut set bounds. Moreover, the authors combine the three improved algorithms into one entire algorithm. Finally, they have verified the effectiveness of the proposed solutions for T-PR queries through extensive experiments on real probabilistic graph datasets.