Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction

Abstract

Topological link-prediction can exploit the entire network topology (global methods) or only the neighbourhood (local methods) of the link to predict. Global methods are believed the best. Is this common belief well-founded? Stochastic-Block-Model (SBM) is a global method believed as one of the best link-predictors, therefore it is considered a reference for comparison. But, our results suggest that SBM, whose computational time is high, cannot in general overcome the Cannistraci-Hebb (CH) network automaton model that is a simple local-learning-rule of topological self-organization proved as the current best local-based and parameter-free deterministic rule for link-prediction. To elucidate the reasons of this unexpected result, we formally introduce the notion of local-ring network automata models and their relation with the nature of common-neighbours' definition in complex network theory. After extensive tests, we recommend Structural-Perturbation-Method (SPM) as the new best global method baseline. However, even SPM overall does not outperform CH and in several evaluation frameworks we astonishingly found the opposite. In particular, CH was the best predictor for synthetic networks generated by the Popularity-Similarity-Optimization (PSO) model, and its performance in PSO networks with community structure was even better than using the original internode-hyperbolic-distance as link-predictor. Interestingly, when tested on non-hyperbolic synthetic networks the performance of CH significantly dropped down indicating that this rule of network self-organization could be strongly associated to the rise of hyperbolic geometry in complex networks. The superiority of global methods seems a "misleading belief" caused by a latent geometry bias of the few small networks used as benchmark in previous studies. We propose to found a latent geometry theory of link-prediction in complex networks.

References in corpus (13)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Predicting Missing Links via Local Information
• Hyperbolic Geometry of Complex Networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• Missing and spurious interactions and the reconstruction of complex networks
• Navigability of Complex Networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Curvature and temperature of complex networks
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Consistencies and inconsistencies between model selection and link prediction in networks
• The Link Prediction Problem in Bipartite Networks

Cited by in corpus (4)

• Network Geometry
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay