Research And Implementation Of K-nearest Neighbors Query Based On BP Neural Net In Uncertain Graph

Complex networks,such as biological,social and communication netwosrks,often entail uncertainty.There are various causes of these uncertain data,such as the wrong original data,the inaccurate technical manner to get data and using coarse-grained data collection for specific applications or privacy protection.These inaccurate data constitutes an uncertain graph model.In uncertain graph problems,a fundamental problem is to search the uncertain graph's k-nearest neighbors.In the present study,the uncertain graph's k-nearest neighbors query algorithm is all focused on the possible worlds model to obtain the probabilities between nodes,then come to a set of k-nearest neighbors.But the time complexity of the query algorithm has been proven to be a#P problem.Now many scholars are in study of some ways to solve the problem.A good one of them is the sampling algorithm which has a significant effect both on time and accuracy.The Chernoff Hoeffding theorem can ensure the accuracy of the sampling algorithm.But when the sampling algorithm computes online or handles frequent queriy,we need a long time to wait for the results.Based on the current situation,I propose a BP-K-nearest neighbors query algorithm based on machine learning and using BP neural network model.The primary research includes:Firstly,I will show the single source of BP-K-nearest neighbors query algorithm(k-nearest neighbors in uncertain graph based on BP neural network)which includes how to process k-nearest neighbors query in uncertain graph by machine learning and what is the form of the training data set.Then I will describe how to use Cantor method to represent the uncertainty nodes in the graph based on the single source of BP-K-nearest neighbors query algorithm.The method expands the single source BP-K-nearest neighbors query algorithm to multiple sources BP-K-nearest neighbors query in order to let the whole uncertainty figure fit the BP network.According to this idea,I propose the following try:First,I will validate that the traditional k-nearest neighbors query algorithm in uncertain graph need a long time to query both in theory and experiments.It is difficult to deal with a big graph which comes from the real world,such as the social network.Second,I will validate that the sampling algorithm ensures the accuracy under certain condition and it is efficiency while computes part of the probability between two nodes.Then I will illustrate that it will need a long time to get the probability between nodes when the sampling algorithm computes online or handles frequent queriy.Third,I will train the BP neural network by part of the real data sets to find the right model to fit the uncertain graph and get a good prediction.At the last,I will illustrate the feasibility of the BP-K-nearest neighbors query algorithm in the real world and prove that the accuracy of the BP-K-nearest neighbors query algorithm is acceptable.