Fast Subgraph Matching by Dynamic Graph Editing

doi:10.1109/TSC.2023.3333840

	Fast Subgraph Matching by Dynamic Graph Editing
	Jiang, Zite 1,2,3; Zhang, Shuai 1,2; Liu, Boxiao 1,2; Hou, Xingzhong 1,2; Yuan, Mengting 4; You, Haihang 1,3
	2024-09-01
发表期刊	IEEE TRANSACTIONS ON SERVICES COMPUTING
ISSN	1939-1374
卷号	17 期号:5 页码:2432-2443
摘要	Subgraph matching is a challenging NP-complete problem that involves finding identical subgraphs of a query graph qq in a larger data graph G. It has numerous applications in diverse fields, including social and biological networks. However, existing subgraph matching algorithms assume that the graph structure is fixed, which limits their performance in solving more difficult matching cases. To address this issue, we propose a novel approach called Dynamic Graph Editing (DGE), which dynamically edits the query graph to optimize the subgraph matching algorithm. Based on this approach, we introduce an efficient enumeration method called Dynamic Graph Editing Enumeration, which significantly improves the performance of the algorithm. Our experimental results show that DGE outperforms current state-of-the-art algorithms in terms of computational efficiency and ability to solve more complex subgraph matching cases.
关键词	Heuristic algorithms Optimization Search problems Approximation algorithms Social networking (online) Pattern matching Constraint handling Graph algorithm subgraph matching query processing optimization technique
DOI	10.1109/TSC.2023.3333840
收录类别	SCI
语种	英语
资助项目	Natural Science Foundation of China[41930110] ; Natural Science Foundation of China[61872272]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering
WOS记录号	WOS:001336306800005
出版者	IEEE COMPUTER SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/41183
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Yuan, Mengting; You, Haihang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, SKLP, Beijing 100045, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 101408, Peoples R China 3.Zhongguancun Lab, Beijing 100190, Peoples R China 4.Wuhan Univ, Sch Comp Sci, Wuhan 430072, Peoples R China
推荐引用方式 GB/T 7714	Jiang, Zite,Zhang, Shuai,Liu, Boxiao,et al. Fast Subgraph Matching by Dynamic Graph Editing[J]. IEEE TRANSACTIONS ON SERVICES COMPUTING,2024,17(5):2432-2443.
APA	Jiang, Zite,Zhang, Shuai,Liu, Boxiao,Hou, Xingzhong,Yuan, Mengting,&You, Haihang.(2024).Fast Subgraph Matching by Dynamic Graph Editing.IEEE TRANSACTIONS ON SERVICES COMPUTING,17(5),2432-2443.
MLA	Jiang, Zite,et al."Fast Subgraph Matching by Dynamic Graph Editing".IEEE TRANSACTIONS ON SERVICES COMPUTING 17.5(2024):2432-2443.