Scale-Free Networks are Ultrasmall

Abstract

We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k) ~ k^-a, i.e. the probability of having k links outgoing from a site. In contrast to the diameter of regular random networks or small world networks which is known to be d ~ lnN, we show, using analytical arguments, that scale free networks with 2<a<3 have a much smaller diameter, behaving as d ~ lnlnN. For a=3, our analysis yields d ~ lnN/lnlnN, as obtained by Bollobas and Riordan, while for a>3, d ~ lnN. We also show that, for any a>2, one can construct a deterministic scale free network with d ~ lnlnN, and this construction yields the lowest possible diameter.

Latex, 4 pages, 2 eps figures, small corrections, added explanations

References in corpus (4)

• Lethality and centrality in protein networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Search in Power-Law Networks
• Extremal properties of random trees

Cited by in corpus (218)

• The structure and function of complex networks
• Synchronization in complex networks
• Characterization of complex networks: A survey of measurements
• Vertex similarity in networks
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• The phase transition in inhomogeneous random graphs
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Turing patterns in network-organized activator-inhibitor systems
• Turing patterns on networks
• Percolation on complex networks: Theory and application
• Self-similarity of complex networks and hidden metric spaces
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Enhancing complex-network synchronization
• Bipartite Graphs as Models of Complex Networks
• Interdependent networks with correlated degrees of mutually dependent nodes
• Network Geometry
• Fractal and Transfractal Recursive Scale-Free Nets
• Efficiency of informational transfer in regular and complex networks
• Optimal Paths in Disordered Complex Networks
• Scale-free Networks Well Done
• Construction and Analysis of Random Networks with Explosive Percolation
• Compact Routing on Internet-Like Graphs
• Structure of shells in complex networks
• Complex Networks on Hyperbolic Surfaces
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Multiscale unfolding of real networks by geometric renormalization
• Linking the Network Centrality Measures Closeness and Degree
• The anatomy of Reddit: An overview of academic research
• Rate equation approach for correlations in growing network models
• Mean-field theory for clustering coefficients in Barabasi-Albert networks
• Polynomial growth in age-dependent branching processes with diverging reproductive number
• Searchability of Networks
• Characterizing the network topology of the energy landscapes of atomic clusters
• Structural properties of spatially embedded networks
• Relations between Average Distance, Heterogeneity and Network Synchronizability
• Navigable Networks as Nash Equilibria of Navigation Games
• Recent advances of percolation theory in complex networks
• Absence of kinetic effects in reaction-diffusion processes in scale-free networks
• The fractal/small-world dichotomy in real-world networks
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Mean first-passage time for random walks on undirected networks
• Structural constraints in complex networks
• Self-avoiding walks on scale-free networks
• Exact solution of mean geodesic distance for Vicsek fractals
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Laplacian Renormalization Group for heterogeneous networks
• Universal scaling of distances in complex networks
• First passage percolation on random graphs with finite mean degrees
• Exact scaling properties of a hierarchical network model
• Random walk and trapping processes on scale-free networks
• Optimal Paths in Complex Networks with Correlated Weights: The World-wide Airport Network
• Exact analytical solution of average path length for Apollonian networks
• Organization of modular networks
• Spreading of infectious diseases on heterogeneous populations: multi-type network approach
• Link prediction based on path entropy
• RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s
• Localization transition on complex networks via spectral statistics
• Asymptotic analysis of first passage time in complex networks
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Geographical Embedding of Scale-Free Networks
• Dynamic Max-Consensus and Size Estimation of Anonymous Multi-Agent Networks
• Scale free networks from a Hamiltonian dynamics
• Localization Transition of Biased Random Walks on Random Networks
• Fractal Boundaries of Complex Networks
• Complex network view of evolving manifolds
• Biased Percolation on Scale-free Networks
• Modeling Structure and Resilience of the Dark Network
• Trapping in scale-free networks with hierarchical organization of modularity
• Complex systems approach to natural language
• Bounding network spectra for network design
• Limited path percolation in complex networks
• Crossovers in ScaleFree Networks on Geographical Space
• Border Detection in Complex Networks
• Dynamic vaccination in partially overlapped multiplex network
• Spreading dynamics on small-world networks with connectivity fluctuations and correlations
• Random walks in modular scale-free networks with multiple traps
• Nonbacktracking expansion of finite graphs
• Counting spanning trees in self-similar networks by evaluating determinants
• Average distance in a hierarchical scale-free network: an exact solution
• The synchronizability of highly clustered scale-free networks
• Scale-free networks as an epiphenomenon of memory
• Search in Complex Networks : a New Method of Naming
• Thresholding normally distributed data creates complex networks
• Degree-dependent intervertex separation in complex networks
• Complex networks embedded in space: Dimension and scaling relations between mass, topological distance and Euclidean distance
• Exploring complex networks via topological embedding on surfaces
• Distance distribution in configuration model networks
• Modeling the average shortest path length in growth of word-adjacency networks
• Efficient algorithm to study interconnected networks
• Dynamic structural and topological phase transitions on the Warsaw Stock Exchange: A phenomenological approach
• Complex network analysis of literary and scientific texts
• Diffusion in scale-free networks with annealed disorder
• Solar Flares Complex Networks
• Anomalous behavior of trapping on a fractal scale-free network
• Navigating ultrasmall worlds in ultrashort time
• Why are there six degrees of separation in a social network?
• A network-based threshold model for the spreading of fads in society and markets
• Network Formation Games with Heterogeneous Players and the Internet Structure
• 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
• Constructing Limited Scale-Free Topologies Over Peer-to-Peer Networks
• Distribution of shortest cycle lengths in random networks
• Impact of degree heterogeneity on the behavior of trapping in Koch networks
• Diffusive Capture Process on Complex Networks
• The Fractional Preferential Attachment Scale-Free Network Model
• On the Tomography of Networks and Multicast Trees
• Probabilistic prediction in scale-free networks: Diameter changes
• Counterexample: scale-free networked graphs with invariable diameter and density feature
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• Optimization of transport protocols with path-length constraints in complex networks
• Discrete surface growth process as a synchronization mechanism for scale free complex networks
• A simple model clarifies the complicated relationships of complex networks
• Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks
• Dense networks with scale-free feature
• Lower bound of assortativity coefficient in scale-free networks
• Scale-Free Networks Emerging from Weighted Random Graphs
• Transport of multiple users in complex networks
• Social distancing strategies against disease spreading
• Identifying time dependence in network growth
• Preferential attachment during the evolution of a potential energy landscape
• Random walks and diameter of finite scale-free networks
• Anomalous biased diffusion in networks
• Scale free networks by preferential depletion
• A scale-free network hidden in the collapsing polymer
• Assortative and disassortative mixing investigated using the spectra of graphs
• Critical Phase of Bond Percolations on Growing Networks
• Correlations in interacting systems with a network topology
• Nonlinear Barabási-Albert Network
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• The scaling of the minimum sum of edge lengths in uniformly random trees
• Algorithmic Networks: central time to trigger expected emergent open-endedness
• Critical behavior and correlations on scale-free small-world networks. Application to network design
• Networks with many structural scales: a Renormalization Group perspective
• Hub-Accelerator: Fast and Exact Shortest Path Computation in Large Social Networks
• Impact of noise and damage on collective dynamics of scale-free neuronal networks
• Two-dimensional Ising model on random lattices with constant coordination number
• Derivation of the percolation threshold for the network model of Barabasi and Albert
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Contact graphs of disk packings as a model of spatial planar networks
• Scale-free network clustering in hyperbolic and other random graphs
• Scale-free networks with a large- to hypersmall-world transition
• The rigorous solution for the average distance of a Sierpinski network
• Size of quantum networks
• An alternative approach to determining average distance in a class of scale-free modular networks
• The Graph Structure of the Internet at the Autonomous Systems Level during Ten Years
• When is a scale-free graph ultra-small?
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• An Agent-Based Model of Message Propagation in the Facebook Electronic Social Network
• Phase transitions on a class of generalized Vicsek-like models of collective motion
• Social dynamics with peer support on heterogeneous networks: The "mafia model"
• Phases of Small Worlds: A Mean Field Formulation
• Scaling Laws in Chennai Bus Network
• Structural Invertibility and Optimal Sensor Node Placement for Error and Input Reconstruction in Dynamic Systems
• Emergence of Long-Range Correlations in Random Networks
• Complex Network Analysis of a Graphic Novel: The Case of the Bande Dessinée Thorgal
• Criterions for locally dense subgraphs
• Potts Model On Random Trees
• Pathlength scaling in graphs with incomplete navigational information
• Strange Attractors in Complex Networks
• Latent Network Summarization: Bridging Network Embedding and Summarization
• Generating random networks that consist of a single connected component with a given degree distribution
• Study of dynamic and static routing for improvement of the transportation efficiency on small complex networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Parallel Delta-Stepping Algorithm for Shared Memory Architectures
• Clustering Algorithms for Scale-free Networks and Applications to Cloud Resource Management
• A new structure entropy of complex networks based on Tsallis nonextensive statistical mechanics
• Random graphs with arbitrary i.i.d. degrees
• Log-periodic oscillations due to discrete effects in complex networks
• Activity ageing in growing networks
• Power law scaling for the adiabatic algorithm for search engine ranking
• Scale-free tree network with an ultra-large diameter
• Random degree-degree correlated networks
• A Pyramid Scheme Model Based on "Consumption Rebate" Frauds
• Complex Networks in the Framework of Nonassociative Geometry
• Fast algorithm for topologically disordered lattices with constant coordination number
• Unusual percolation in simple small-world networks
• Towards Limited Scale-free Topology with Dynamic Peer Participation
• Error-correcting codes on scale-free networks
• On the Capacity of Fractal D2D Social Networks with Hierarchical Communications
• DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs
• Gaussian Networks Generated by Random Walks
• Model-based reconstruction of real-world fractal complex networks
• Degree and connectivity of the Internet's scale-free topology
• Simulation of Large Scale Neural Networks for Evaluation Applications
• Efficiency of message transmission using biased random walks in complex networks in the presence of traps
• On Equilibrium Metropolis Simulations on Self-Organized Urban Street Networks
• Two Power Series Models of Self-Similarity in Social Networks
• Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks
• Slow dynamics of Zero Range Process in the Framework of Traps Model
• Modeling Transitivity in Complex Networks
• An extremal problem: How small scale-free graph can be
• Average shortest-path length in word-adjacency networks: Chinese versus English
• Active-absorbing phase transition and small world behaviour in Ising model on finite addition type networks in two dimensions
• Data Driven Charge Transfer Atlas Provides Topological View of Electronic Structure Properties for Arbitrary Proteins Complexes
• Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application
• Electronic Structure Topology Associated Domain is Useful to Minimize the Uncertainty of QM/MM Boundary Charge Transfer Effects
• Cumulative structure and path length in networks of knowledge
• Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks
• Unicast and Multicast Qos Routing with Soft Constraint Logic Programming
• Estimating Shortest Path Length Distributions via Random Walk Sampling
• From Spatial to Spectral: Network Renormalization via Dynamical Correlations
• Universality classes in the time evolution of epidemic outbreaks on complex networks
• Connectivity estimation of high dimensional data recorded from neuronal cells
• Time series of Internet AS-level topology graphs: four patterns and one model
• Fission: A Provably Fast, Scalable, and Secure Permissionless Blockchain
• Node Exchange Network and its Statistical Analysis
• The Analyses of Node Swapping Networks by New Graph Index
• Building Bridges into the Unknown: Personalizing Connections to Little-known Countries
• Computing well-balanced spanning trees of unweighted networks
• Pulse-coupled model of excitable elements on heterogeneous sparse networks
• Arbitrary degree distribution and high clustering in networks of locally interacting agents
• Coupled effects of local movement and global interaction on contagion
• Dynamical patterns of epidemic outbreaks in complex heterogeneous networks
• Bring your friend! Real or virtual?
• Distributed Maximal Independent Set on Scale-Free Networks
• Zero forcing number of graphs with a power law degree distribution