摘要
子图查询与匹配是社会网络分析和大规模网络图知识发现中的核心技术,也是决定大规模社会网络分析和知识发现准确性的关键。针对当前大规模图数据环境下子图查询算法准确率低、开销大的问题,提出基于路径适配的子图匹配算法。首先基于路径建立图数据的RDF(Resource Description Framework,资源描述框架)索引;然后将查询子图分解为一组路径,在分解过程中为每条路径获得一组候选匹配路径;最后通过k-partition交集图将候选路径连接在一起,从而构建出查询图的结果子图。实验测试了在不同数据集上的路径索引构建时间以及F-measure值,与Spath(Shortest Path,最短路径)算法、Sapper算法和SQM(Subgraph Query Matching,子图查询匹配)算法相比,在处理大规模数据时,该算法的查询准确率提高了15%。
Subgraph pattern matching is the core technology in social network analysis and knowledge discovery,and also the key to determine the accuracy of social network analysis and knowledge discovery.In view of the low accuracy and high cost of the subgraph query algorithm based on backtracking in large-scale data graph environment,a subgraph matching algorithm based on path adaptation is proposed.First,an index based on the path RDF(Resource Description Framework)graph is built.Then,the query graph is decomposed into a set of paths,for each path in the process of decomposition to obtain a set of candidate paths.Finally,the candidate paths are concatenated together through the k-partition intersection graph to build the result subgraph of the query graph.Compared with Spath(Shortest Path)algorithm,Sapper algorithm and SQM(Subgraph Query Matching)algorithm,this algorithm improves the query accuracy by 15%when dealing with large-scale data.
作者
胡新苗
林穗
姜文超
熊梦
贺忠堂
Hu Xin-miao;Lin Sui;Jiang Wen-chao;Xiong Meng;He Zhong-tang(School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China;Cloud Computing Center,Chinese Academy of Sciences,Dongguan 523808,China)
出处
《广东工业大学学报》
CAS
2022年第1期50-55,共6页
Journal of Guangdong University of Technology
基金
国家重点研发计划项目(2018YFB1003603)
广东省自然科学基金资助项目(2018A030313061)
广东省科技计划项目(2019B010139001)
广州市科技计划项目(201902020016)。
关键词
社会网络
知识发现
大规模数据图
子图查询
子图匹配
social network
knowledge discovery
large-scale data graphs
subgraph query
subgraph matching
