PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiscale unfolding of real networks by geometric renormalization

Guillermo García-Pérez, Marián Boguñá, M. Ángeles Serrano

arXiv:1706.00394v1cond-mat.dis-nncond-mat.stat-mechphysics.soc-ph

TL;DR

Multiple scales in complex networks are difficult to disentangle because small-world structure makes geometric length scaling challenging to define. The paper uses geometric renormalization of embedded networks to examine their structure across scales, finding self-similarity in real scale-free networks. This multiscale view offers a way to study network organization across scales and motivates further applications.

  • Problem

    Coexisting scales in complex networks are difficult to define and study because small-world structure entangles them and topology alone lacks a suitable geometric length-scale transformation.

    Source: §I · p. 1

  • Method

    The geometric renormalization group coarse-grains nodes in an embedded network into supernodes, recursively producing layers at progressively larger length scales.

    Source: §I · p. 1, §II · pp. 1–2

  • Results

    Real-world scale-free networks show self-similarity under geometric renormalization, while their flow progressively selects longer-range connections in keeping with their small-worldness.

    Source: §III · p. 4, §V · p. 7

  • Takeaways & Limitations

    The method offers a tool for examining global network organization across scales and may support applications such as multiscale community detection and finite-size scaling.

    Source: §V · p. 7

    The geometric scaling result applies to real networks insofar as they admit a good embedding in the underlying metric space.

    Source: §III · p. 4

Abstract

from arXiv · show

Multiple scales coexist in complex networks. However, the small world property makes them strongly entangled. This turns the elucidation of length scales and symmetries a defiant challenge. Here, we define a geometric renormalization group for complex networks and use the technique to investigate networks as viewed at different scales. We find that real networks embedded in a hidden metric space show geometric scaling, in agreement with the renormalizability of the underlying geometric model. This allows us to unfold real scale-free networks in a self-similar multilayer shell which unveils the coexisting scales and their interplay. The multiscale unfolding offers a basis for a new approach to explore critical phenomena and universality in complex networks, and affords us immediate practical applications, like high-fidelity smaller-scale replicas of large networks and a multiscale navigation protocol in hyperbolic space which boosts the success of single-layer versions.

I. INTRODUCTION

Complex networks contain coexisting scales, but their small-world structure and the lack of a suitable geometric length transformation have made scale-invariance difficult to establish. The paper introduces a geometric renormalization group to examine networks across scales.

I. INTRODUCTION

  • The broader motivation is that scale invariance links geometric self-similarity with phenomena such as system dynamics near critical points.The introduction describes symmetry as invariance under transformation, corresponding to similarity across parts of a system or across scales.Source: §I · p. 1
  • Small-world and ultrasmall-world path lengths make shortest-path scaling factors poor, leaving the definition of network self-similarity and scale-invariance controversial.Earlier topological approaches found some self-similarity, but scaling beyond degree distribution and maximum and average degrees was not observed.Source: §I · p. 1
  • Hidden metric-space models provide a geometric basis for defining self-similarity and scale-invariance and studying the scales in real-network connectivity.Their connectivity law combines node popularity and similarity, giving the network a range of distance scales [14, 16, 17].Source: §I · p. 1
  • The paper introduces a geometric renormalization group (RGN) that embeds networks and coarse-grains neighboring nodes into supernodes to select longer-range connections at successive scales.The approach is inspired by Kadanoff's block-spin renormalization group.Source: §I · p. 1

II. EVIDENCE OF GEOMETRIC SCALING IN REAL NETWORKS

The section defines a geometric coarse-graining procedure for embedded networks and applies it to real scale-free networks. Across renormalized layers, topological features show self-similarity, and community structure remains useful for finding high-modularity partitions of the original networks.

