动态图模式匹配技术综述

来源：软件学报杂志2018年第3期北京时间：

作者：许嘉,张千桢,赵翔,吕品,李陶深

单位：许嘉，广西大学 计算机与电子信息学院, 广西 南宁 530004;广西高校并行分布式计算技术重点实验室(广西大学), 广西 南宁 530004;广西高校多媒体通信与信息处理重点实验室(广西大学), 广西 南宁 53000411,张千桢，广西大学 计算机与电子信息学院, 广西 南宁 53000402,赵翔，国防科技大学 系统工程学院, 湖南 长沙 41007303,吕品，广西大学 计算机与电子信息学院, 广西 南宁 530004;广西高校并行分布式计算技术重点实验室(广西大学), 广西 南宁 530004;广西高校多媒体通信与信息处理重点实验室(广西大学), 广西 南宁 53000404,李陶深，广西大学 计算机与电子信息学院, 广西 南宁 530004;广西高校并行分布式计算技术重点实验室(广西大学), 广西 南宁 53000405

摘要：随着大数据时代的到来，多源异构数据的快速增长已经成为开放性问题，数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中，例如网络安全分析和社交网络舆情分析，描述实体对象之间关系的图数据的结构和内容往往不是固定不变的，图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此，如何在动态更新的图数据中进行高效的查询、匹配，是目前研究的热点问题.从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展.最后，对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望.

关键词：动态图;图模式匹配;子图同构;匹配算法;图搜索

基金资助：国家自然科学基金（61402494，61402498，61402513）；广西自然科学基金青年基金（2015GXNSFBA139243，2016GXNSFBA380182）；广西大学科研基金（XGZ141182，XGZ150322）；广西高等教育本科教学改革工程重点项目（2017JGZ103）