Distance-Constraint Reachability Computation in Uncertain Graphs
Distance-Constraint Reachability Computation in Uncertain Graphs
复制标题
DOI：
10.14778/2002938.2002941
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
R. Jin;Lin Liu;Bolin Ding;Haixun Wang
中科院分区：
文献类型：
--
作者：
R. Jin;Lin Liu;Bolin Ding;Haixun Wang
在新兴网络应用的推动下，不确定图的查询和挖掘变得越来越重要。在本文中，我们研究一个基本的问题，我们称之为距离约束可达性（DCR）的问题：给定两个顶点s和t，是什么概率，从s到t的距离小于或等于一个用户定义的阈值d的不确定图？由于这个问题是#P-Complete，我们专注于在线高效准确地近似DCR。我们的主要结果包括两个新的估计的概率可达性。一种是基于不等概率抽样方案的Horvitz-Thomson型估计器，另一种是一种新的递归抽样估计器，它有效地将确定性递归计算过程与抽样过程相结合，以提高估计精度。这两种估计量都可以产生比直接抽样估计量小得多的方差，直接抽样估计量将每次试验视为1或0。我们还提出了方法，使这些估计更计算效率。在真实的数据集和合成数据集上的综合实验评价表明了新估计的有效性和准确性。
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.