Quantum link prediction in complex networks

João P. Moutinho*, André Melo, Bruno Coutinho, István A. Kovács, Yasser Omar

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)
39 Downloads (Pure)

Abstract

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

Original languageEnglish
Article number032605
Number of pages12
JournalPhysical Review A
Volume107
Issue number3
DOIs
Publication statusPublished - 2023

Fingerprint

Dive into the research topics of 'Quantum link prediction in complex networks'. Together they form a unique fingerprint.

Cite this