Statistical complexity of heterogeneous geometric networks

Keith Malcolm Smith*, Jason P. Smith

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Article numbere0000026
Number of pages22
JournalPLOS Complex Systems
Volume2
Issue number1
DOIs
Publication statusPublished - 3 Jan 2025

Keywords

  • statistical complexity
  • latent geometry
  • real-world networks
  • degree heterogeneity

Fingerprint

Dive into the research topics of 'Statistical complexity of heterogeneous geometric networks'. Together they form a unique fingerprint.

Cite this