II. EVIDENCE OF GEOMETRIC SCALING IN REAL NETWORKS

  • The RGN operator acts on an embedded map containing network topology and geometry, grouping consecutive angular nodes into supernodes while preserving their order.Supernodes are linked when any node in one block was linked to any node in the other; the transformation raises the minimum length scale and can be iterated.Source: §II · pp. 1–2, Figure 1 · p. 2
  • The study applies RGN to six real scale-free networks from technology, transportation, biology, and scripts, using S1 embeddings and blocks of size r = 2.The process halves the system at each step; finite networks permit O(log N) iterations.Source: §II · p. 2
  • Degree distributions, degree-degree correlations, and clustering spectra show self-similar behavior, with curves collapsing across layers when degrees are rescaled by their average.Figure 2 presents the RGN flow for Internet AS, Human Metabolic, and Music networks; its top panels show complementary cumulative distributions of rescaled degrees.Source: §II · pp. 2–3, Figure 2 · p. 3
  • Community structure is preserved along the RGN flow, allowing high-modularity partitions of the original network to be found from much smaller versions.The section compares layer modularity, the induced partition's modularity on the original network, and normalized mutual information with the original partition.Source: §II · pp. 2–3

III. GEOMETRIC RENORMALIZATION OF THE S1 MODEL

The S1 model’s geometric renormalization preserves congruence with its hidden metric space, explaining self-similar scaling in suitably embedded real scale-free networks. The flow’s degree behavior depends on the model’s connectivity exponents.

III. GEOMETRIC RENORMALIZATION OF THE S1 MODEL

  • Renormalized connection probabilities retain the S1 model’s original form, keeping model and well-embedded real networks congruent with the hidden metric space.The geometric-layout transformation also has an abelian semigroup structure.Source: §III · p. 4
  • The hidden-degree distribution remains asymptotically power-law with the same exponent when (γ −1)/2 < β; β stays fixed, while angular ordering preserves community structure.The unchanged β explains the self-similarity of clustering spectra.Source: §III · p. 4
  • For γ < 3 or β < 2, the flow approaches a highly connected graph; at γ = 3 and β ≥2 or β = 2 and γ ≥3, average degree is preserved; for γ > 3 and β > 2, it approaches a ring.In the latter case, renormalized layers eventually lose the small-world property.Source: §III · p. 4
  • The phase diagram separates γ- and β-dominated regimes; real networks shown lie in the fully connected fixed-point region, and all but Internet and Airports are β-dominated.Their average degree grows exponentially along the flow, as predicted.Source: Figure 3 · p. 4, §III · pp. 4–5

IV. APPLICATIONS

The RGN unfolds scale-free networks into a self-similar multilayer shell, exposing coexisting scales and their interplay. This structure motivates both single-scale and multiscale applications.

IV. APPLICATIONS

  • The RGN unfolds scale-free complex networks into a self-similar multilayer shell that reveals coexisting scales and their interplay.Source: §IV · p. 5
  • The paper presents practical applications alongside the theoretical implication that self-similarity under RGN appears to be ubiquitous in real networks.Source: §IV · p. 5
  • The applications include one that selects a specific scale and another that exploits multiple scales simultaneously.Source: §IV · p. 5

A. Mini-me network replicas

Mini-me replicas provide reduced versions of large networks, with density adjusted after renormalization. Across three dynamics and three real networks, their behavior closely matches that of the originals.

A. Mini-me network replicas

  • Mini-me replicas can serve as reduced testbeds for routing protocols and support finite-size scaling of critical phenomena from a single-size network.They can be produced at any scale within the range where self-similarity is preserved.Source: A. Mini-me network replicas · p. 5
  • Renormalized networks can become denser, so link pruning readjusts μ to match the original network’s expected average degree.Only links consistent with the adjusted S1 connection probability are retained, yielding a statistically equivalent reduced network to a very good approximation.Source: A. Mini-me network replicas · p. 5
  • Across Ising, SIS, and Kuramoto dynamics on three real networks, Mini-me replicas show very similar results to the original networks at all tested scales.The dynamics are sensitive to mesoscale structure, supporting preservation of micro- and mesoscales in the replicas.Source: A. Mini-me network replicas · p. 5

B. Multiscale navigation

The multiscale navigation protocol uses geometric representations of network layers to improve greedy routing. Adding layers raises success rates while only mildly increasing successful-path stretch, at the cost of supernode information.

