PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperbolic Geometry of Complex Networks

Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, Marian Boguna

arXiv:1006.5169v2cond-mat.stat-mechcond-mat.dis-nncs.NIphysics.soc-ph

TL;DR

The paper asks how complex-network topology and function can be explained geometrically. It develops a hyperbolic framework linking topology to geometry and statistical mechanics, then shows that geometry-guided transport is maximally efficient and robust in networks with strong heterogeneity and clustering.

  • Problem

    The paper addresses how heterogeneous degree distributions, clustering, and efficient network transport can arise from an underlying structure without global topology knowledge.

  • Method

    The paper models complex networks in hyperbolic space, maps node distances to edge energies in a statistical-mechanical ensemble, and uses the geometry to guide transport.

  • Results

    Strong heterogeneity and clustering emerge as geometric reflections, while geometry-guided transport achieves best-possible efficiency and remains robust under catastrophic network damage.

  • Takeaways & Limitations

    Hyperbolic geometry provides tools and an explanation for why hierarchical, strongly clustered complex networks support efficient decentralized routing.

Abstract

from arXiv · show

We develop a geometric framework to study the structure and function of complex networks. We assume that hyperbolic geometry underlies these networks, and we show that with this assumption, heterogeneous degree distributions and strong clustering in complex networks emerge naturally as simple reflections of the negative curvature and metric property of the underlying hyperbolic geometry. Conversely, we show that if a network has some metric structure, and if the network degree distribution is heterogeneous, then the network has an effective hyperbolic geometry underneath. We then establish a mapping between our geometric framework and statistical mechanics of complex networks. This mapping interprets edges in a network as non-interacting fermions whose energies are hyperbolic distances between nodes, while the auxiliary fields coupled to edges are linear functions of these energies or distances. The geometric network ensemble subsumes the standard configuration model and classical random graphs as two limiting cases with degenerate geometric structures. Finally, we show that targeted transport processes without global topology knowledge, made possible by our geometric framework, are maximally efficient, according to all efficiency measures, in networks with strongest heterogeneity and clustering, and that this efficiency is remarkably robust with respect to even catastrophic disturbances and damages to the network structure.

I. INTRODUCTION

The paper proposes hyperbolic geometry as a framework for explaining complex-network structure and function. Negative curvature and metric properties account for heterogeneous degrees, clustering, statistical-mechanical descriptions, and efficient, robust navigation.

  • Motivation and framework: Hyperbolic geometry is proposed as an underlying framework for studying the structure and function of complex networks.The framework treats hyperbolic spaces as smooth, continuous analogues of trees.
  • Network topology: Heterogeneous degree distributions and strong clustering emerge naturally from negative curvature and metric properties, respectively.The degree-distribution exponent depends on hyperbolic curvature.
  • Statistical mechanics: Hyperbolic distances between nodes are interpreted as edge energies in a statistical-mechanical network ensemble with Fermi-Dirac statistics.Temperature controls clustering, and auxiliary fields become linear functions of distances.
  • Statistical mechanics: The hot-regime limits of the ensemble include the configuration model and classical random graphs as networks with degenerate geometric structures.The phase transition separates cold and hot regimes.
  • Network function: Targeted transport guided by hyperbolic geometry achieves best-possible efficiency in strongly heterogeneous and clustered networks and remains robust under catastrophic damage.The processes require no global topology knowledge.
  • Hyperbolic geometry: Hyperbolic space expands exponentially with distance, unlike Euclidean space, and has metric structures equivalent to those of trees.This exponential expansion supplies space for branching hierarchical organization.

III. TOPOLOGICAL HETEROGENEITY VERSUS GEOMETRICAL HYPERBOLICITY

