MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk

doi:10.3390/e21060569

	MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk
	Liu, Kai 1,2; Zhang, Yi 1,2; Lu, Kai 1,2; Wang, Xiaoping 3; Wang, Xin 1,2; Tian, Guojing 4
	2019-06-01
发表期刊	ENTROPY
ISSN	1099-4300
卷号	21 期号:6 页码:16
摘要	Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well-and even cease to work-for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.
关键词	graph isomorphism isomorphic mapping discrete-time quantum walk graph mining data mining
DOI	10.3390/e21060569
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2016YFB0200401] ; program for New Century Excellent Talents in University ; National Science Foundation (NSF) China[61402492] ; National Science Foundation (NSF) China[61402486] ; National Science Foundation (NSF) China[61379146] ; laboratory pre-research fund[9140C810106150C81001] ; Natural Science Foundation of Hunan Province of China[2019JJ40340] ; HUNAN Province Science Foundation[2017RS3045]
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary
WOS记录号	WOS:000475304200030
出版者	MDPI
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4504
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Kai; Wang, Xiaoping
作者单位	1.Natl Univ Def Technol, Coll Comp, Changsha 410073, Hunan, Peoples R China 2.Natl Univ Def Technol, Sci & Technol Parallel & Distributed Proc Lab, Changsha 410073, Hunan, Peoples R China 3.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Liu, Kai,Zhang, Yi,Lu, Kai,et al. MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk[J]. ENTROPY,2019,21(6):16.
APA	Liu, Kai,Zhang, Yi,Lu, Kai,Wang, Xiaoping,Wang, Xin,&Tian, Guojing.(2019).MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk.ENTROPY,21(6),16.
MLA	Liu, Kai,et al."MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk".ENTROPY 21.6(2019):16.