Driven by the emerging network applications, querying and mining uncertain graphs has become increasingly important. In this paper, we investigate a fundamental problem concerning uncertain graphs, which we call the distance-constraint reachability (DCR) problem: Given two vertices s and t, what is the probability that the distance from s to t is less than or equal to a user-defined threshold d in the uncertain graph? Since this problem is #P-Complete, we focus on efficiently and accurately approximating DCR online. Our main results include two new estimators for the probabilistic reachability. One is a Horvitz-Thomson type estimator based on the unequal probabilistic sampling scheme, and the other is a novel recursive sampling estimator, which effectively combines a deterministic recursive computational procedure with a sampling process to boost the estimation accuracy. Both estimators can produce much smaller variance than the direct sampling estimator, which considers each trial to be either 1 or 0. We also present methods to make these estimators more computationally efficient. The comprehensive experiment evaluation on both real and synthetic datasets demonstrates the efficiency and accuracy of our new estimators.
Authors in REF investigated a more generalized and informative distance-constraint reachability (DCR) query problem: given two nodes s and t in an probabilistic graph G, the aim is to compute the probability that the distance form s to t is less than or equal to d. They show that the simple reachability problem without constraint becomes a special case of the distance-constraint reachability, considering the case where the threshold d is larger than the length of the longest path.
Distance-Constraint Reachability Computation in Uncertain Graphs
PVLDB
PVLDB
Computer Science