Transport in weighted networks: Partition into superhighways and roads

Abstract

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality -- number of times a node (or link) is used by transport paths. One component, the {\it superhighways}, is the infinite incipient percolation cluster; for which we find that nodes (or links) with high centrality dominate. For the other component, {\it roads}, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.

12 pages, 5 figures

References in corpus (14)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The architecture of complex weighted networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Resilience of the Internet to random breakdowns
• Universal Behavior of Load Distribution in Scale-free Networks
• Dynamics of market correlations: Taxonomy and portfolio analysis
• Topology of correlation based minimal spanning trees in real and model markets
• Optimal Paths in Disordered Complex Networks
• Scale-free trees: the skeletons of complex networks
• Minimum spanning trees on random networks
• Current Flow in Random Resistor Networks: The Role of Percolation in Weak and Strong Disorder
• Load distribution in weighted complex networks
• Effect of Disorder Strength on Optimal Paths in Complex Networks

Cited by in corpus (49)

• Spatial Networks
• Multiscale mobility networks and the large scale spreading of infectious diseases
• Extracting the multiscale backbone of complex weighted networks
• Understanding Road Usage Patterns in Urban Areas
• Unification of theoretical approaches for epidemic spreading on complex networks
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Predicting commuter flows in spatial networks using a radiation model based on temporal ranges
• Robust classification of salient links in complex networks
• Information filtering in complex weighted networks
• Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
• Epidemic Spreading in Weighted Networks: An Edge-Based Mean-Field Solution
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Brain, Music and non-Poisson Renewal Processes
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Extracting the information backbone in online system
• A parametric approach to information filtering in complex networks: The Pólya filter
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• Comprehensive routing strategy on multilayer networks
• Networking - A Statistical Physics Perspective
• Percolation properties in a traffic model
• The Competition for Shortest Paths on Sparse Graphs
• Localizations on Complex Networks
• Transport on weighted Networks: when correlations are independent of degree
• Counting spanning trees in self-similar networks by evaluating determinants
• Dynamics on networks: competition of temporal and topological correlations
• Transport in networks with multiple sources and sinks
• Mechanism of organization increase in complex systems
• Robustness of skeletons and salient features in networks
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Efficient immunization strategies to prevent financial contagion
• Emergence of double scaling law in complex system
• Transport of multiple users in complex networks
• The path most travelled: Mining road usage patterns from massive call data
• Betweenness centrality in dense spatial networks
• Anomalous electrical and frictionless flow conductance in complex networks
• Real-Space Renormalization Group for Spectral Properties of Hierarchical Networks
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• Topological estimation of the latent geometry of a complex network
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• Scaling of internode distances in weighted complex networks
• AutoEKF: Scalable System Identification for COVID-19 Forecasting from Large-Scale GPS Data
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs
• Percolation thresholds for discrete-continuous models with non-uniform probabilities of bond formation
• Identification and prioritization of urban traffic bottlenecks
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
• Learning the optimally coordinated routes from the statistical mechanics of polymers