The paper connects approximate hierarchies and metric similarity among network nodes to hyperbolic geometry. A simple distance-threshold model then produces heterogeneous, power-law degree distributions without explicitly imposing them.

  • Topological motivation: Approximate taxonomies and dendrogram-like hierarchies suggest negative curvature because trees and hyperbolic spaces share the same metric structure.The hierarchy need not be strictly a tree.
  • Metric mapping: Overlapping attribute disks can be mapped to hyperbolic nodes so that bounded similarity distances correspond to bounded hyperbolic distances.The mapping and its converse hold under bounded radius ratios and center separations.
  • Model construction: Nodes are placed uniformly in a hyperbolic disk and connected only when their hyperbolic distance is at most R.The disk radius represents the depth of the hidden tree-like hierarchy.
  • Model construction: The average degree of a node is proportional to the intersection area between the node-containing disk and its connection disk.The intersection is computed using the hyperbolic law of cosines.
  • Degree control: R = 2 ln[8N/(π¯k)] sets the disk radius for an N-node network with target average degree ¯k, and R scales as ln N.The scaling matches the depth growth of a balanced tree.
  • Degree distribution: A power-law degree distribution emerges naturally because exponential radial node density combines with exponentially varying average degree.No separate mechanism is imposed to enforce the power law.

B. Quasi-uniform node density at arbitrary negative curvature

The generalized model allows arbitrary negative curvature and quasi-uniform radial densities. Degree heterogeneity depends on the normalized density-to-curvature ratio, while average-degree control becomes less accurate near α/ζ = 1/2.

  • Generalized model: The model generalizes the node density to an exponential profile with exponent α and the curvature to K = −ζ2.Uniform density is recovered only when α = ζ.
  • Average degree: For large R, r, and y, the angular integration boundary is approximated as θy = 2eζ(R−r−y)/2.This approximation is substituted into the average-degree integral.
  • Model boundary: Average-degree control becomes less accurate as α approaches ζ/2, and ξ is undefined at α/ζ = 1/2.Fixing R through Eq. (25) instead causes average degree to grow polylogarithmically with network size.
  • Degree distribution: The average degree ¯k(r) has radius scaling independent of α when α > ζ/2.The degree distribution is then derived using the same procedure as in the uniform-density case.
  • Degree distribution: The degree-distribution heterogeneity depends on α and ζ only through their ratio α/ζ.This ratio compares the expansion rate of the node hierarchy with the curvature-driven expansion of space.
  • Degree distribution: The model produces scale-free networks with γ = 2α/ζ + 1 ⩾2 when α/ζ ⩾1/2.Uniform density gives α = ζ and γ = 3.

V. HETEROGENEOUS TOPOLOGY IMPLIES HYPERBOLIC GEOMETRY

The paper shows that a heterogeneous network with metric structure can be rescaled into an effective hyperbolic geometry. An S1 model mapped to radial coordinates in H2 generates statistically equivalent network ensembles.

  • A scale-free network with metric structure can be naturally rescaled so its metric space becomes hyperbolic.
  • The S1 model places nodes uniformly on a circle, assigns power-law expected degrees, and connects pairs through an integrable distance-dependent probability.
  • The connection rule makes the realized average degree proportional to expected degree, preserving a power-law degree distribution with exponent γ.
  • The κ-to-r mapping converts the power-law degree variable κ into an exponentially distributed radial coordinate r, with α = ζ(γ −1)/2.
  • The mapped S1 and H2 models have approximately matching connection probabilities and identical average degrees as functions of radial position.
  • With appropriate parameters, the S1 and H2 models generate statistically equivalent network ensembles, supporting effective hyperbolic geometry for heterogeneous metric networks.

VI. HYPERBOLIC GEOMETRY VERSUS STATISTICAL MECHANICS

The paper relaxes the step-function connection rule and maps the resulting hyperbolic network ensemble to statistical mechanics. Hyperbolic distances become fermionic link energies, while temperature separates geometric network regimes.

  • The generalized model replaces the step-function connection rule with a family of probability functions parameterized by β > 0.
  • The geometric ensemble is identical to an exponential random-graph ensemble whose auxiliary link fields are linear functions of hyperbolic distances.
  • The connection probability is a Fermi-Dirac distribution, making hyperbolic distance x the energy of a fermionic link.
  • In the statistical-mechanics interpretation, R is the chemical potential, 2/ζ is the Boltzmann constant, and β = 1/T is inverse temperature.
  • For β > 1, the statistical-mechanical chemical potential and parameter ν reproduce the corresponding quantities obtained from geometric arguments.
  • At T = 0, the Fermi distribution becomes the geometric step function; at T = 1, a phase transition arises from divergence of the connection function.

