摘要
随着图结构的大规模应用,图数据库上的查询已经成为图挖掘的研究热点。针对无向加权图,本文提出一种基于最短权值路径和拉普拉斯图谱的子图查询方法PSQuery。首先,PSQuery方法选取可表示数据图的高效特征属性;接着,对提取的特征属性按照哈希映射进行编码,将特征编码组合生成节点编码和图编码,并且基于图编码构建索引树;最后,通过实现过滤验证框架得到结果集:按照提取特征的嵌套性质进行过滤生成候选集,再根据VF2算法进行验证得到最终的超图集合。实验结果表明,提出的方法加速了无向加权图数据库上的子图查询过程,提高了查询效率。
With the wide application of graphs, the querying on graph database attracts more and more attention. This paper proposes a querying method called PSQuery based on shortest weight path and Laplacian spectra for undirected weighted graphs. Specifically, we first choose some high quality features to represent a graph, which includes the information of nodes labels, edges, shortest weight path and Laplacian spectra. Then, these information features are encoded by hash mapping, with their codes combined to build an index. Finally, we implement the filtering-and-verification framework: the false positives are pruned according to the properties of extracted features, and a candidate set is generated;the result set is obtained using the VF2 algorithm to check the candidates. The experimental results show that the proposed method speeds up the subgraph querying and improves the efficiency.
作者
朱磊
姚燕妮
高勇
王一川
姬文江
黑新宏
刘征
ZHU Lei;YAO Yanni;GAO Yong;WANG Yichuan;JI Wenjiang;HEI Xinhong;LIU Zheng(School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China;School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)
出处
《西安理工大学学报》
CAS
北大核心
2019年第3期291-299,共9页
Journal of Xi'an University of Technology
基金
国家自然科学基金资助项目(61602374,61602376)
陕西省自然科学基金资助项目(2016JQ6041,2017JQ6020)
陕西省教育厅科研计划资助项目(16JK1552,16JK1573)
关键词
图挖掘
子图查询
最短权值路径
拉普拉斯图谱
graph mining
subgraph querying
shortest weight path
Laplacian spectra
