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

Link prediction using continuous-time quantum walk

作　　者：钱菁[1] 杨林涛[1] 余泽太[1] 刘守印[1] 

机构地区：[1]华中师范大学物理科学与技术学院,武汉430079

出　　处：《计算机应用研究》2016年第1期104-107,共4页Application Research of Computers

基　　金：湖北省自然科学基金资助项目(2013CFB210)

摘　　要：链路预测是复杂网络研究的基础问题之一,目前研究者们已经提出了许多链路预测的方法,其中大量的链路预测方法是基于经典随机游走。量子游走是经典随机游走的量子模拟。大量研究表明,在诸如图匹配、搜索等很多领域,基于量子游走的量子算法的性能远优于其对应的经典随机游走算法。但目前几乎没有关于基于量子游走的链路预测算法研究报道,提出了一种基于连续时间量子游走的链路预测方法。实验结果表明,连续时间量子游走链路预测结果的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.

关 键 词：复杂网络 链路预测 量子游走 相似度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP181[自动化与计算机技术—计算机科学与技术]