Journal Article

Link Prediction with Continuous-Time Classical and Quantum Walks

Malmi, Joonas, Rossi, Matteo A. C., Goldsmith, Mark, García-Pérez, Guillermo, Saarinen, Harto, Maniscalco, Sabrina

2023

Overview

Protein–protein interaction (PPI) networks consist of the physical and/or functional interactions between the proteins of an organism, and they form the basis for the field of network medicine. Since the biophysical and high-throughput methods used to form PPI networks are expensive, time-consuming, and often contain inaccuracies, the resulting networks are usually incomplete. In order to infer missing interactions in these networks, we propose a novel class of link prediction methods based on continuous-time classical and quantum walks. In the case of quantum walks, we examine the usage of both the network adjacency and Laplacian matrices for specifying the walk dynamics. We define a score function based on the corresponding transition probabilities and perform tests on six real-world PPI datasets. Our results show that continuous-time classical random walks and quantum walks using the network adjacency matrix can successfully predict missing protein–protein interactions, with performance rivalling the state-of-the-art.

• Publisher: MDPI AG,MDPI
• Subject: Algorithms / link prediction / Methods / Networks / Probability / Proteins / protein–protein interaction networks / quantum walks / Random walk / random walks / Social networks / Transition probabilities