Liu Kai, Zhang Yi, Lu Kai, Wang Xiaoping, Wang Xin, Tian Guojing
College of Computer, National University of Defense Technology, Changsha 410073, China.
Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China.
Entropy (Basel). 2019 Jun 5;21(6):569. 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.
图同构是指确定两个图是否具有相同的拓扑结构。它在图像匹配、生物化学和信息检索等领域发挥着重要作用。量子游走作为一种新型量子计算模型，已被用于同构映射检测，以与经典计算模型相比优化时间复杂度。然而，这些受量子启发的算法对于具有固有对称性的图（如实正则图）表现不佳，甚至无法工作。通过分析图对称性对同构检测的影响，我们提出了一种基于离散时间量子游走（DTQW）的有效图同构算法（MapEff），以提高同构映射检测的准确性，特别是对于实正则图。借助辅助边，该算法可以有效地区分对称节点，从而通过多轮选择推断出合格的同构映射。在1585对图上进行的实验表明，我们的算法与其他现有最先进算法相比具有更好的性能。
