基于连续时间量子游走的链路预测方法研究

摘要

链路预测是复杂网络研究的基础问题之一，目前研究者们已经提出了许多链路预测的方法，其中大量的链路预测方法是基于经典随机游走。量子游走是经典随机游走的量子模拟。大量研究表明，在诸如图匹配、搜索等很多领域，基于量子游走的量子算法的性能远优于其对应的经典随机游走算法。但目前几乎没有关于基于量子游走的链路预测算法研究报道，提出了一种基于连续时间量子游走的链路预测方法。实验结果表明，连续时间量子游走链路预测结果的 AUC 值和经典随机游走的结果非常接近。而在 precision 和 recall 指标上，远优于经典随机游走的链路预测结果。%Link prediction is one of the key issues of complex networks.Many link prediction methods have been proposed so far.The classical random walk as an effective tool has been widely used to study the link prediction problems.Quantum walk is the quantum analogue of classical random walk.Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications,such as graph matching,searching etc..But few of the re-search is about the link prediction based on quantum walk.This paper proposed a new link prediction method based on conti-nuous-time quantum walk.Experiments show that the AUC result of continuous-time quantum walk is very close to that of the classical random walk,while the precision and recall results of continuous-time quantum walk are much higher than that of the classical random walk.