Multiscale network renormalization: scale-invariance without geometry

Abstract

Systems with lattice geometry can be renormalized exploiting their coordinates in metric space, which naturally define the coarse-grained nodes. By contrast, complex networks defy the usual techniques, due to their small-world character and lack of explicit geometric embedding. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we introduce a graph renormalization scheme valid for any hierarchy of heterogeneous coarse-grainings, thereby allowing for the definition of 'block-nodes' across multiple scales. This approach identifies a class of scale-invariant networks characterized by a necessary and specific dependence on additive hidden variables attached to nodes, plus optional dyadic factors. If the hidden variables are annealed, they lead to realistic scale-free networks with assortativity and finite local clustering, even in the sparse regime and in absence of geometry. If they are quenched, they can guide the renormalization of real-world networks with node attributes and distance-dependence or communities. As an application, we derive an accurate multiscale model of the International Trade Network applicable across arbitrary geographic partitions. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization.

References in corpus (31)

• Emergence of scaling in random networks
• Community detection in graphs
• Stochastic blockmodels and community structure in networks
• Self-similarity of complex networks
• Hyperbolic Geometry of Complex Networks
• The statistical mechanics of networks
• The phase transition in inhomogeneous random graphs
• The Statistical Physics of Real-World Networks
• Fitness-dependent topological properties of the World Trade Web
• Self-similarity of complex networks and hidden metric spaces
• Graph limits and exchangeable random graphs
• Skeleton and fractal scaling in complex networks
• The origin of degree correlations in the Internet and other networks
• Sparse graphs using exchangeable random measures
• Spectral coarse-graining of complex networks
• Exact and explicit probability densities for one-sided Levy stable distributions
• Coarse-Graining and Self-Dissimilarity of Complex Networks
• Multiscale unfolding of real networks by geometric renormalization
• Network Cosmology
• Reconstruction methods for networks: the case of economic and financial systems
• Laplacian Renormalization Group for heterogeneous networks
• Geographical Coarsegraining of Complex Networks
• Universal fractal scaling of self-organized networks
• Enhanced Gravity Model of trade: reconciling macroeconomic and network models
• A GDP-driven model for the binary and weighted structure of the International Trade Network
• Levy stable distributions via associated integral transform
• Exponential random graph models for networks with community structure
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Classical Information Theory of Networks
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes

Cited by in corpus (3)

• Network Renormalization
• Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
• Inhomogeneous random graphs with infinite-mean fitness variables