2021/12/09 by João P. Moutinho, Moutinho, João P., André Melo +7 · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Bioinformatics and Genomic Networks #Biological Physics (physics.bio-ph) #Complex Network Analysis Techniques #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2112.04768
openalex publication_date 2021/12/09 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
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.