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

• 作者: 孟凡荣 张青 闫秋艳
• 来源期刊: 计算机应用研究
• 关键词: 图数据 信息熵 子图匹配
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 4035-4037
• 页数: 3页
• 分类号: TP391|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2012.11.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孟凡荣	中国矿业大学计算机科学与技术学院	81	935	16.0	28.0
2	张青	中国矿业大学计算机科学与技术学院	27	502	11.0	22.0
3	闫秋艳	中国矿业大学计算机科学与技术学院	26	129	6.0	10.0