Efficient Behavior of Small-World Networks

Abstract

We introduce the concept of efficiency of a network, measuring how efficiently it exchanges information. By using this simple measure small-world networks are seen as systems that are both globally and locally efficient. This allows to give a clear physical meaning to the concept of small-world, and also to perform a precise quantitative a nalysis of both weighted and unweighted networks. We study neural networks and man-made communication and transportation systems and we show that the underlying general principle of their construction is in fact a small-world principle of high efficiency.

1 figure, 2 tables. Revised version. Accepted for publication in Phys. Rev. Lett

Cited by in corpus (295)

• The structure and function of complex networks
• Community detection in graphs
• Evolution of networks
• The structure and dynamics of multilayer networks
• Spatial Networks
• Characterization of complex networks: A survey of measurements
• Predicting Missing Links via Local Information
• Synchronization in small-world systems
• Networks beyond pairwise interactions: structure and dynamics
• Vital nodes identification in complex networks
• A model for cascading failures in complex networks
• Evidence of economic segregation from mobility lockdown during COVID-19 epidemic
• Human Mobility: Models and Applications
• Mitigation of Malicious Attacks on Networks
• Recommender Systems
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Statistical physics of vaccination
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• The efficiency of multi-target drugs: the network approach might help drug design
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• The Network Analysis of Urban Streets: A Primal Approach
• Modeling Cascading Failures in the North American Power Grid
• Centrality Measures in Spatial Networks of Urban Streets
• Is the Boston subway a small-world network ?
• Efficiency of Scale-Free Networks: Error and Attack Tolerance
• Statistical analysis of 22 public transport networks in Poland
• Recurrence-based time series analysis by means of complex network methods
• The physics of brain network structure, function, and control
• Layered Complex Networks
• Graph analysis of functional brain networks: practical issues in translational neuroscience
• Vulnerability and Protection of Critical Infrastructures
• Structure and dynamics of core-periphery networks
• A Tutorial in Connectome Analysis: Topological and Spatial Features of Brain Networks
• Structural Properties of Planar Graphs of Urban Street Patterns
• Power grids vulnerability: a complex network approach
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Consistency and differences between centrality measures across distinct classes of networks
• Small-world behavior in time-varying graphs
• Topology of the conceptual network of language
• Public transport networks: empirical analysis and modeling
• A Method to Find Community Structures Based on Information Centrality
• Graph Metrics for Temporal Networks
• Evolving functional network properties and synchronizability during human epileptic seizures
• Measuring and modelling correlations in multiplex networks
• Functional modularity of background activities in normal and epileptic brain networks
• Network resilience
• Structure and Time-Evolution of an Internet Dating Community
• Stations, trains and small-world networks
• Efficiency of informational transfer in regular and complex networks
• Brain Network Analysis: Separating Cost from Topology using Cost-integration
• Measuring social dynamics in a massive multiplayer online game
• Navigation of brain networks
• Ising-like dynamics in large-scale functional brain networks
• Network Analysis of Particles and Grains
• Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
• Defecting or not defecting: how to "read" human behavior during cooperative games by EEG measurements
• Enhancing network robustness for malicious attacks
• Formalising the multidimensional nature of social networks
• Developmental increases in white matter network controllability support a growing diversity of brain dynamics
• Ising model in small-world networks
• Combining complex networks and data mining: why and how
• Shannon entropy of brain functional complex networks under the influence of the psychedelic Ayahuasca
• Preferential Detachment During Human Brain Development: Age- and Sex-Specific Structural Connectivity in Diffusion Tensor Imaging (DTI) Data
• A spectrum of routing strategies for brain networks
• Topological analysis of the connectome of digital reconstructions of neural microcircuits
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Impact of the reference choice on scalp EEG connectivity estimation
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Choosing Wavelet Methods, Filters, and Lengths for Functional Brain Network Construction
• Urban street networks: a comparative analysis of ten European cities
• Scaling and correlations in three bus-transport networks of China
• Clustering coefficients for correlation networks
• Transport on Complex Networks: Flow, Jamming and Optimization
• The Influence of Network Topology on Sound Propagation in Granular Materials
• A topological criterion for filtering information in complex brain networks
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• Multiple, weak hits confuse complex systems: A transcriptional regulatory network as an example
• Fastest learning in small world neural networks
• A Large-Scale Community Structure Analysis In Facebook
• Network Harness: Metropolis Public Transport
• Range-based attack on links in scale-free networks: are long-range links responsible for the small-world phenomenon?
• Modular gateway-ness connectivity and structural core organization in maritime network science
• Urban road networks -- Spatial networks with universal geometric features? A case study on Germany's largest cities
• Multimodal urban mobility and multilayer transport networks
• Smart Rewiring for Network Robustness
• The Backbone of a City
• Reduced integration and improved segregation of functional brain networks in Alzheimer's disease
• Multiscale Topological Properties Of Functional Brain Networks During Motor Imagery After Stroke
• Mesoscopic organization reveals the constraints governing C. elegans nervous system
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• Vulnerability of weighted networks
• From brain to earth and climate systems: Small-world interaction networks or not?
• Growing Urban Bicycle Networks
• Spatio-temporal networks: reachability, centrality and robustness
• Role of Network Topology in the Synchronization of Power Systems
• Models of communication and control for brain networks: distinctions, convergence, and future outlook
• Emergence of assortative mixing between clusters of cultured neurons
• A tale of two cities. Vulnerabilities of the London and Paris transit networks
• Can we neglect the multi-layer structure of functional networks?
• The Organization of Strong Links in Complex Networks
• The Web Graph of a Tourism System
• Structural and topological phase transitions on the German Stock Exchange
• How structure sculpts function: unveiling the contribution of anatomical connectivity to the brain's spontaneous correlation structure
• Beware of the Small-World neuroscientist!
• Loss of synchronization in complex neuronal networks with delay
• Social cohesion, structural holes, and a tale of two measures
• Weight Thresholding on Complex Networks
• Unraveling Spurious Properties of Interaction Networks with Tailored Random Networks
• Sparsity through evolutionary pruning prevents neuronal networks from overfitting
• Local impacts on road networks and access to critical locations during extreme floods
• Inferring network properties from time series using transfer entropy and mutual information: validation of multivariate versus bivariate approaches
• The Sensitivity of Electric Power Infrastructure Resilience to the Spatial Distribution of Disaster Impacts
• Network Analysis in the Legal Domain: A complex model for European Union legal sources
• Modularity produces small-world networks with dynamical time-scale separation
• Critical fluctuations in spatial complex networks
• Enhancing synchronizability of weighted dynamical networks using betweenness centrality
• State and Network Structures of Stock Markets around the Global Financial Crisis
• Data-driven strategies for optimal bicycle network growth
• Using graph concepts to understand the organization of complex systems
• Modular networks emerge from multiconstraint optimization
• Estimating the impact of structural directionality: How reliable are undirected connectomes?
• Resilient by Design: Simulating Street Network Disruptions across Every Urban Area in the World
• Network structure of subway passenger flows
• Evolving small-world networks with geographical attachment preference
• Optimization of network structure to random failures
• Systematic evaluation of a new combinatorial curvature for complex networks
• Software systems through complex networks science: Review, analysis and applications
• Topological Structure of Urban Street Networks from the Perspective of Degree Correlations
• Discrete Ricci curvatures for directed networks
• Random Walks Along the Streets and Canals in Compact Cities: Spectral analysis, Dynamical Modularity, Information, and Statistical Mechanics
• Smallest small-world network
• Multilayer Network Science: from Cells to Societies
• Optimizing topological cascade resilience based on the structure of terrorist networks
• A network perspective on intermedia agenda-setting
• Public transportation in UK viewed as a complex network
• Correlation Between Student Collaboration Network Centrality and Academic Performance
• Distributing circuits over heterogeneous, modular quantum computing network architectures
• Complex networks: new trends for the analysis of brain connectivity
• Quantifying efficient information exchange in real network flows
• Synchronisation in networks of delay-coupled type-I excitable systems
• Exploring associations between micro-level models of innovation diffusion and emerging macro-level adoption patterns
• Human and social capital strategies for Mafia network disruption
• Great cities look small
• Enhancing the robustness of scale-free networks
• Self-avoiding walks and connective constants in small-world networks
• Identifying vital nodes by Achlioptas process
• Epidemics of Liquidity Shortages in Interbank Markets
• Analysis on the urban street network of Korea: Connections between topology and meta-information
• Effect of shortest path multiplicity on congestion of multiplex networks
• Complex networks with tuneable dimensions as a universality playground
• Quantum transport with coupled cavities on the Apollonian network
• Temporal Gravity Model for Important Nodes Identification in Temporal Networks
• A statistical model for brain networks inferred from large-scale electrophysiological signals
• Generating Robust and Efficient Networks Under Targeted Attacks
• The Weighted Bitcoin Lightning Network
• Modeling self-organization of communication and topology in social networks
• Integrating temporal and spatial scales: Human structural network motifs across age and region-of-interest size
• Introduction to correlation networks: Interdisciplinary approaches beyond thresholding
• Evolutionary Events in a Mathematical Sciences Research Collaboration Network
• Parenclitic network analysis of methylation data for cancer identification
• Extinction times of epidemic outbreaks in networks
• Antiferromagnetic Ising model in small-world networks
• Optimizing transport efficiency on scale-free networks through assortative or dissortative topology
• Developmental time windows for axon growth influence neuronal network topology
• Large-scale inference and graph theoretical analysis of gene-regulatory networks in B. stubtilis
• The emergent integrated network structure of scientific research
• Evolving efficiency and robustness of global oil trade networks
• Scale-free networks embedded in fractal space
• Resilience of international oil trade networks under extreme event shock-recovery simulations
• A framework to generate hypergraphs with community structure
• Adaptive rewiring of random neural networks generates convergent-divergent units
• Basic principles drive self-organization of brain-like connectivity structure
• The agents' preferences and the topology of networks
• Goal-directed graph construction using reinforcement learning
• How to design multi-target drugs: Target search options in cellular networks
• Synchronization dynamics on the EU and US power grids
• Sizing the length of complex networks
• The Flow Dimension and Capacity for Structuring Urban Street Networks
• Centrality Measures in Complex Networks: A Survey
• Evolutionary and topological properties of gene modules and driver mutations in a leukemia gene regulatory network
• Characterization and exploitation of community structure in cover song networks
• The Multiplex Efficiency Index: unveiling the Brazilian Air Transportation Multiplex Network -- BATMN
• Revealing directed effective connectivity of cortical neuronal networks from measurements
• Absorbing Random Walks Interpolating Between Centrality Measures on Complex Networks
• Disruption and recovery of the US domestic airline networks during the COVID-19 pandemic
• Fair sharing of resources in a supply network with constraints
• On Detection and Structural Reconstruction of Small-World Random Networks
• Kinetic-growth self-avoiding walks on small-world networks
• Transmission of packets on a hierarchical network: Statistics and explosive percolation
• Scale-variant topological information for characterizing the structure of complex networks
• Coevolution of relationship-driven cooperation under recommendation protocol on multiplex networks
• Network-centric indicators for fragility in global financial indices
• Emergence of Robust and Efficient Networks in a Family of Attachment Models
• Threshold-free estimation of entropy from a Pearson matrix
• Balancing building and maintenance costs in growing transport networks
• Cluster structure of functional networks estimated from high-resolution EEG data
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Zero-temperature Glauber dynamics on small-world networks
• Complex systems: features, similarity and connectivity
• Link deletion in directed complex networks
• An interpretable machine-learned model for international oil trade network
• Comparing spatial networks: A 'one size fits all' efficiency-driven approach
• Structural efficiency of percolation landscapes in flow networks
• Random-Graph Models and Characterization of Granular Networks
• Anomalous Consistency in Mild Cognitive Impairment: a complex networks approach
• Information Flow in the FTX Bankruptcy: A Network Approach
• Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
• Optimizing the Human Learnability of Abstract Network Representations
• Understanding Cascading Failures in Power Grids
• On alternative formulations of the small-world metric in complex networks
• Pendular behavior of public transport networks
• Distinct neurodynamics of functional brain networks in Alzheimer's disease and frontotemporal dementia as revealed by EEG
• Connectedness matters: Construction and exact random sampling of connected graphs
• Real-Space Visualization of Quantum Phase Transition by Network Topology
• Inferring Information Flow in Spike-train Data Sets using a Trial-Shuffle Method
• Finding the right scale of a network: Efficient identification of causal emergence through spectral clustering
• Comparing local search paths with global search paths on protein residue networks: allosteric communication
• Bounds of the sum of edge lengths in linear arrangements of trees
• A Communication Model for Adaptive Service Provisioning in Hybrid Wireless Networks
• A novel approach to study realistic navigations on networks
• Redundancy Analysis of the Railway Network of Hungary
• Impact of shocks to economies on the efficiency and robustness of the international pesticide trade networks
• Epidemic modelling requires knowledge of the social network
• Network-Based Approach for Modeling and Analyzing Coronary Angiography
• Robustness of Regular Graphs Based on Natural Connectivity
• Brain network efficiency is influenced by pathological source of corticobasal syndrome
• Existence of Life in 2 + 1 Dimensions
• Quantifying navigation complexity in transportation networks
• Low Cost Carriers induce specific and identifiable delay propagation patterns: an analysis of the EU and US systems
• Studying power-grid synchronization with incremental refinement of model heterogeneity
• Distinct Modes of Functional Neural Organization in Autism: Insights from Dynamical Systems Analysis of Resting-State EEG
• Exit Ripple Effects: Understanding the Disruption of Socialization Networks Following Employee Departures
• Emergence of scale-free properties in Hebbian networks
• Extremal Properties of Complex Networks
• Log-periodic oscillations due to discrete effects in complex networks
• Using complex networks to model 2-D and 3-D soil porous architecture
• Network efficiency of spatial systems with fractal morphology: a geometric graphs approach
• The general conformable fractional grey system model and its applications
• A Graph-Neural-Network-Entropy model of vital node identification on network attack and propagation
• A framework for seizure detection using effective connectivity, graph theory and deep modular neural networks
• Higher-order shortest paths in hypergraphs
• Random degree-degree correlated networks
• Effectiveness of Rapid Rail Transit System in Beijing
• Emergence of Functionally Differentiated Structures via Mutual Information Minimization in Recurrent Neural Networks
• New nodes attack strategies for real complex weighted networks
• On the assesment of functional connectivity in an immersive brain-computer interface during motor imagery
• Network approach towards understanding the crazing in glassy amorphous polymers
• Hypothesis Testing for Two Sample Comparison of Network Data
• Early deafness leads to re-shaping of global functional connectivity beyond the auditory cortex
• Nodal statistics-based equivalence relation for graph collections
• Multiscale modeling of brain network organization
• Functional brain networks: great expectations, hard times, and the big leap forward
• Decision-Making Frameworks for Network Resilience -- Managing and Mitigating Systemic (Cyber) Risk
• Range-based attacks on links in random scale-free networks
• Theory of Interface: Category Theory, Directed Networks and Evolution of Biological Networks
• Effect of Anisotropic Peierls Barrier on the Evolution of Discrete Dislocation Networks in Ni
• Unveiling connectivity patterns of railway timetables through complex network theory and Infomap clustering
• Taking a moment to measure Networks - A hierarchical approach
• Effects of neuronal variability on phase synchronization of neural networks
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Fortifying Critical Infrastructure Networks with Multicriteria Portfolio Decision Analysis: An Application to Railway Stations in Finland
• Local search on protein residue networks
• Altered connectedness of the brain chronnectome during the progression of Alzheimer's disease
• Decoding Musical Evolution Through Network Science
• Tracing the Attention of Moving Citizens
• superblockify: A Python Package for Automated Generation, Visualization, and Analysis of Potential Superblocks in Cities
• A model for the generation of road networks
• Landscape allocation: stochastic generators and statistical inference
• Functional and spatial rewiring jointly generate convergent-divergent units in self-organizing networks
• Towards a Quantitative Theory of Digraph-Based Complexes and its Applications in Brain Network Analysis
• Application of discrete Ricci curvature in pruning randomly wired neural networks: A case study with chest x-ray classification of COVID-19
• Topological and Temporal Stability Analysis of the Lightning Network
• Statistical analysis of weighted networks
• Optimality of Moore neighborhoods in protein contact maps
• Opportunities and challenges in partitioning the graph measure space of real-world networks
• Diseases on complex networks. Modeling from a database and a protection strategy proposal
• GUDIE: a flexible, user-defined method to extract subgraphs of interest from large graphs
• Some properties of hierarchic regular networks (a peep into fractal structures)
• Graph Metrics for Internet Robustness -- A Survey
• Manifold learning for brain connectivity
• Fast multipole networks
• Abrupt efficiency collapse in real-world complex weighted networks: robustness decrease with link weights heterogeneity
• Pattern phase diagram of spiking neurons on spatial networks
• Probabilistic Constraint Programming for Parameters Optimisation of Generative Models
• Power Plexus: A network based analysis
• Spatial Neural Networks and their Functional Samples: Similarities and Differences
• Étude de l'omniprésence des propriétés petit- monde et sans-échelle
• Noise-Induced Burst and Spike Synchronizations in An Inhibitory Small-World Network of Subthreshold Bursting Neurons
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• A big-world network in ASD: Dynamical connectivity analysis reflects a deficit in long-range connections and an excess of short-range connections
• Modelling terrestrial route networks to understand inter-polity interactions (southern Etruria, 950-500 BC)
• Recursive Shortest Path Algorithm with Application to Density-integration of Weighted Graphs
• Stable Matching with Incomplete Information in Structured Networks
• A Collaboration Network Model Of Cytokine-Protein Network
• Knowledge transfer in a tourism destination: the effects of a network structure