中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk

文献类型：期刊论文

作者Liu, Kai1,3; Zhang, Yi1,3; Lu, Kai1,3; Wang, Xiaoping2; Wang, Xin1,3; Tian, Guojing4
刊名ENTROPY
出版日期2019-06-01
卷号21期号:6页码:16
关键词graph isomorphism isomorphic mapping discrete-time quantum walk graph mining data mining
ISSN号1099-4300
DOI10.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
语种英语
WOS记录号WOS:000475304200030
出版者MDPI
源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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。