Near critical preferential attachment networks have small giant components

Maren Eckhoff, Peter Morters, Marcel Ortgiese

Research output: Contribution to journalArticle

9 Downloads (Pure)

Abstract

Preferential attachment networks with power law exponent τ> 3 are known to exhibit a phase transition. There is a value ρ c> 0 such that, for small edge densities ρ≤ ρ c every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities ρ> ρ c there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like exp(-c/ρ-ρc) for an explicit constant c> 0 depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of Dereich and Mörters (Ann Probab 41(1):329–384, 2013) and recent progress in the theory of branching random walks (Gantert et al. in Ann Inst Henri Poincaré Probab Stat 47(1):111–129, 2011).

Original languageEnglish
Pages (from-to)663-703
Number of pages41
JournalJournal of Statistical Physics
Volume173
Issue number3-4
Early online date14 May 2018
DOIs
Publication statusPublished - 1 Nov 2018

Fingerprint

Giant Component
Preferential Attachment
attachment
Decay
proportion
apexes
Proportion
decay
Branching Random Walk
Scale-free Networks
random walk
Power Law
polynomials
Phase Transition
Exponent
exponents
Model
Configuration
Polynomial
Approximation

Keywords

  • Barabási-Albert model
  • Killed branching random walk
  • Percolation
  • Preferential attachment
  • Scale-free network
  • Survival probability

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Cite this

Near critical preferential attachment networks have small giant components. / Eckhoff, Maren; Morters, Peter; Ortgiese, Marcel.

In: Journal of Statistical Physics, Vol. 173, No. 3-4, 01.11.2018, p. 663-703.

Research output: Contribution to journalArticle

@article{41e80eabd0944fa1b375b7fec223f899,
title = "Near critical preferential attachment networks have small giant components",
abstract = "Preferential attachment networks with power law exponent τ> 3 are known to exhibit a phase transition. There is a value ρ c> 0 such that, for small edge densities ρ≤ ρ c every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities ρ> ρ c there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like exp(-c/ρ-ρc) for an explicit constant c> 0 depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of Dereich and M{\"o}rters (Ann Probab 41(1):329–384, 2013) and recent progress in the theory of branching random walks (Gantert et al. in Ann Inst Henri Poincar{\'e} Probab Stat 47(1):111–129, 2011).",
keywords = "Barab{\'a}si-Albert model, Killed branching random walk, Percolation, Preferential attachment, Scale-free network, Survival probability",
author = "Maren Eckhoff and Peter Morters and Marcel Ortgiese",
year = "2018",
month = "11",
day = "1",
doi = "10.1007/s10955-018-2054-5",
language = "English",
volume = "173",
pages = "663--703",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer New York",
number = "3-4",

}

TY - JOUR

T1 - Near critical preferential attachment networks have small giant components

AU - Eckhoff, Maren

AU - Morters, Peter

AU - Ortgiese, Marcel

PY - 2018/11/1

Y1 - 2018/11/1

N2 - Preferential attachment networks with power law exponent τ> 3 are known to exhibit a phase transition. There is a value ρ c> 0 such that, for small edge densities ρ≤ ρ c every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities ρ> ρ c there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like exp(-c/ρ-ρc) for an explicit constant c> 0 depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of Dereich and Mörters (Ann Probab 41(1):329–384, 2013) and recent progress in the theory of branching random walks (Gantert et al. in Ann Inst Henri Poincaré Probab Stat 47(1):111–129, 2011).

AB - Preferential attachment networks with power law exponent τ> 3 are known to exhibit a phase transition. There is a value ρ c> 0 such that, for small edge densities ρ≤ ρ c every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities ρ> ρ c there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like exp(-c/ρ-ρc) for an explicit constant c> 0 depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of Dereich and Mörters (Ann Probab 41(1):329–384, 2013) and recent progress in the theory of branching random walks (Gantert et al. in Ann Inst Henri Poincaré Probab Stat 47(1):111–129, 2011).

KW - Barabási-Albert model

KW - Killed branching random walk

KW - Percolation

KW - Preferential attachment

KW - Scale-free network

KW - Survival probability

UR - http://www.scopus.com/inward/record.url?scp=85056568533&partnerID=8YFLogxK

U2 - 10.1007/s10955-018-2054-5

DO - 10.1007/s10955-018-2054-5

M3 - Article

VL - 173

SP - 663

EP - 703

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 3-4

ER -