Average path length in random networks

Abstract

Analytic solution for the average path length in a large class of random graphs is found. We apply the approach to classical random graphs of Erdös and Rényi (ER) and to scale-free networks of Barabási and Albert (BA). In both cases our results confirm previous observations: small world behavior in classical random graphs $l_{ER}\sim \ln N$ and ultra small world effect characterizing scale-free BA networks $l_{BA}\sim \ln N/\ln \ln N$. In the case of scale-free random graphs with power law degree distributions we observed the saturation of the average path length in the limit of $N\to \infty$ for systems with the scaling exponent $2<\alpha <3$ and the small-world behaviour for systems with $\alpha >3$.

4 pages, 2 figures, changed content

References in corpus (20)

• Statistical mechanics of complex networks
• Evolution of networks
• Dynamical and correlation properties of the Internet
• Universal Behavior of Load Distribution in Scale-free Networks
• Search in Power-Law Networks
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Scale-Free Networks are Ultrasmall
• Halting viruses in scale-free networks
• Class of correlated random networks with hidden variables
• Highly clustered scale-free networks
• Epidemic threshold in structured scale-free networks
• A General Formalism for Inhomogeneous Random Graphs
• The origin of degree correlations in the Internet and other networks
• Optimal Paths in Disordered Complex Networks
• Statistical ensemble of scale-free random graphs
• Path finding strategies in scale-free networks
• Critical phenomena in networks
• Shortest paths and load scaling in scale-free trees
• Metric structure of random networks
• How to calculate the main characteristics of random graphs - a new approach

Cited by in corpus (76)

• Vertex similarity in networks
• Uncovering collective listening habits and music genres in bipartite networks
• Compact Routing on Internet-Like Graphs
• Universal scaling of distances in complex networks
• Exact analytical solution of average path length for Apollonian networks
• Analyses of Some Structural Properties on a Class of Hierarchical Scale-free Networks
• Organization of modular networks
• Distance distribution in random graphs and application to networks exploration
• Strong Effects of Network Architecture in the Entrainment of Coupled Oscillator Systems
• On the genre-fication of Music: a percolation approach (long version)
• An extended formalism for preferential attachment in heterogeneous complex networks
• The topology of large Open Connectome networks for the human brain
• Complex systems approach to natural language
• Fractal scale-free networks resistant to disease spread
• Analytical results for the distribution of shortest path lengths in random networks
• Average distance in a hierarchical scale-free network: an exact solution
• Public transportation in UK viewed as a complex network
• Degree-dependent intervertex separation in complex networks
• Distance distribution in configuration model networks
• Modeling the average shortest path length in growth of word-adjacency networks
• Dynamic structural and topological phase transitions on the Warsaw Stock Exchange: A phenomenological approach
• Effect of shortest path multiplicity on congestion of multiplex networks
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Perturbing General Uncorrelated Networks
• Distribution of shortest cycle lengths in random networks
• Searching for small-world and scale-free behaviour in long-term historical data of a real-world power grid
• Evolutionary Events in a Mathematical Sciences Research Collaboration Network
• Transition from fractal to non-fractal scalings in growing scale-free networks
• Heterogeneous excitable systems exhibit Griffiths phases below hybrid phase transitions
• Power-law distributions of dynamic cascade failures in power-grid models
• Complex Network for Solar Active Regions
• Network Detection Theory and Performance
• Bayesian Discovery of Threat Networks
• Properties of Kinetic Transition Networks for Atomic Clusters and Glassy Solids
• Statistical analysis of articulation points in configuration model networks
• Modeling the Impact of Social Distancing and Targeted Vaccination on the Spread of COVID-19 through a Real City-Scale Contact Network
• The Human Plasma Membrane Peripherome: Visualization and Analysis of Interactions
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Strong-disorder renormalization group study of the Anderson localization transition in three and higher dimensions
• Synchronization dynamics on the EU and US power grids
• Sizing the length of complex networks
• What makes us humans: Differences in the critical dynamics underlying the human and fruit-fly connectome
• Mapping the $q$-voter model: From a single chain to complex networks
• Thermodynamic approach for community discovering within the complex networks: LiveJournal study
• Non-universal power-law dynamics of SIR models on hierarchical modular networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Network analysis of the COSMOS galaxy field
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• The rigorous solution for the average distance of a Sierpinski network
• Statistical analysis of edges and bredges in configuration model networks
• When is a scale-free graph ultra-small?
• Natural orbital networks
• Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
• DeepGG: a Deep Graph Generator
• Studying power-grid synchronization with incremental refinement of model heterogeneity
• Deterministic Random Walk Model in NetLogo and the Identification of Asymmetric Saturation Time in Random Graph
• It's Always April Fools' Day! On the Difficulty of Social Network Misinformation Classification via Propagation Features
• Log-periodic oscillations due to discrete effects in complex networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Prediction of USA November 2020 Election Results Using Multifactor Twitter Data Analysis Method
• Eigenvalue Preferential Attachment Networks A Dandelion Structure
• Properties of Latent Variable Network Models
• Unimodular lattice triangulations as small-world and scale-free random graphs
• Metrics for Community Analysis: A Survey
• Model-based reconstruction of real-world fractal complex networks
• Statistical privacy-preserving message dissemination for peer-to-peer networks
• Physics of free climbing
• Parallel Scheduling Algorithm based on Complex Coloring for Input-Queued Switches
• A machine learning procedure to detect network attacks
• Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks
• Statistics of remote regions of networks
• Solving Splitted Multi-Commodity Flow Problem by Efficient Linear Programming Algorithm
• Proximity Based Load Balancing Policies on Graphs: A Simulation Study
• The largest cognitive systems will be optoelectronic
• Universality classes in the time evolution of epidemic outbreaks on complex networks