A Graph Matching Algorithm Based On The Minimal Connected Dominating Subgraph

Subgraph matching problem is essentially a subgraph isomorphism problem.Given a query graph and a data graph,subgraph matching problem refers to the process of solving all data subgraphs that are isomorphic to the query graph in the data graph.According to whether the graph structure changes with time,sulograph matching can be divided into static graph matching and dynamic graph matching.With the increasing scale of graph in the real world,the efficiency of subgraph matching algorithm is increasing exponentially,so the subgraph matching optimization method has become a hot research topic.In addition,with the rapid development of these fields,the structure of describing the relationship graph between entity objects will be updated with its development.In view of the above problems,through comparing the advantages and disadvantages of the current mainstream static graph matching and dynamic graph matching schemes,and through theoretical research and experimental demonstration,this paper proposes the static graph matching optimization method and dynamic graph matching method which are suitable for large-scale query graph.The main work of this paper is as follows:firstly,this paper introduces the current mainstream static graph matching algorithm and dynamic graph matching algorithm.Through a lot of experimental analysis,the shortcomings of the current mainstream methods are pointed out;then,by analyzing the structure of query graph and the time complexity in the process of sub graph matching,combined with the minimum connected dominating set,the k query node path is proposed to match the supporting nodes in the query graph first,reducing the iterations of the sub graph matching process;the cost model is proposed,before matching,In order to construct the optimal matching order for query nodes,priority is given to match nodes with high degree of discrimination,which reduces the size of candidate set of subsequent nodes according to the dominance relationship between query graph nodes,according to the dominated nodes in query graph,effective pruning rules are proposed to further filter the false-positive candidate set and get the final result set;considering that when the data graph changes,the traditional static graph matching algorithm is used The method can not meet the real-time requirement of dynamic graph.By analyzing the changes of the updated part of data graph and the result set before and after the update,the nodes of data graph are classified,and the index based on map candidate set label set and hierarchical path index are proposed,which avoids a lot of redundant calculation in the process of dynamic graph matching.In addition,according to the sequence of query nodes,index updating can be determined when updating the data graph.Incremental updating is used to update only the local index,which reduces the cost of index reconstruction.Finally,the static graph matching optimization algorithm mentioned above is used to improve the efficiency of dynamic graph matching.