Source-linked AI summary
Emergent Complex Network Geometry
Zhihao Wu, Giulia Menichetti, Christoph Rahmede, Ginestra Bianconi
TL;DR
The paper asks whether network geometry can emerge from dynamics rather than a prescribed embedding. It proposes a two-parameter growing network model and reports emergent geometric properties in the model and a variety of real networks.
Problem
The paper asks whether a hidden metric space drives network dynamics or can instead emerge from network evolution.
Source: INTRODUCTION · p. 3Method
The authors grow simplicial complexes by gluing triangles under two dynamical parameters, without using an embedding space, and compare the resulting networks with real datasets.
Source: INTRODUCTION · p. 3Results
The model develops locality, small-world properties, non-trivial community structure, and finite spectral dimensions without an embedding space; real datasets also show non-trivial curvature distributions and finite effective spectral dimensions.
Source: RESULTS · p. 13, DISCUSSION · p. 14Takeaways & Limitations
The stylized model may be useful in fields involving networks with clustering, including biological, social, and technological systems.
Source: DISCUSSION · p. 15Determining the underlying metric of these networks remains an open question.
Source: DISCUSSION · p. 14
Abstract
from arXiv · showhide
Networks are mathematical structures that are universally used to describe a large variety of complex systems such as the brain or the Internet. Characterizing the geometrical properties of these networks has become increasingly relevant for routing problems, inference and data mining. In real growing networks, topological, structural and geometrical properties emerge spontaneously from their dynamical rules. Nevertheless we still miss a model in which networks develop an emergent complex geometry. Here we show that a single two parameter network model, the growing geometrical network, can generate complex network geometries with non-trivial distribution of curvatures, combining exponential growth and small-world properties with finite spectral dimensionality. In one limit, the non-equilibrium dynamical rules of these networks can generate scale-free networks with clustering and communities, in another limit planar random geometries with non-trivial modularity. Finally we find that these properties of the geometrical growing networks are present in a large set of real networks describing biological, social and technological systems.
INTRODUCTION
The paper presents a two-parameter, embedding-independent growing network model in which geometry emerges from network dynamics, and examines its structural and spectral properties. It also assesses how those properties align with biological, social, and technological network datasets as a basis for modeling real networks.
RESULTS
- The two-parameter growing geometrical network produces emergent heterogeneous geometry, including small-world structure, modularity, and finite spectral dimension across distinct planar and scale-free regimes.The authors also report that this stylized model captures main features of a large variety of real-network datasets.Source: INTRODUCTION · pp. 2–3, RESULTS · pp. 6, 10, 13
INTRODUCTION
- Rather than assuming hidden space drives links, the model starts with embedding-independent triangle growth; m caps triangles per link, while p allows distance-two nodes to be linked.The resulting network is the skeleton of a growing simplicial complex.Source: INTRODUCTION · p. 3, RESULTS · pp. 4–5
- The introduction frames the study around whether hidden geometry causes network dynamics or instead emerges from them, and proposes a model that captures features found in many real datasets.The motivating applications of network geometry include routing, data mining, and community detection.Source: INTRODUCTION · pp. 2–4
RESULTS
- For m = ∞ and p = 0, preferential attachment yields a scale-free network with γ = 3; for m = 2, the degree distribution is exponential.The graphs are planar for m = 2 at any p, or for p = 0 at any m.Source: RESULTS · pp. 6–7
- Curvature is heterogeneous rather than constant: for p = 0 its mean is zero, with an unbounded negative tail that is exponential at m = 2 and power-law at m = ∞.For m = 2 or p = 0, the Euler characteristic is χ = 1; for m = ∞ and p = 0, curvature fluctuations have infinite second moment.Source: RESULTS · pp. 11–12
- Despite exponential network growth, average distance from the initial triangle scales as D ∝ log N independently of m and p, while the spectral dimension remains finite.The combination of high clustering and logarithmically growing distances gives the networks small-world topology.Source: RESULTS · pp. 12–13
- For p > 0 the networks develop a non-trivial K-core and community structure; for p = 0, the maximal K-core has K = 2.Across the parameter range, the model also has finite average clustering.Source: RESULTS · pp. 10, 13
- Real biological, social, and technological networks show large modularity and clustering, small average distance, non-trivial maximal K-core structure, and curvature distributions with positive or negative tails.Their Laplacian spectra also display power-law tails from which an effective finite spectral dimension can be calculated.Source: RESULTS · p. 13
- The geometrical growing network models share many properties with these real datasets and should be used and modified to model several real networks.Source: RESULTS · p. 14
DISCUSSION
Growing simplicial complexes can spontaneously develop locality and spatial properties, including small-world structure, communities, and finite spectral dimensions. The underlying metric remains an open question, while higher-dimensional and finite-Hausdorff-dimension extensions are proposed directions.
DISCUSSION
- The model’s non-equilibrium stochastic dynamics produce locality and spatial properties, including small-world structure, non-trivial communities, and finite spectral dimensions.The conclusion presents this as evidence that simple stochastic rules can generate random self-organized geometries.Source: DISCUSSION · p. 14
- Determining the networks’ underlying metric remains open, including whether models with m = 2 and p = 0 have a hyperbolic character.These models have zero average curvature but a negative third moment of the curvature distribution.Source: DISCUSSION · p. 14
- Proposed extensions include gluing higher-dimensional simplices, exploring finite Hausdorff dimension, and studying equilibrium network ensembles with constrained triangle incidence.Finite Hausdorff dimension is described as typical distance scaling like a power of network size.Source: DISCUSSION · p. 14
- The authors describe the model as stylized but potentially useful for complex networks with clustering, including biological, social, and technological networks.Table I covers structural properties of real datasets; the listed measures include size, links, average distance, clustering, modularity, maximal K-core, and spectral dimension.Source: DISCUSSION · p. 15, Table I · p. 15
- Figure 7 plots curvature distributions P(R) for a variety of real datasets.The supplied caption does not state a comparative outcome.Source: Figure 7 · p. 16
Degree distribution of m = ∞and p = 0-
For m = ∞ and p = 0, the network’s degree distribution is scale-free with exponent 3. The derivation uses the growth rule in which each step attaches a new node to both ends of a randomly selected link.
Degree distribution of m = ∞ and p = 0
- At each step, a randomly chosen link receives a new node attached to both of its endpoints.The probability that a new link attaches to a node of degree k is k/(2t).Source: Degree distribution of m = ∞and p = 0- · p. 16
- The degree-distribution derivation uses the large-time scaling N(k, t) ≃ tP(k), with total node count N ≃ t.The resulting curvature has mean ⟨R⟩ = 0, while ⟨R2⟩ diverges with network size.Source: Degree distribution of m = ∞and p = 0- · pp. 16–17
- For m = ∞ and p = 0, the degree distribution is scale-free with power-law exponent γ = 3.The node curvature has a power-law negative tail, P(R) ≃ |R|^-3 for R < 0 and |R| ≫ 1.Source: Degree distribution of m = ∞and p = 0- · p. 17
Degree distribution of m = 2 for p = 0-
For m = 2, the degree distribution is exponential for any p; the p = 0 case also has zero average curvature and finite second curvature moment.
Degree distribution of m = 2 for p = 0
- For m = 2, the degree distribution is exponential for any value of p.The passage develops the p = 0 case and leaves p > 0 to the Supplementary Information.Source: Degree distribution of m = 2 for p = 0- · p. 17
- When p = 0, each node has exactly two unsaturated links, and the total number of unsaturated links grows as L ≃ t.At large t, a node gains an average of 2/t links through process (a).Source: Degree distribution of m = 2 for p = 0- · p. 17
- For p = 0, curvature R = 1 − k/4 has mean ⟨R⟩ = 0 and finite second moment as t → ∞.Source: Degree distribution of m = 2 for p = 0- · p. 17
Euler characteristic χ of geometrical growing network with either m = 2 or p = 0-
With p = 0, the Euler characteristic remains χ = 1 as the network grows. For m > 2 and p > 0, it instead grows linearly with network size.
Euler characteristic χ of geometrical growing network with either m = 2 or p = 0
- For p = 0, the Euler characteristic χ remains 1 at every network size.The process starts from one triangle and each step adds one node, two links, and one triangle, leaving Δχ = 0.Source: Euler characteristic χ of geometrical… · p. 17
- For m = 2, process (b) also leaves χ unchanged because it adds one link and one triangle.Source: Euler characteristic χ of geometrical… · p. 17
- For m > 2 and p > 0, process (b) makes χ grow linearly with network size because it closes, on average, more than one triangle.Source: Euler characteristic χ of geometrical… · p. 18
Definition of Modularity M-
Modularity M evaluates the significance of a network’s community structure. Its optimization is NP-hard, so the study uses a greedy method whose result is a lower bound on maximal modularity.
Definition of Modularity M-
- Modularity M measures the significance of a network’s community structure.The passage introduces its definition but does not provide the formula.Source: Definition of Modularity M- · p. 18
- The modularity definition uses the adjacency matrix a, the total number of links L, and q_i to indicate each node’s community.Finding the partition that optimizes modularity is NP-hard.Source: Definition of Modularity M- · p. 18
- The study uses the Leuven method to find communities, and its modularity value is a lower bound on the network’s maximal modularity.Source: Definition of Modularity M- · p. 18
Definition of the Clustering coefficient-
The clustering coefficient describes how often two nodes connected to a common node are connected to each other. Locally, it is defined for a node using its triangles and degree.
Definition of the Clustering coefficient-
- The clustering coefficient is the probability that two nodes connected to a common node are also connected to each other.In social networks, this corresponds to the probability that a friend of a friend is also your friend.Source: Definition of the Clustering… · p. 18
- For node i, the local clustering coefficient C_i is defined as the probability that two of its neighbours are neighbours of each other.Source: Definition of the Clustering… · p. 18
- The local definition uses t_i, the number of triangles through node i, and k_i, its degree.Source: Definition of the Clustering… · p. 18
Definition of the K-core-
A network’s K-core is its maximal subgraph in which every included node has at least K links to other nodes in that subgraph. It can be obtained by iterative pruning.
Definition of the K-core-
- The K-core is the maximal subgraph whose nodes each have at least K links to other nodes in the K-core.Source: Definition of the K-core- · p. 19
- The K-core can be obtained by repeatedly removing nodes whose degree k_i is less than K.Source: Definition of the K-core- · p. 19
Definition of the spectral dimension of a network-
The spectral dimension d_S is defined through the small-eigenvalue scaling of the Laplacian’s eigenvalue density. The passage also relates it to cumulative eigenvalue scaling and notes that it matches dimension for regular lattices.
Definition of the spectral dimension of a network-
- For small λ, if the Laplacian eigenvalue density g(λ) scales with d_S > 0, that exponent is called the network’s spectral dimension.Source: Definition of the spectral dimension… · p. 19
- For regular lattices in dimension d, the spectral dimension satisfies d_S = d.Source: Definition of the spectral dimension… · p. 19
- When the spectral dimension is well defined, the cumulative distribution P_c(λ) also scales for small λ.The supplied passage does not state the scaling formula.Source: Definition of the spectral dimension… · p. 19
Real datasets
The authors analyzed biological, technological, and social datasets, including brain, protein, Internet, power-grid, and student friendship networks. The author contribution statement assigns research design, coding, figure preparation, and manuscript writing across the team.
Real datasets
- The dataset analysis spans biological, technological, and social networks, including brain co-activation, four protein contact maps, the Internet, the US power grid, and high-school friendships.The friendship network comes from the Add Health dataset.Source: Real datasets · p. 19
- The analyzed examples include a brain co-activation network, four protein contact maps, and the Internet at the Autonomous System level.Source: Real datasets · p. 19
Author contribution statement
- Research design and main manuscript writing were shared by C. R. and G. B.; Z. W., G. M., and G. B. wrote the code.Z. W. and G. M. prepared figures, and all authors reviewed the manuscript.Source: Author contribution statement · p. 24