All scale-free networks are sparse
arXiv:1106.5150 · doi:10.1103/PhysRevLett.107.178701
Abstract
We study the realizability of scale free-networks with a given degree sequence, showing that the fraction of realizable sequences undergoes two first-order transitions at the values 0 and 2 of the power-law exponent. We substantiate this finding by analytical reasoning and by a numerical method, proposed here, based on extreme value arguments, which can be applied to any given degree distribution. Our results reveal a fundamental reason why large scale-free networks without constraints on minimum and maximum degree must be sparse.
4 pages, 2 figures
References in corpus (1)
Cited by in corpus (52)
- Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science
- Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
- Spectrum of Controlling and Observing Complex Networks
- Quantifying randomness in real networks
- Sparse graphs using exchangeable random measures
- Entropy of stochastic blockmodel ensembles
- A topological insight into restricted Boltzmann machines
- Minimum Dominating Sets in Scale-Free Network Ensembles
- Constructing and sampling directed graphs with given degree sequences
- Social confinement and mesoscopic localization of epidemics on networks
- Degree correlations in directed scale-free networks
- The Phase Stability Network of all Inorganic Materials
- Network comparison and the within-ensemble graph distance
- Low-dimensional behavior of Kuramoto model with inertia in complex networks
- Dense Power-law Networks and Simplicial Complexes
- Network community detection using modularity density measures
- Entropy distribution and condensation in random networks with a given degree distribution
- Clustering of random scale-free networks
- Fast and accurate determination of modularity and its effect size
- Exact sampling of graphs with prescribed degree correlations
- Structurally Robust Control of Complex Networks
- Finding network communities using modularity density
- Multiplex congruence network of natural numbers
- Discriminating abilities of threshold-free evaluation metrics in link prediction
- Bias in generation of random graphs
- Network nestedness as generalized core-periphery structures
- What exactly are the properties of scale-free and other networks?
- Counterexample: scale-free networked graphs with invariable diameter and density feature
- Two universal physical principles shape the power-law statistics of real-world networks
- Endemic infections are always possible on regular networks
- From sparse to dense and from assortative to disassortative in online social networks
- Dense networks with scale-free feature
- Lower bound of assortativity coefficient in scale-free networks
- Entropy rate of non-equilibrium growing networks
- Structural Bounds on the Dyadic Effect
- Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
- Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
- Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
- Social patterns revealed through random matrix theory
- Fundamental Structural Constraint of Random Scale-Free Networks
- Latent Poisson models for networks with heterogeneous density
- Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
- Giant component sizes in scale-free networks with power-law degrees and cutoffs
- Exactly scale-free scale-free networks
- Detecting network communities via greedy expanding based on local superiority index
- Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario
- Distinct Degrees and Their Distribution in Complex Networks
- Nodal statistics-based equivalence relation for graph collections
- Characterizing several properties of high-dimensional random Apollonian networks
- Correlation-Based Community Detection
- Pulse-coupled model of excitable elements on heterogeneous sparse networks
- Construction of simplicial complexes with prescribed degree-size sequences