VII. DEGREE DISTRIBUTION AT NON-ZERO TEMPERATURE

At non-zero temperature, the cold regime preserves the model’s power-law degree distribution, while the hot regime requires cutoff-dependent renormalization and changes the degree-scaling relationship.

  • Cold regime: The cold regime retains the same power-law degree distribution as at zero temperature, with γ > 2 determined by the H2 parameters.The average degree is k̄ = 2µIκ̄^2, and γ = 2α/ζ + 1.
  • Hot regime: In the hot regime, the connection-probability integral diverges and must be explicitly cut off at χ_max = N/(2µκκ′).The cutoff is required because the connection probability is nonintegrable in this regime.
  • Hot regime: χ_max^(1−β)/(1−β) is the leading large-χ_max term for β ∈ [0, 1), determining the hot-regime normalization.
  • Hot regime: In the hot regime, average degree scales with hidden variable κ as κ^β rather than proportionally to κ, so the generated degree exponent differs from the input exponent γ̃.
  • Parameter constraints: The hot regime permits γ̃ > β + 1 in S1 or α > βζ/2 in H2, with both conditions yielding γ > 2.

VIII. CLUSTERING AS A FUNCTION OF TEMPERATURE

Clustering decreases with temperature in the cold regime, is maximized at zero temperature, and vanishes in the thermodynamic limit throughout the hot regime.

  • Temperature dependence: Clustering decreases with temperature in the cold regime, reaching its maximum at T = 0 and approaching zero at T = 1.The decrease is described as gradual and almost linear.
  • Zero-temperature analysis: At zero temperature, the clustering integral becomes the intersection area of a square and a stripe in rescaled-distance coordinates.The inner integral is represented geometrically by this intersection.
  • Zero-temperature analysis: For small expected degree κ, the stripe nearly contains the square, giving c̄(κ₀) ≈ 1 and proving that clustering is maximized at zero temperature.Structural constraints prevent clustering from equaling 1 for all node degrees.
  • Degree dependence: For large expected degree, degree-dependent clustering decays as κ^−1, with a prefactor that decreases with the power-law exponent.
  • Hot regime: In the hot regime, temperature has no effect on clustering, which is zero for large networks because the thermodynamic-limit prefactor vanishes.

IX. CONNECTION TO THE CONFIGURATION MODEL AND CLASSICAL RANDOM GRAPHS

The model connects hyperbolic network ensembles to degenerate non-geometric limits: the configuration model and classical random graphs emerge when metric structure disappears.

  • Degenerate geometric limits: Sending T and ζ to infinity at fixed η = ζ/T removes the angular contribution to hyperbolic distance, making x_ij = r_i + r_j and degenerating the metric structure.
  • Classical random graphs: Alternatively, heating networks with finite α and ζ makes connection probability uniform, p(x) → p = k̄/N, independently of distance.
  • Classical random graphs: The resulting degree distribution is Poissonian, and the ensemble converges to classical random graphs G_N,p with average degree k̄ = pN.
  • Classical random graphs: In this limit, the network loses both its metric structure and its hierarchical heterogeneous organization.
  • Model flexibility: The model can generate scale-free networks with independently controlled average degree, power-law exponent γ > 2, and average clustering through its S1 and H2 parameters.

X. EFFICIENCY OF GREEDY NAVIGATION IN MODELED NETWORKS

The framework enables greedy navigation using hyperbolic coordinates rather than global topology knowledge, and evaluates its efficiency under static and damaged network conditions.

  • Navigation mechanism: Greedy forwarding uses node coordinates to send information to the neighbor closest to the destination in hyperbolic space.This avoids requiring global knowledge of network topology.
  • Navigation algorithms: Modified greedy forwarding avoids dropping packets at local minima by excluding the current node from distance comparisons and rejecting only immediate backtracking.Original greedy forwarding drops packets at local minima.
  • Navigation limitations: Greedy forwarding can fail at local minima, use paths much longer than shortest paths, and lose efficiency under network damage.
  • Efficiency measures: Navigation efficiency is assessed using successful-path percentage, average hop length, and average and maximum hop or hyperbolic stretch.

