Node Similarity Top-k Query of the Large-Scale Dynamic Graph With Weak Repeated Path Constraint

Node similarity Top-k query has always been a hot topic in the graph field. The existing node similarity Top-k query methods often need to traverse the whole graph, so its iterative calculation process is very inefficient on the large-scale graph. Besides, when the graph changes dynamically, it is difficult to update the query process and results adaptively, leading to the low accuracy of the query results. To solve those problems, in this paper, we propose a node similarity Top-k query method of the large-scale dynamic graph with weak repeated path constraint. In this method, we first divide the similarity relation according to the correlation degree of nodes in the base graph. Then, we put forward the direct similarity and the generic similarity, meanwhile, give their definition and expression, prove the isolation of direct similarity query in the base graph based on the direct similarity relation. And then a quick query method for the direct similarity Top-k attached result set of $i$ step walk is given on the basis of the value of Top-k. When the attached result set of the direct similarity query cannot satisfy the strict Top-k query requirement, by setting weak repeated path multilevel constraint and introducing the idea of the Monte Carlo simulation, we put forward single-edge weaken factor and change the base graph into many single-direction graphs by weak pageRank random walk mechanism, and then realize the cumulative calculation for the generic similarity Top-k complete result set in single-direction graph set. Finally, according to the dynamic characteristics of the graph, based on the principle of local adaptation, we set the trigger update strategy of the base graph and the linkage update strategy of the weak single-direction graph set to ensure the accuracy of the query and minimize the updating maintenance cost. The experiments show that the method in this paper has great advantages in query efficiency, query accuracy, and update efficiency.