Quantum Link Prediction in Complex Networks

Link prediction in complex networks consists in finding which pairs of nodes are likely to be connected, taking advantage of the information encoded in the topology of each network. Complex networks describe many physical,... [ view full abstract ]

Link prediction in complex networks consists in finding which pairs of nodes are likely to be connected, taking advantage of the information encoded in the topology of each network. Complex networks describe many physical, biological, social and information systems, giving the problem of link prediction multidisciplinary implications. Research so far has been focused on the application to social and biological networks. 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 [1]. 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.

Most link prediction methods developed so far are based on the Triadic Closure Principle (TCP), which assumes that two nodes are more likely to be connected if they have many direct connections in common. Recently it has been shown that, despite its dominant use in biological networks, the TCP idea is not valid for most protein pairs [2]. Instead, the authors propose a link prediction method based around paths of length three (L3), which they argue is a better representation of the topological patterns that emerge in protein networks. The results show the L3 method significantly outperforms other link prediction methods found in the literature. A follow up study by a different group [3] showed that the L3 method can be further improved by considering a local community paradigm around each path of length three (CH-L3 method).

In this work we present a novel method for link prediction on 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 (see Fig. 1), indicating that our method is also able to capture complex local patterns (such as local communities around paths of length three) 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.

[1] T. Rolland et al., Cell 159, 1212 (2014).

[2] I. Kovács et al., bioRxiv https://doi.org/10.1101/275529 (2018).

[3] A. Muscoloni et al., bioRxiv https://doi.org/10.1101/346916 (2018).