摘要
子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。
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 on the basis of information measure,using 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.
出处
《计算机应用研究》
CSCD
北大核心
2012年第11期4035-4037,共3页
Application Research of Computers
基金
国家自然科学基金资助项目(71003096
61003169)
高等学校博士学科点专项科研基金资助项目(20110095110010
20100095110003)
关键词
图数据
信息熵
子图匹配
graph
information entropy
subgraph matching query