Preferential attachment without vertex growth: emergence of the giant component
arXiv:1904.11861 · doi:10.1214/20-AAP1610
Abstract
We study the following preferential attachment variant of the classical Erdos-Renyi random graph process. Starting with an empty graph on n vertices, new edges are added one-by-one, and each time an edge is chosen with probability roughly proportional to the product of the current degrees of its endpoints (note that the vertex set is fixed). We determine the asymptotic size of the giant component in the supercritical phase, confirming a conjecture of Pittel from 2010. Our proof uses a simple method: we condition on the vertex degrees (of a multigraph variant), and use known results for the configuration model.
arXiv comment20 pages
References in corpus (16)
- Emergence of scaling in random networks
- Evolution of networks
- The phase transition in the configuration model
- Principles of statistical mechanics of random networks
- Achlioptas process phase transitions are continuous
- Critical window for the configuration model: finite third moment degrees
- Probability asymptotics: notes on notation
- On Wormald's differential equation method
- On edge exchangeable random graphs
- The evolution of subcritical Achlioptas processes
- On the critical probability in percolation
- The phase transition in bounded-size Achlioptas processes
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Popularity-Driven Networking
- Preferential attachment alone is not sufficient to generate scale free random networks
- Slightly subcritical hypercube percolation