Information entropy based algorithm for efficient subgraph matching
基于信息熵的子图匹配算法

Subgraph matching query refers to input a query graph and a data graph, and output the graph which contains all the subgraphs of the data graph. Subgraph query is widely used in social network, biological network and the query application of the information network. Current work on subgraph matching queries used static cost models which could be ineffective due to long-tailed degree distributions, for it would spend more time in traversing the adjacent node. According to the information entropy in the basis of information measure, the conditional information entropy as the basic for the heuristic matching subgraph matching algorithm, this paper proposed an information entropy based algorithm for efficient subgraph matching. Experiments show that the proposed method has a higher efficiency of inquires. And in the long-tailed degree distributions of dataset, the effect is more apparent.