Link prediction with continuous-time classical and quantum walks
arXiv:2208.11030 · doi:10.3390/e25050730
Abstract
Protein-protein interaction (PPI) networks consist of the physical and/or functional interactions between the proteins of an organism. 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 random walks. In the case of quantum walks, we examine the usage of both the network adjacency and Laplacian matrices for controlling the walk dynamics. We define a score function based on the corresponding transition probabilities and perform tests on four 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.
arXiv comment9 pages, 5 figures
References in corpus (21)
- Emergence of scaling in random networks
- Evolution of the social network of scientific collaborations
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- Growing Scale-Free Networks with Tunable Clustering
- Universal computation by quantum walk
- Quantum walks of correlated particles
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- Random walks and diffusion on networks
- Link Prediction Based on Local Random Walk
- An example of the difference between quantum and classical random walks
- Strongly Correlated Quantum Walks in Optical Lattices
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
- Experimental Two-dimensional Quantum Walk on a Photonic Chip
- Progresses and Challenges in Link Prediction
- Efficient Quantum Walk on a Quantum Processor
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Efficient quantum circuits for continuous-time quantum walks on composite graphs