Original scientific paper

https://doi.org/10.17559/TV-20160104014155

Link prediction using discrete-time quantum walk

Jing Qian ; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Lintao Yang ; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Zetai Yu ; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Shouyin Liu ; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China

Abstract

Link prediction is one of the key issues of complex networks, which attracts much research interest currently. 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 and searching. But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk. This paper proposes a new link prediction method based on discrete-time quantum walk. Experiment results show that prediction accuracy of our method is better than the typical methods. The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher. But our method can be greatly accelerated by executing on quantum computers.

Keywords

complex networks; discrete-time quantum walk; computer engineering; link prediction

Hrčak ID:

188227

URI

https://hrcak.srce.hr/188227

Publication date:

25.10.2017.

Article data in other languages: croatian

Visits: 2.367 *