Processing k-nearest neighbors query over uncertain graphs

Complex networks, such as biological networks, social networks, and communication networks, have been widely studied, and the data extracted from those applications is inherently uncertain due to noise, incompleteness and inaccuracy, so these applications can be modeled as uncertain graphs. The k-nearest neighbors (kNN) is a fundamental query for uncertain graphs, which is to compute the k nearest nodes to some specific node in a graph. In this paper, we design a framework for processing kNN query in uncertain graphs. We firstly propose a new kNN query over uncertain graphs, following which a novel algorithm is proposed to solve the kNN query. Then we optimize this algorithm which greatly improves the efficiency of the kNN query. Theoretical analysis and experimental results show that the proposed algorithm can efficiently retrieve the answer of a kNN query for an uncertain graph.