Quantum Link Prediction in Complex Networks

Autor:	Moutinho, João P., Melo, André, Coutinho, Bruno, Kovács, István A., Omar, Yasser
Rok vydání:	2021
Předmět:	Quantum Physics Condensed Matter - Disordered Systems and Neural Networks Computer Science - Social and Information Networks Physics - Biological Physics
Druh dokumentu:	Working Paper
Popis:	Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize 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, QLP, 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. Comment: Keywords: Complex Networks, Quantum Algorithms, Link Prediction, Social Networks, Protein-Protein Interaction Networks
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2112.04768 Zobrazit plný text záznamu View this record from Arxiv