B. Multiscale navigation

  • The protocol uses the S1–H2 quasi-isomorphism to represent the multiscale shell geometrically in hyperbolic space, where connection probability decreases with hyperbolic distance.Source: B. Multiscale navigation · p. 5
  • Greedy routing uses the neighbor closest to the destination in metric space, while multiscale routing selects a next supernode at a coarse layer and forwards through the real network.When single-layer greedy routing gets trapped, coarse layers can provide alternative paths; blocks of connected consecutive nodes are restricted to one or two nodes.Source: B. Multiscale navigation · p. 6
  • Adding navigation layers increases success rates while only mildly changing successful-path stretch; one or two layers already have a notable effect in many systems.The tradeoff is additional information about supernodes compared with single-layer greedy routing.Source: B. Multiscale navigation · p. 6

V. DISCUSSION

Hidden metric spaces provide a geometric basis for examining how network structure changes across scales. Geometric renormalization reveals self-similarity in real scale-free networks and suggests scientific and practical uses for multiscale views.

V. DISCUSSION

  • The multiscale navigation figure compares success rate across layer counts and path stretch against shortest paths and a single-layer baseline.Its illustration contrasts an unsuccessful original-layer greedy route with a successful route using both layers.Source: Figure 5 · p. 7
  • Hidden metric-space congruency explains why real scale-free networks with good embeddings display self-similar scaling under geometric renormalization.The authors describe this as evidence in favour of hidden metric spaces underlying real networks.Source: §V · p. 7
  • Unlike topological renormalization, geometric renormalization orders boxes by the embedding and preserves mesoscopic structure across observation scales.Without an underlying model, topological renormalization does not make it obvious in advance when self-similarity will appear or whether mesoscopic structure will be maintained.Source: §V · p. 7
  • The authors propose using geometric renormalization to study metapopulation models with local and global movement, and to develop community detection from multiscale information.They also envision downscaled networks for finite-size scaling to determine critical exponents, which they say current methods cannot do.Source: §V · p. 7

1. Real networks data

The section describes the real-network datasets and procedures used to embed, renormalize, and analyze networks across layers. It also outlines the models and simulations used to study network structure, dynamics, and navigation.

1. Real networks data

  • The datasets cover the Internet, airports, human metabolism, the human interactome, music-chord transitions, and word adjacency in Darwin’s On the Origin of Species.The airport, music, and word networks are made undirected by retaining bidirectional edges; music links are first filtered for sparsity.Source: §1 · p. 8
  • Only the largest connected component of each network is retained for analysis.Source: §1 · p. 8

2. S1 model and transformation to H2

  • The S1 model embeds nodes on a circle, with connection probability governed by hidden degrees and angular distance, and is isomorphic to the H2 model.The hidden degrees are proportional to node degrees; the H2 representation uses radial coordinates and hyperbolic distance.Source: §2 · p. 8

3. Adjusting the average degree of Mini-me network replicas

  • To restore the original average degree in renormalized replicas, the procedure lowers the model parameter and prunes links, correcting for finite-size effects.The correction factor is adjusted until the difference in average degree is below 0.1.Source: §3 · p. 9

4. Simulation of dynamical processes

  • The dynamical simulations cover Ising spins, SIS epidemic spreading, and Kuramoto oscillators, with statistics collected over 100 realizations.The methods use Metropolis-Hastings, Gillespie, and Heun integration, respectively.Source: §4 · pp. 9–10

5. Multiscale navigation

  • Multiscale navigation routes greedily at the highest layer where source and destination differ, then uses gateways to descend toward the destination.Each node is assumed to know destination coordinates across layers and information about its supernodes and gateways.Source: §5 · p. 10

Appendix B: Evidence of geometric scaling in real networks

The appendices examine real-network behavior across renormalized layers and develop the geometric renormalization group’s mathematical and statistical-mechanical foundations, including average-degree flows and links between local parameters and global spectral properties. They also describe diffusion-time and synchronization-stability patterns similar to Fig. 3B for networks with N = 1000 and average degree ⟨κ⟩ = 5.

Appendix B: Evidence of geometric scaling in real networks

  • Appendix B compares renormalized topological features for Airports, Proteome, and Words, and empirical connection probabilities for six real networks and their renormalized versions.The features include rescaled-degree distributions, clustering, and community structure; the connection-probability plots also show the theoretical curve.Source: Appendix B · pp. 11–12, Figure 6 · p. 11, Figure 7 · p. 12

1. The semigroup structure of the coarse-graining step

  • Coarse-graining has a semigroup structure: applying factors r1 and r2 successively maps nodes to the same supernodes and yields the same final link structure as applying r1r2 once.The mapping follows from equality of the resulting supernode indices.Source: §1 · p. 12

