Design And Research Of Isomorphic Subgraph Search Algorithm

With the development of computer network technology,network graph has gradually become an important data form in data analysis and data mining.For complex network graphs,it is necessary to model a heterogeneous information network that contains different types of nodes and edges.Isomorphic subgraph search is an important problem in the process of heterogeneous graph mining.It refers to finding all the subgraphs that are isomorphic from the large graph.The current isomorphic subgraph search algorithm is mainly faced with two problems,one is how to streamline the filter,remove the redundant traversal;the second is how to reduce the number of verification,to improve the efficiency of removing duplicates.In order to improve the time efficiency and the removing duplicates rate,this paper proposes an algorithm named DSSIS(Distinct Structural Subgraph Isomorphism Search),which based on pruning filter.The algorithm reduces the number of callbacks by substituting the replaceable nodes.Experiments show that the DSSIS algorithm can reduce the number of program callbacks and improve the efficiency of filtering time.In order to improve the efficiency of removing duplicates,this paper proposes a Hash-Index based on hash index.In the hash table,we use the numerical relation based on the node number to establish two indexes for the subgraph set.Experiments show that Hash-Index algorithm can reduce the number of traversal times of subgraph candidate sets by the classification of two numerical relational indexes,so as to improve the efficiency of verification.