Economic Small-World Behavior in Weighted Networks

Abstract

The small-world phenomenon has been already the subject of a huge variety of papers, showing its appeareance in a variety of systems. However, some big holes still remain to be filled, as the commonly adopted mathematical formulation suffers from a variety of limitations, that make it unsuitable to provide a general tool of analysis for real networks, and not just for mathematical (topological) abstractions. In this paper we show where the major problems arise, and how there is therefore the need for a new reformulation of the small-world concept. Together with an analysis of the variables involved, we then propose a new theory of small-world networks based on two leading concepts: efficiency and cost. Efficiency measures how well information propagates over the network, and cost measures how expensive it is to build a network. The combination of these factors leads us to introduce the concept of {\em economic small worlds}, that formalizes the idea of networks that are "cheap" to build, and nevertheless efficient in propagating information, both at global and local scale. This new concept is shown to overcome all the limitations proper of the so-far commonly adopted formulation, and to provide an adequate tool to quantitatively analyze the behaviour of complex networks in the real world. Various complex systems are analyzed, ranging from the realm of neural networks, to social sciences, to communication and transportation networks. In each case, economic small worlds are found. Moreover, using the economic small-world framework, the construction principles of these networks can be quantitatively analyzed and compared, giving good insights on how efficiency and economy principles combine up to shape all these systems.

17 pages, 10 figures, 4 tables

Cited by in corpus (58)

• The structure and function of complex networks
• The structure and dynamics of multilayer networks
• Spatial Networks
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Statistical physics of vaccination
• Structural measures for multiplex networks
• Evolutionary games on multilayer networks: A colloquium
• The Network Analysis of Urban Streets: A Primal Approach
• Centrality Measures in Spatial Networks of Urban Streets
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Graph analysis of functional brain networks: practical issues in translational neuroscience
• Vulnerability and Protection of Critical Infrastructures
• Structural Properties of Planar Graphs of Urban Street Patterns
• Enhancing complex-network synchronization
• A Method to Find Community Structures Based on Information Centrality
• Modelling the Air Transport with Complex Networks: a short review
• Complex network analysis of water distribution systems
• Brain Network Analysis: Separating Cost from Topology using Cost-integration
• Network Analysis of Particles and Grains
• Preferential Detachment During Human Brain Development: Age- and Sex-Specific Structural Connectivity in Diffusion Tensor Imaging (DTI) Data
• A topological criterion for filtering information in complex brain networks
• Modular gateway-ness connectivity and structural core organization in maritime network science
• The Backbone of a City
• Phase transition in the economically modeled growth of a cellular nervous system
• From brain to earth and climate systems: Small-world interaction networks or not?
• Spatio-temporal networks: reachability, centrality and robustness
• Measure for degree heterogeneity in complex networks and its application to recurrence network analysis
• Social cohesion, structural holes, and a tale of two measures
• Unraveling Spurious Properties of Interaction Networks with Tailored Random Networks
• Emergence of small-world anatomical networks in self-organizing clustered neuronal cultures
• A measure of centrality based on the network efficiency
• Using graph concepts to understand the organization of complex systems
• Spatial network surrogates for disentangling complex system structure from spatial embedding of nodes
• Global synchronization of partially forced Kuramoto oscillators on Networks
• Multilayer Network Science: from Cells to Societies
• Complex networks: new trends for the analysis of brain connectivity
• Quantifying efficient information exchange in real network flows
• Developmental time windows for axon growth influence neuronal network topology
• Large-scale inference and graph theoretical analysis of gene-regulatory networks in B. stubtilis
• Minimal models of weighted scale-free networks
• The agents' preferences and the topology of networks
• Storage capacity of phase-coded patterns in sparse neural networks
• Cluster structure of functional networks estimated from high-resolution EEG data
• Continuous and robust clustering coefficients for weighted and directed networks
• Bounds of the sum of edge lengths in linear arrangements of trees
• Brain network efficiency is influenced by pathological source of corticobasal syndrome
• SALSA: A Novel Dataset for Multimodal Group Behavior Analysis
• Weighted networks of scientific communication: the measurement and geometrical role of weight
• The growing topology of the C. elegans connectome
• Learning Graph Filters for Structure-Function Coupling based Hub Node Identification
• Communicability Angle and the Spatial Efficiency of Networks
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Abrupt efficiency collapse in real-world complex weighted networks: robustness decrease with link weights heterogeneity
• An Automated System for Discovering Neighborhood Patterns in Ego Networks
• Statistical analysis of weighted networks
• Noise-Induced Burst and Spike Synchronizations in An Inhibitory Small-World Network of Subthreshold Bursting Neurons
• Effect of Small-World Connectivity on Fast Sparsely Synchronized Cortical Rhythms
• Recursive Shortest Path Algorithm with Application to Density-integration of Weighted Graphs