计算机应用与软件2017，Vol.34Issue(6)：180-186,7.DOI:10.3969/j.issn.1000-386x.2017.06.033
基于抽样的不确定图k最近邻搜索算法
K-NEAREST NEIGHBOR SEARCH ALGORITHM FOR UNCERTAIN GRAPHS BASED ON SAMPLING
摘要
Abstract
Uncertain graphs are a very important and widely used mathematical model in networks composed of uncertain data such as biological networks or social networks.Since the two-point connectivity probability problem in the graph is a complete problem, the k nearest-neighbor query problem is much more complex than the normal graph and is related to the definition of "distance".Using the shortest distance as the definition of distance, we discuss the k-nearest neighbor search problem (k-NN) under the condition that the uncertain graph is a weighted graph.In order to overcome the problem of time exponential explosion caused by computing two-point connectivity probability, a sampling k-NN query algorithm based on Dijkstra algorithm is proposed.The convergence rate and convergence rate are studied.The proposed method is proved to be more efficient than kMinDist method and has high recall rate.关键词
人工智能/不确定图/概率图/生物网络/k-NN/抽样技术Key words
Artificial intelligence/Uncertain graphs/Probability graph/Biological network k-NN/Sampling technique分类
信息技术与安全科学引用本文复制引用
张伟..基于抽样的不确定图k最近邻搜索算法[J].计算机应用与软件,2017,34(6):180-186,7.基金项目
国家科技支撑计划项目(2014BAI17B01) （2014BAI17B01）
软件开发环境国家重点实验室开放课题(SKLSDE-2012KF-02). （SKLSDE-2012KF-02）
