Statistical complexity of heterogeneous geometric networks

Smith, Keith Malcolm and Smith, Jason P. (2024) Statistical complexity of heterogeneous geometric networks. PLOS Complex Systems. ISSN 2837-8830 (In Press)

[thumbnail of Smith-Smith-PLOS-CS-2024-Statistical-complexity-of-heterogeneous-geometric-networks] Text. Filename: Smith-Smith-PLOS-CS-2024-Statistical-complexity-of-heterogeneous-geometric-networks.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 January 2099.
Download (1MB) | Request a copy

Abstract

Degree heterogeneity and latent geometry, also referred to as popularity and similarity, are key explanatory components underlying the structure of real-world networks. The relationship between these components and the statistical complexity of networks is not well understood. We introduce a parsimonious normalised measure of statistical complexity for networks. The measure is trivially 0 in regular graphs and we prove that this measure tends to 0 in Erdös-Rényi random graphs in the thermodynamic limit. We go on to demonstrate that greater complexity arises from the combination of heterogeneous and geometric components to the network structure than either on their own. Further, the levels of complexity achieved are similar to those found in many real-world networks. However, we also find that real-world networks establish connections in a way which increases complexity and which our null models fail to explain. We study this using ten link growth mechanisms and find that only one mechanism successfully and consistently replicates this phenomenon -- probabilities proportional to the exponential of the number of common neighbours between two nodes. Common neighbours is a mechanism which implicitly accounts for degree heterogeneity and latent geometry. This explains how a simple mechanism facilitates the growth of statistical complexity in real-world networks.

ORCID iDs

Smith, Keith Malcolm ORCID logoORCID: https://orcid.org/0000-0002-4615-9020 and Smith, Jason P.;
CORE (COnnecting REpositories)