%0 Journal Article
%T Information entropy based algorithm for efficient subgraph matching<br>基于信息熵的子图匹配算法
%A MENG Fan-rong
%A ZHANG Qing
%A YAN Qiu-yan
%A <br>孟凡荣
%A 张　青
%A 闫秋艳
%J 计算机应用研究
%D 2012
%I 
%X 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.
%K graph
%K information entropy
%K subgraph matching query<br>图数据
%K 信息熵
%K 子图匹配
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=A9D9BE08CDC44144BE8B5685705D3AED&aid=11CC05D77ABBCF65B7716528DF9E465F&yid=99E9153A83D4CB11&vid=771469D9D58C34FF&iid=708DD6B15D2464E8&sid=EE2AB59C5A18EE3E&eid=BC41B8F5E6D3918E&journal_id=1001-3695&journal_name=计算机应用研究&referenced_num=0&reference_num=13