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

Temporal Priority Constrained Graph Pattern Strong Simulation Matching

作　　者：金浩宇 霍宏[1] 方涛[1] JIN Hao-yu;HUO Hong;FANG Tao(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《计算机技术与发展》2023年第6期88-94,共7页Computer Technology and Development

摘　　要：图模式匹配是一种在图数据上进行高效查询的重要方法,有着广泛的应用前景,例如知识发现、社交网络分析、智能问答等。大多数现有的研究工作都是基于静态的图数据,而现实生活中的图数据很多属于包含时间信息的时态图,针对时态图上的模式图匹配,该文提出了一种时序优先级约束的时序模式图强模拟匹配算法(Temporal Priority Constrained Graph Pattern Strong Simulation Matching,TPC-GPSSM)。该算法在模式图的图拓扑结构的匹配过程中加入时间顺序约束,即考虑了时态图中不同时态边之间的时序优先级,同时通过设置冗余顶点过滤规则来缩小搜索范围,优化时序检查的队列顺序,以达到提前剪枝、减少计算复杂度的目的。提出了时态边聚合度来评价算法对时态边的过滤效果,在三个时序数据集上的大量实验表明,相比传统的强模拟算法,所提算法能够有效过滤错误结果,并且在不同规模的数据图上均具有良好的性能表现。Graph pattern matching is an important method for efficient query on graph data,which has wide application prospects,such as knowledge discovery,intelligent question answering,social network analysis,and so on.Most of the existing researches are generally based on static graph data.However,many graph data with time information in real world belong to temporal graphs.Aiming at graph pattern matching in temporal graphs,a temporal priority constrained graph pattern strong simulation matching method is proposed.It introduces the constraints of time orders into the pattern graph matching as while matching the graph topology of pattern graphs,namely,it considers the temporal priorities of different temporal edges in temporal graphs.Meanwhile,redundant vertex filtering rules are set to narrow the search scope and optimize the queue of time order,so as to prune the graph in advance and reduce the computational complexity.Moreover,the temporal edge closeness is proposed to evaluate the algorithm’s performance by the filtering effects on temporal edges.Experiments results on three temporal datasets have shown that the proposed method can effectively filter out the error matching results compared with the traditional strong simulation algorithm,and also has satisfactory performance on data graphs of different scales.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]