Average path length in uncorrelated random networks with hidden variables

Abstract

Analytic solution for the average path length in a large class of uncorrelated random networks with hidden variables is found. We apply the approach to classical random graphs of Erdos and Renyi (ER), evolving networks introduced by Barabasi and Albert (BA) as well as random networks with asymptotic scale-free connectivity distributions characterized by an arbitrary scaling exponent $\alpha >2$. Our result for $2<\alpha <3$ shows that structural properties of asymptotic scale-free networks including numerous examples of real-world systems are even more intriguing then ultra-small world behavior noticed in pure scale-free structures and for large system sizes $N\to \infty$ there is a saturation effect for the average path length.

8 pages, 4 figures; see also cond-mat/0212230 and cond-mat/0308629

References in corpus (2)

• Optimal Paths in Disordered Complex Networks
• How to calculate the main characteristics of random graphs - a new approach

Cited by in corpus (74)

• Vertex similarity in networks
• Uncovering collective listening habits and music genres in bipartite networks
• 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
• An extended formalism for preferential attachment in heterogeneous complex networks
• The topology of large Open Connectome networks for the human brain
• On the genre-fication of Music: a percolation approach (long version)
• Complex systems approach to natural language
• Fractal scale-free networks resistant to disease spread
• Average distance in a hierarchical scale-free network: an exact solution
• Analytical results for the distribution of shortest path lengths in random networks
• Public transportation in UK viewed as a complex network
• Degree-dependent intervertex separation in complex networks
• Modeling the average shortest path length in growth of word-adjacency networks
• Distance distribution in configuration model 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 subcritical Erdős-Rényi networks
• The distribution of shortest path lengths in a class of node duplication network models
• Searching for small-world and scale-free behaviour in long-term historical data of a real-world power grid
• Distribution of shortest cycle lengths in random networks
• 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
• The Human Plasma Membrane Peripherome: Visualization and Analysis of Interactions
• Modeling the Impact of Social Distancing and Targeted Vaccination on the Spread of COVID-19 through a Real City-Scale Contact Network
• 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
• Mapping the $q$-voter model: From a single chain to complex networks
• What makes us humans: Differences in the critical dynamics underlying the human and fruit-fly connectome
• Thermodynamic approach for community discovering within the complex networks: LiveJournal study
• Non-universal power-law dynamics of SIR models on hierarchical modular networks
• Network analysis of the COSMOS galaxy field
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• 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
• When is a scale-free graph ultra-small?
• Statistical analysis of edges and bredges in configuration model networks
• Natural orbital networks
• DeepGG: a Deep Graph Generator
• Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• 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
• Studying power-grid synchronization with incremental refinement of model heterogeneity
• Log-periodic oscillations due to discrete effects in complex networks
• Properties of Latent Variable Network Models
• Prediction of USA November 2020 Election Results Using Multifactor Twitter Data Analysis Method
• Eigenvalue Preferential Attachment Networks A Dandelion Structure
• Unimodular lattice triangulations as small-world and scale-free random graphs
• Statistical privacy-preserving message dissemination for peer-to-peer networks
• Model-based reconstruction of real-world fractal complex networks
• Metrics for Community Analysis: A Survey
• 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
• Proximity Based Load Balancing Policies on Graphs: A Simulation Study
• Solving Splitted Multi-Commodity Flow Problem by Efficient Linear Programming Algorithm
• The largest cognitive systems will be optoelectronic
• Universality classes in the time evolution of epidemic outbreaks on complex networks
• Statistics of remote regions of networks