2. Selecting long-range connections

  • Renormalized networks retain long-range connections from the original graph because links spanning larger angular distances require larger r to be integrated into supernodes.The comparison averages normalized angular distance over links not integrated within a supernode.Source: §2 · p. 13, Figure 8 · p. 13

3. Geometric renormalization of the S1 model

  • For the S1 model, the RG derivation assumes equal-sized supernodes for simplicity, while remaining valid for unequal sizes; mass transformations preserve the semigroup structure and angles use a generalized center of mass.The generalized center of mass is introduced to make angle transformations preserve that structure as well.Source: §3 · pp. 13–14

Particular case r = 2

  • For r = 2, the average-degree scaling exponent ν is solved exactly as a function of β and γ, and agrees with the power-law approximation for large β or γ.The exponent is defined by ⟨k′⟩ = r^ν⟨k⟩.Source: Particular case r = 2 · p. 17, Figure 9 · p. 18

Solution in the power-law approximation

  • Under the power-law approximation, the network flows to a fully connected graph if γ < 3 or β < 2, to ⟨k⟩→0 if γ > 3 and β > 2, with an unstable fixed point on the stated boundary.This conclusion assumes the power-law approximation; the authors expect it to describe the flow well as r → ∞. For γ < 2β + 1, the renormalized mass distribution remains power-law distributed.Source: §4 · p. 15, Solution in the power-law approximation · pp. 18–19

5. Mapping to hyperbolic space and the partition function

  • In the H2 model, each node pair represents a fermionic state with energy xmn/2 in the grandcanonical ensemble, and the network likelihood is the corresponding microstate probability.The appendix writes the system’s partition function and rearranges it according to the renormalization into supernodes.Source: §5 · p. 20

6. Local vs. global properties

  • RG analysis assesses how stable global network properties are to perturbations of local degree heterogeneity and clustering, using adjacency- and Laplacian-spectrum comparisons.For the synthetic networks shown, the spectra depend on γ only in the top-left phase-diagram region and are independent of γ in the bottom-right region.Source: §6 · p. 21, Figure 10 · p. 22, Figure 11 · p. 23
  • Diffusion time and the synchronization-stability measure λn/λ2 show similarities with Fig. 3B across 100 realizations of networks with N = 1000 and ⟨κ⟩ = 5.Diffusion time is the inverse of algebraic connectivity λ2; λn/λ2 is related to the time required to recover synchronization after a perturbation.Source: Figure 12 · p. 23

Appendix D: Mini-me network replicas

Figure 13 compares three dynamical processes on smaller-scale Mini-me replicas and the original Airports, Proteome, and Words networks. Across all three processes, replica curves are extremely similar to the original-network results.

Appendix D: Mini-me network replicas

  • Smaller-scale Mini-me replicas produce curves extremely similar to the original networks across the Ising, SIS, and Kuramoto processes.Results are averaged over 100 simulations, with error bars showing order-parameter fluctuations.Source: Figure 13 · p. 24
  • The columns show results for Airports, Proteome, and Words networks, with r = 2 making each layer 2^l times smaller than the original.Source: Figure 13 · p. 24
  • The rows track Ising magnetization against inverse temperature, SIS prevalence against infection rate, and Kuramoto coherence against coupling strength.Source: Figure 13 · p. 24

Appendix E: Multiscale navigation networks

The navigation coarse-graining preserves congruency with the underlying metric space even when block sizes differ. The appendix also presents degree distributions, clustering spectra, and empirical connection probabilities for the coarse-grained networks.

Appendix E: Multiscale navigation networks

  • The appendix presents complementary cumulative degree distributions and clustering spectra for layers in the multiscale navigation shell.Source: Appendix E · p. 25, Figure 14 · p. 25, Figure 15 · p. 25
  • Metric-space congruency is preserved after navigation coarse-graining even when block sizes differ.In this procedure, pairs are merged into a supernode only if they are connected.Source: Appendix E · p. 25
  • Empirical connection probabilities report the fraction of connected pairs within ranges of χ(l), with a theoretical connection-probability curve also shown.Source: Figure 16 · p. 26, Appendix E · p. 26
Loading 1706.00394v1…