A. Static networks

In static networks, greedy forwarding is highly efficient, particularly when the degree distribution is strongly heterogeneous. For γ = 2.1, reachability is nearly complete and OGF paths are all shortest.

  • For γ = 2.1, OGF and MGF achieve success ratios of 99.92% and 99.99%, respectively.
  • For γ = 2.1, OGF has maximum stretch 1, meaning all greedy paths are shortest paths.
  • As γ decreases toward 2, success ratio increases while average path length and all stretches decrease.
  • GF is exceptionally efficient in static networks, with reachability near 100% and greedy paths generally optimal for small γ.

B. Dynamic networks

Greedy forwarding remains effective under network topology changes. In networks with small γ, it maintains high reachability and low stretch despite link failures, including catastrophic damage levels.

  • Scenario 2 evaluates paths that traversed a removed link and measures their continued success and new stretches after rerouting.
  • In Scenario 1, the new success ratio remains remarkably high for small γ across meaningful link-removal percentages.
  • For γ = 2.1 and pr ≤ 10%, MGF maintains a new success ratio above 99%.The passage characterizes simultaneous failure of 10% of links as a rare catastrophe for a network such as the Internet.
  • Average stretch increases slightly as pr increases but remains quite low.
  • In Scenario 2, average stretch remains below 1.1 and maximum stretch never exceeds 1.5.
  • Overall, GF retains high reachability and low stretch after catastrophic network damage, especially for γ values found in real networks such as the Internet.

C. Role of clustering

Clustering and degree heterogeneity are both important for navigability. GF performs best with strong clustering, but becomes ineffective in degenerate zero-clustering models.

  • At γ = 2.1, GF efficiency improves as temperature decreases and clustering strengthens, reaching best possible performance at zero temperature.
  • The configuration model and classical random graphs represent degenerate zero-clustering cases of the geometric network ensemble.
  • In the configuration model, GF success ratio never exceeds 40% and falls below 10% for large γ.
  • In classical random graphs, OGF and MGF average success ratios are 0.17% and 0.21%, respectively.
  • The results indicate that hierarchical organization through heterogeneous degree distribution and metric structure through strong clustering are both critically important for network navigability.

E. Why hierarchical structure and strong clustering ensure efficient navigation

Hierarchical organization and strong clustering align network paths with hyperbolic geodesics, enabling efficient greedy navigation without global topology knowledge. This structure also preserves navigability under severe network damage.

  • E. Why hierarchical structure and strong clustering ensure efficient navigation: Smaller γ and T increase congruency between network topology and hyperbolic geometry, making networks more navigable.Congruency is measured by hyperbolic stretch.
  • E. Why hierarchical structure and strong clustering ensure efficient navigation: Greedy paths follow a hierarchical pattern: moving from peripheral low-degree nodes toward the core, turning toward the destination, then descending to it.This pattern corresponds to increasing and then decreasing node degrees.
  • E. Why hierarchical structure and strong clustering ensure efficient navigation: Strong clustering supplies partially disjoint paths with the same hierarchical pattern, so alternative congruent routes remain after link failures.Greedy forwarding can continue using the same hyperbolic-geodesic direction.
  • E. Why hierarchical structure and strong clustering ensure efficient navigation: Stronger heterogeneity creates bridges that connect high-degree nodes across the network, allowing greedy forwarding to cross the network in one hop after reaching a bridge.Networks with γ > 3 have no bridges, and greedy-forwarding success deteriorates to zero in the thermodynamic limit.
  • E. Why hierarchical structure and strong clustering ensure efficient navigation: The framework links heterogeneity to negative curvature and clustering to metric structure, while showing that heterogeneous metric networks possess effective hyperbolic geometry.These geometric properties support navigability without global topology knowledge.
  • E. Why hierarchical structure and strong clustering ensure efficient navigation: Strongest clustering and heterogeneity produce optimal navigability according to all efficiency measures, with robustness to catastrophic network damage.The geometric underpinning makes routing efficiently possible through the right hyperbolic direction toward the destination.
Loading 1006.5169v2…