How to determine if a random graph with a fixed degree sequence has a giant component
arXiv:1601.03714 · doi:10.1007/s00440-017-0757-1
Abstract
For a fixed degree sequence , let be a uniformly chosen (simple) graph on where the vertex has degree . In this paper we determine whether has a giant component with high probability, essentially imposing no conditions on . We simply insist that the sum of the degrees in which are not 2 is at least for some function going to infinity with . This is a relatively minor technical condition, and when does not satisfy it, both the probability that has a giant component and the probability that has no giant component are bounded away from .
arXiv comment42 pages, to appear in Probability Theory and Related Fields
References in corpus (9)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- The phase transition in the configuration model
- Distances in random graphs with finite variance degrees
- An old approach to the giant component problem
- The switch Markov chain for sampling irregular graphs
- A simple solution to the k-core problem
- The component sizes of a critical random graph with given degree sequence
Cited by in corpus (5)
- Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
- Critical Percolation on Random Networks with Prescribed Degrees
- Percolation on random graphs with a fixed degree sequence
- The spread of fire on a random multigraph
- Random Spatial Networks: Small Worlds without Clustering, Traveling Waves, and Hop-and-Spread Disease Dynamics