基于抽样的不确定图k最近邻搜索算法

K-NEAREST NEIGHBOR SEARCH ALGORITHM FOR UNCERTAIN GRAPHS BASED ON SAMPLING

在诸如生物网络或社交网络等各种由不确定数据组成的网络中,不确定图是一种十分重要和普遍使用的数学模型。由于不确定图中计算两点连通概率问题是#P完全问题,其k最近邻查询问题要比确定图复杂得多,并且与"距离"的定义相关。采用"最短距离"作为距离定义,讨论了在不确定图是加权图的情况下,求解k最近邻搜索问题(k-NN问题)。为了克服计算两点连通概率带来的时间指数爆炸问题,提出了一个基于Dijkstra算法的抽样k-NN查询算法,研究了其收敛性和收敛速度,同时通过实验验证了所提出的方法效率优于kMinDist方法并且具有很高的查全率。

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 m u c h more complex than the normal graph and is related to the definition of ＂ distance＂ . Using the shortest distance as the definition of distance, w e 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 - N N 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.