Adaptive Network Automata Modelling of Complex Networks for Link Prediction

Many complex networks have a connectivity that might be only partially detected or that tends to grow over time, hence the prediction of non-observed links is a fundamental problem in network science. The aim of topological link prediction is to forecast these non-observed links by only exploiting features intrinsic to the network topology. It has a wide range of real applications, like suggesting friendships in social networks or predicting interactions in biological networks. The Cannistraci-Hebb theory is a recent achievement in network science that includes a theoretical framework to understand local-based link prediction on paths of length n. In this study we introduce two innovations: one on the theory of modelling (science) and the other on the theory of realization (engineering). For the theory of modelling we first recall a definition of network automata as a general framework for modelling the growth of connectivity in complex networks. We then show that several deterministic models previously developed fall within this framework and we introduce novel network automata following the Cannistraci-Hebb rule. For the theory of realization, we present how to build adaptive network automaton for link prediction, which incorporate multiple deterministic models of self-organization and automatically learns the rule that better explains the patterns of connectivity in the network under investigation. We compare the Cannistraci-Hebb Adaptive (CHA) network automaton against state-of-the-art link prediction methods, including structural perturbation method (SPM), stochastic block models (SBM), and artificial intelligence algorithms for graph representation learning, such as graph embedding methods and message-passing-based models. In particular, we compare the Message Passing Link Predictor (MPLP), a state-of-the-art link prediction method that differs from general-purpose graph embedding methods by approximating heuristic scores such as Common Neighbor through quasi-orthogonal message-passing. We also compare with MPLP+, a scalable variant that avoids costly preprocessing by leveraging only one-hop neighborhoods. CHA displays an overall higher link prediction performance across different evaluation frameworks on 1269 networks across 14 complex systems domains. Finally, we highlight that CHA offers the key advantage to explicitly explain the mechanistic rule of self-organization which leads to the link prediction performance, whereas SPM, SBM, and AI-based methods like graph embeddings and MPLP do not. In comparison to CHA, SBM unfortunately shows irrelevant and unsatisfactory performance demonstrating that SBM modelling is not adequate for link prediction in real networks.