ABSTRACT | Biological function emerges from the complex interplay between molecules in our cells, as well as social behavior from the interactions between individuals. Even against the best efforts, current large-scale maps of these systems are typically still missing the majority of the interactions. Answering this call, state-of-the-art network-based link prediction tools rely on the triadic closure principle, stating that nodes are likely to interact if they share many of their interaction partners, utilizing network paths of length l=2. We show that this principle is valid only for a small fraction of the nodes, while it fails completely for most of these networks. As a solution, we propose to identify missing interactions based on l=3 paths. Our top predictions for proteins validate as well experimentally as known protein-protein interactions, outperforming any existing technique several times. The same approach can also be applied to infer functional behavior in these systems in the augmented graph, where a function is represented by an additional "functional" node, leading to significantly improved predictions for protein annotations. On the contrary of traditional guilt-by-association techniques, our approach can identify functionally relevant nodes even if they have no partners involved in a given function. As a proof of concept, we study infection spreading in heterogeneous complex networks with and without long-range interactions by multiple numerical techniques and show that highly correlated nodes, which are infected at the same time, are typically not directly connected. Besides highlighting the profound roles of indirect connectivity, this finding has far-reaching implications in disease intervention strategies at both cellular and social scales.
BIO | István Kovács, Ph.D., is working on bridging the gap between structure and function in complex systems in the Barabasilab at Northeastern University, Boston. He is developing novel methodologies to predict the emerging structural and functional patterns in a broad spectrum of problems ranging from systems biology to quantum physics, in close collaboration with experimental groups.