  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.
