基于信息熵的子图匹配算法

子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。

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.