面向不确定图的概率可达查询  

Answering Probabilistic Reachability Queries over Uncertain Graphs

作　　者：袁野[1,2] 王国仁[1,2] 

机构地区：[1]医学影像计算教育部重点实验室(东北大学),沈阳110004 [2]东北大学信息科学与工程学院,沈阳110004

出　　处：《计算机学报》2010年第8期1378-1386,共9页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(60933001);国家自然科学基金面上项目(60773221);国家"八六三"高技术研究发展计划项目基金(2009AA01Z150);国家自然科学基金(60803026)资助~~

摘　　要：图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.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.

关 键 词：不确定图 可能世界 条件随机算法 路径集 割集 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]