Journal of Guangdong University of Technology ›› 2022, Vol. 39 ›› Issue (01): 50-55.doi: 10.12052/gdutxb.210043

Previous Articles     Next Articles

A Path Adaptation-based Subgraph Matching Algorithm for Large-scale RDF Graph Data

Hu Xin-miao1, Lin Sui1, Jiang Wen-chao1,2, Xiong Meng2, He Zhong-tang2   

  1. 1. School of Computer Science and Technology, Guangdong University of Technology, Guangzhou 510006, China;
    2. Cloud Computing Center, Chinese Academy of Sciences, Dongguan 523808, China
  • Received:2021-03-11 Published:2022-01-20

HTML

PDF (PC)

2846

Abstract: 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.

Key words: social network, knowledge discovery, large-scale data graphs, subgraph query, subgraph matching

CLC Number: 

  • TP391
[1] 关皓元, 朱斌, 李冠宇, 等. 基于资源描述框架图切分与顶点选择性的高效子图匹配算法[J]. 计算机应用, 2019, 39(2): 360-369.
GUAN H Y, ZHU B, LI G Y, et al. Efficient subgraph matching method based on resource description framework graph segmentation and vertex selectivity [J]. Journal of Computer Applications, 2019, 39(2): 360-369.
[2] YU J, LIU X M, LIU Y B, et al. Multiple pattern graph correlations for efficient graph pattern matching[C]//2017 IEEE/ACS 14th International Conference on Computer Systems and Applications. Hammamet: IEEE, 2017: 469-474.
[3] 关皓元, 朱斌, 李冠宇, 等. 基于RDF图结构切分的高效子图匹配方法[J]. 计算机应用, 2018, 38(7): 1898-1904.
GUAN H Y, ZHU B, LI G Y, et al. Efficient subgraph matching method based on structure segmentation of RDF graph [J]. Journal of Computer Applications, 2018, 38(7): 1898-1904.
[4] MA Z M, CAPRETZ M A M, YAN L. Storing massive resource description framework(RDF) data: a survey [J]. Knowledge Engineering Review, 2016, 31(4): 391-413.
[5] 罗国辉, 林穗, 姜文超. 一种基于二进制编码处理的数字保序匹配算法[J]. 广东工业大学学报, 2017, 34(5): 56-59.
LUO G H, LIN S, JIANG W C. A digital order-preserving-matching algorithm based on binary coding processing [J]. Journal of Guangdong University of Technology, 2017, 34(5): 56-59.
[6] 于静, 刘燕兵, 张宇, 等. 大规模图数据匹配技术综述[J]. 计算机研究与发展, 2015, 52(2): 391-409.
YU J, LIU Y B, ZHANG Y, et al. Survey on large-scale graph pattern matching [J]. Journal of Computer Research and Development, 2015, 52(2): 391-409.
[7] 许文, 宋文爱, 富丽贞, 等. 面向大规模图数据的分布式子图匹配算法[J]. 计算机科学, 2019, 46(4): 28-35.
XU W, SONG W A, FU L Z, et al. Distributed subgraph matching algorithm for large scale graph data [J]. Computer Science, 2019, 46(4): 28-35.
[8] 李龙洋, 董一鸿, 施炜杰, 等. SQM: 基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
LI L Y, DONG Y H, SHI W J, et al. SQM: subgraph matching algorithm for single large-scale graphs under Spark [J]. Journal of Computer Applications, 2019, 39(1): 46-50.
[9] ULLMANN J R. An algorithm for subgraph isomorphism [J]. Journal of the ACM, 1976, 23(1): 31-42.
[10] CORDELLA L P, FOGGIA P. A (sub)graph isomorpism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372.
[11] HE H, SINGH A K. Graphs-at-a-time: query language and access methods for graph data bases[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 405-418.
[12] ZHANG S, LI S, YANG J. GADDI: distance index based subgraph matching in biological networks[C]//Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 192-203.
[13] 张硕, 李建中, 高宏, 等. 一种多到一子图同构检测方法[J]. 软件学报, 2010, 21(3): 401-414.
ZHANG S, LI J Z, GAO H, et al. Approach for efficient subgraph isomorphism testing for multiple graphs [J]. Journal of Software, 2010, 21(3): 401-414.
[14] HAN W S, LEE J, LEE J H. TurboISO: towards ultrafast and roubst subgraph isomorphism search in large graph databases[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 337-348.
[15] 孙云浩, 李逢雨, 李冠宇, 等. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
SUN Y H, LI F Y, LI G Y, et al. Multi-pattern matching method for RDF graph [J]. Computer Engineer and Applications, 2020, 56(13): 84-92.
[16] LI G F, YAN L, MA Z M. An approach for approximate subgraph matching in fuzzy RDF graph [J]. Fuzzy Sets and Systems, 2019, 376: 106-126.
[1] Xie Guang-qiang, Xu Hao-ran, Li Yang, Chen Guang-fu. Consensus Opinion Enhancement in Social Network with Multi-agent Reinforcement Learning [J]. Journal of Guangdong University of Technology, 2022, 39(06): 36-43.
[2] Du Helen S., Luo Zi-chan, Chen Yang-sen. Value Co-creation Based on Social Network Analysis and Counterfactual Analysis: Taking Xiaomi Virtual Community as an Example [J]. Journal of Guangdong University of Technology, 2020, 37(02): 11-21.
[3] Peng Jia-en, Deng Xiu-qin, Liu Tai-heng, Liu Fu-chun, Li Wen-zhou. A Recommendation Algorithm of Latent Factor Model Fused with the Social and Tag Information [J]. Journal of Guangdong University of Technology, 2018, 35(04): 45-50.
[4] Rao Dong-ning, Wang Jun-xing, Wei lai, Wang Ya-li. Parallel Minimal Cut Set Algorithm and Its Application in Financial Social Networks [J]. Journal of Guangdong University of Technology, 2018, 35(02): 46-50.
[5] Rao Dong-ning, Wen Yuan-li, Wei lai, Wang Ya-li. A Weighted Centrality Algorithm for Social Networks Based on Spark Platform in Different Cultural Environments [J]. Journal of Guangdong University of Technology, 2017, 34(03): 15-20.
[6] WANG Xiao-Tong. An Evaluation of Microblog Users’ Influence Based on PageRank [J]. Journal of Guangdong University of Technology, 2016, 33(03): 49-54.
[7] YANG Chun-Yan, LI Zhi-Ming. Extenics Based Social Network Structure [J]. Journal of Guangdong University of Technology, 2014, 31(1): 1-6.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © 2017 Journal of Guangdong University of Technology
Add：729 East Dongfeng RD., Guangzhou PRC. Postcode: 510090
Tel：020-37626653,020-37626139,020-37626396
Email：xbzrb@gdut.edu.cn
Supported:Beijing Magtech