时序优先级约束的时序模式图强模拟匹配

来源：计算机技术与发展杂志2023年第06期北京时间：

作者：金浩宇;霍宏;方涛

单位：上海交通大学 电子信息与电气工程学院,上海 200240 Author(s): JIN Hao-yu;HUO Hong;FANG Tao School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China 关键词: 模式图匹配;时态图;强模拟;图模拟;时序模式图 Keywords: graph pattern matching;temporal graph;strong simulation;graph simulation;temporal graph pattern 分类号: TP301 DOI: 10. 3969 / j. issn. 1673-629X. 2023. 06. 014 摘要: 图模式匹配是一种在图数据上进行高效查询的重要方法,有着广泛的应用前景,例如知识发现、社交网络分析、智能问答等。 大多数现有的研究工作都是基于静态的图数据,而现实生活中的图数据很多属于包含时间信息的时态图,针对时态图上的模式图匹配,该文提出了一种时序优先级约束的时序模式图强模拟匹配算法( Temporal Priority ConstrainedGraph Pattern Strong Simulation Matching,TPC-GPSSM) 。 该算法在模式图的图拓扑结构的匹配过程中加入时间顺序约束,即考虑了时态图中不同时态边之间的时序优先级,同时通过设置冗余顶点过滤规则来缩小搜索范围,优化时序检查的队列顺序,以达到提前剪枝、减少计算复杂度的目的。 提出了时态边聚合度来评价算法对时态边的过滤效果,在三个时序数据集上的大量实验表明,相比传统的强模拟算法,所提算法能够有效过滤错误结果,并且在不同规模的数据图上均具有良好的性能表现。

摘要：图模式匹配是一种在图数据上进行高效查询的重要方法,有着广泛的应用前景,例如知识发现、社交网络分析、智能问答等。 大多数现有的研究工作都是基于静态的图数据,而现实生活中的图数据很多属于包含时间信息的时态图,针对时态图上的模式图匹配,该文提出了一种时序优先级约束的时序模式图强模拟匹配算法( Temporal Priority ConstrainedGraph Pattern Strong Simulation Matching,TPC-GPSSM) 。 该算法在模式图的图拓扑结构的匹配过程中加入时间顺序约束,即考虑了时态图中不同时态边之间的时序优先级,同时通过设置冗余顶点过滤规则来缩小搜索范围,优化时序检查的队列顺序,以达到提前剪枝、减少计算复杂度的目的。 提出了时态边聚合度来评价算法对时态边的过滤效果,在三个时序数据集上的大量实验表明,相比传统的强模拟算法,所提算法能够有效过滤错误结果,并且在不同规模的数据图上均具有良好的性能表现。

关键词：模式图匹配;时态图;强模拟;图模拟;时序模式图