Quantum Link Prediction in Complex Networks

Predicting the existence of a link in a complex network is a non-trivial task, namely for large social and biological networks, with important applications. Experiments to map the full structure of biological networks (e.g. protein-protein interactions) are very challenging, costly and time consuming, and large amounts of data is still missing. Link prediction methods are not only a key computational tool to aid these efforts in understanding complex biological systems, but also very useful for other studies of time-varying complex networks, as for example social networks.

In this work we present a novel method for link prediction in complex networks based on continuous-time quantum walks. The control of a relative phase allows our method to be used in different types of networks (physical, biological, social, etc.). By exploiting quantum coherence we are able to outperform the state of the art classical methods, indicating that our method is also able to capture complex local patterns (such as local communities around paths of length 3) without the need to impose a specific pattern structure. Our results indicate there is a strong potential for combining quantum algorithms with complex network research to produce tools with direct and immediate experimental relevance.