Research On Top-k Subgraph Query Algorithm Based On Double Index

In this paper a graph search algorithm based on double index Top-k,the algorithm is mainly applied to labeled undirected weighted graph to heterogeneous networks and heterogeneous query graph,namely from the raw data to find large heterogeneous networks while satisfying the matching results of query graph structure and label category two conditions.The Top-k subgraph query algorithm has an obvious speed advantage in retrieving large graphs.First of all,some related concepts about graph query in data mining are described,and the research status and development and related algorithms are briefly introduced,and their advantages and disadvantages are analyzed.Secondly,in the offline phase,we propose the concept of double index for large graphs,that is two kinds indexes,graph topological index and maximum meta path weight(MMW)indexes.They sum up the topology of the network and provide the upper bound on the maximum meta path weight.At the same time,also established a large sort of edge list,which can be ordered by Top-k in the simultaneous execution of sub graph matching algorithm,in order to effectively solve the big picture on the most interesting of subgraph query problem at the same time compared to the results of the query phase diagram.Thirdly,in online query phase,a method based on index to calculate the upper bound of interest degree is proposed.In the query matching process,the candidate matches of the query nodes are pruned first according to the topological index,and then the list of sorted edges is traversed according to the order from the top to the bottom.During the traversal process,generate the size of 1 candidate matching,using the greedy algorithm to instantiate the matched candidate edges,calculated instantiated candidate maximum value,the minimum value,and has been instantiated were compared,in order to maintain the set of K heap size instantiation.Finally,extensive experiments are carried out on a number of synthetic datasets,and the experimental results and data sets are analyzed in detail.The effectiveness and rationality of the proposed algorithm are proved.