{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T16:01:12Z","timestamp":1773417672745,"version":"3.50.1"},"reference-count":32,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The National Key Research and Development Program of China","award":["2016YFB0200401"],"award-info":[{"award-number":["2016YFB0200401"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u2014and even cease to work\u2014for 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.<\/jats:p>","DOI":"10.3390\/e21060569","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T03:38:01Z","timestamp":1559792281000},"page":"569","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2155-8276","authenticated-orcid":false,"given":"Kai","family":"Liu","sequence":"first","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Yi","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Kai","family":"Lu","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Xiaoping","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China"}]},{"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Guojing","family":"Tian","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1016\/j.imavis.2008.10.013","article-title":"Graph matching using the interference of discrete-time quantum walks","volume":"27","author":"Emms","year":"2009","journal-title":"Image Vis. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-14-S7-S13","article-title":"A subgraph isomorphism algorithm and its application to biochemical data","volume":"14","author":"Bonnici","year":"2013","journal-title":"BMC Bioinform."},{"key":"ref_3","unstructured":"Dickinson, P., Dickinson, P., and Riesen, K. (2008, January 16\u201318). Generalized Graph Matching for Data Mining and Information Retrieval. Proceedings of the Industrial Conference on Advances in Data Mining: Medical Applications, E-Commerce, Marketing, and Theoretical Aspects, Leipzig, Germany."},{"key":"ref_4","first-page":"82","article-title":"Graph matching: Theoretical foundations, algorithms, and applications","volume":"2000","author":"Bunke","year":"2000","journal-title":"Proc. Vis. Interface"},{"key":"ref_5","unstructured":"Garey, M.R. (1997). Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, W. H. Freeman & Co."},{"key":"ref_6","unstructured":"Hopcroft, J.E., and Wong, J.K. (May, January 30). Linear time algorithm for isomorphism of planar graphs (Preliminary Report). Proceedings of the ACM Symposium on Theory of Computing, Seattle, WA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Beckmann, A., Berger, U., L\u00f6we, B., and Tucker, J.V. (July, January 30). Logical Approaches to Computational Barriers. Proceedings of the Second Conference on Computability in Europe, CiE 2006, Swansea, UK.","DOI":"10.1007\/11780342"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans, Pattern Anal. Mach. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1109\/TPAMI.2017.2696940","article-title":"Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3","volume":"40","author":"Carletti","year":"2017","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1109\/TPAMI.2005.138","article-title":"Exact and approximate graph matching using random walks","volume":"27","author":"Marco","year":"2005","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical Graph Isomorphism","volume":"60","author":"Mckay","year":"2013","journal-title":"J. Symbolic Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1016\/j.patcog.2008.09.001","article-title":"Graph matching using the interference of continuous-time quantum walks","volume":"42","author":"Emms","year":"2009","journal-title":"Pattern Recognit."},{"key":"ref_13","unstructured":"Qiang, X. (2011). The Research of Graph Isomorphism Algorithm Based on Quantum Walk. [Master\u2019s Thesis, National University of Defense Technology]. (In Chinese)."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Wang, X., Zhang, Y., Lu, K., Wang, X., and Liu, K. (2018). Marking Vertices to Find Graph Isomorphism Mapping Based on Continuous-Time Quantum Walk. Entropy, 20.","DOI":"10.3390\/e20080586"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty years of graph matching in pattern recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_16","unstructured":"Carletti, V., Foggia, P., Greco, A., Saggese, A., and Vento, M. (2018). Comparing performance of graph matching algorithms on huge graphs. Pattern Recognit. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Carletti, V., Foggia, P., Greco, A., Saggese, A., and Vento, M. (2018, January 17\u201319). The VF3-Light Subgraph Isomorphism Algorithm: When Doing Less Is More Effective. Proceedings of the Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), Beijing, China.","DOI":"10.1007\/978-3-319-97785-0_30"},{"key":"ref_18","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","year":"1993","journal-title":"Combinatorics Paul erdos is eighty"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Backstrom, L., and Leskovec, J. (2011, January 9\u201312). Supervised Random Walks: Predicting and Recommending Links in Social Networks. Proceedings of the Fourth ACM International Conference on Web Search and Data Mining (WSDM\u201911), Hong Kong, China.","DOI":"10.1145\/1935826.1935914"},{"key":"ref_20","unstructured":"Page, L., Brin, S., Motwani, R., and Winograd, T. (2019, May 31). The PageRank Citation Ranking: Bringing Order to the Web. Available online: http:\/\/ilpubs.stanford.edu:8090\/422\/."},{"key":"ref_21","unstructured":"Kashima, H., and Inokuchi, A. (2002, January 9). Kernels for graph classification. Proceedings of the ICDM Workshop on Active Mining, Maebashi City, Japan."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Perozzi, B., Al-Rfou, R., and Skiena, S. (2014, January 24\u201327). Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2623330.2623732"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1186\/s40537-016-0060-5","article-title":"Limited random walk algorithm for big graph data clustering","volume":"3","author":"Zhang","year":"2016","journal-title":"J. Big Data"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1687","DOI":"10.1103\/PhysRevA.48.1687","article-title":"Quantum random walks","volume":"48","author":"Aharonov","year":"1993","journal-title":"Phys. Rev. A"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"052307","DOI":"10.1103\/PhysRevA.67.052307","article-title":"Quantum random-walk search algorithm","volume":"67","author":"Shenvi","year":"2003","journal-title":"Phys. Rev. A"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"130504","DOI":"10.1103\/PhysRevLett.101.130504","article-title":"Quantum Simulations of Classical Annealing Processes","volume":"101","author":"Somma","year":"2008","journal-title":"Phys. Rev. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539705447311","article-title":"Quantum Walk Algorithm for Element Distinctness","volume":"37","author":"Ambainis","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lu, K., Zhang, Y., Xu, K., Gao, Y., and Wilson, R.C. (2014, January 24\u201328). Approximate Maximum Common Sub-graph Isomorphism Based on Discrete-Time Quantum Walk. Proceedings of the International Conference on Pattern Recognition, Stockholm, Sweden.","DOI":"10.1109\/ICPR.2014.252"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","article-title":"Quantum computation and decision trees","volume":"58","author":"Farhi","year":"1998","journal-title":"Phys. Rev. A"},{"key":"ref_30","unstructured":"Feynman, R.P., and Hibbs, A.R. (2010). Quantum Mechanics and Path Integrals, Dover Publications."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth ACM Symposium on Theory of Computing, Philadelphia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"075303","DOI":"10.1088\/1751-8113\/41\/7\/075303","article-title":"A classical approach to the graph isomorphism problem using quantum walks","volume":"41","author":"Douglas","year":"2008","journal-title":"J. Phys. A Math. Theor."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/569\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:56:26Z","timestamp":1760187386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/6\/569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,5]]},"references-count":32,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["e21060569"],"URL":"https:\/\/doi.org\/10.3390\/e21060569","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,5]]}}}