基于阈值的概率图可达查询

• 作者: 王国仁 袁野
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 概率图 可能世界 不确定事件 同构图缩减 路径集 割集
• 年，卷（期）: 2010,（12）
• 页码范围: 2219-2228
• 分类号: TP391
• 字数: 9379字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.02219

摘要

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王国仁	东北大学信息科学与工程学院	228	2804	25.0	45.0