基于参考节点嵌入的图可达性查询

来源：计算机应用杂志2016年第7期北京时间：

作者：温菊屏, 胡小生, 林冬梅, 曾亚光

单位：1. 佛山科学技术学院 电子与信息工程学院, 广东 佛山 528000;2. 佛山市计算机学会, 广东 佛山 528000;3. 佛山科学技术学院 信息与教育技术中心, 广东 佛山 528000

摘要：针对k步可达性查询算法无法解决带距离约束的图可达性查询问题，提出基于参考节点嵌入的图可达性查询算法。首先，从所有节点中选出极少数有代表性的全局参考节点，预先计算所有节点与全局参考节点之间的最短路径距离；然后，采用最短路径树和范围最小值查询技术求得局部参考节点；接着，利用三角不等式关系得到查询点对距离范围；最后，根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系，可快速得出可达性结论。针对社会关系网络和公路网络数据，将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法，其索引建立时间小4个数量级，其索引规模小2个数量级；相较于Dijkstra算法，在公路网络和社会关系网络中，直接得出可达性结论的比例分别为92%和78.6%，其查询时间大大缩短，分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销，实现在线查询计算复杂度的降低，可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

关键词：k步可达性查询,带距离约束的图可达性查询,参考节点嵌入,三角不等式关系,最短路径树

基金资助：国家自然科学基金资助项目（11474053），广东高校优秀青年创新人才培养计划项目（2013LYM_0097，2014KQNCX184）。