Distance-Constraint Reachability Computation in Uncertain Graphs
Driven by the emerging network applications, querying and mining uncertain graphs has become increasingly important. In this paper, the authors investigate a fundamental problem concerning uncertain graphs, which they 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, they focus on efficiently and accurately approximating DCR online. Their main results include two new estimators for the probabilistic reachability.