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

doi:10.3390/e21060569

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk
	Liu, Kai 1,3; Zhang, Yi 1,3; Lu, Kai 1,3; Wang, Xiaoping 2; Wang, Xin 1,3; Tian, Guojing 4
刊名	ENTROPY
	2019-06-01
卷号	21 期号:6 页码:16
关键词	graph isomorphism isomorphic mapping discrete-time quantum walk graph mining data mining
ISSN号	1099-4300
DOI	10.3390/e21060569
英文摘要	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.
资助项目	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
语种	英语
出版者	MDPI
WOS记录号	WOS:000475304200030
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/4503]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Kai; Wang, Xiaoping
作者单位	1.Natl Univ Def Technol, Sci & Technol Parallel & Distributed Proc Lab, Changsha 410073, Hunan, Peoples R China 2.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China 3.Natl Univ Def Technol, Coll Comp, Changsha 410073, 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.