Fluctuations in a general preferential attachment model via Stein's method

Carina Betken, Hanna Döring, Marcel Ortgiese

Research output: Contribution to journalArticle

Abstract

We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.
Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalRandom Structures and Algorithms
Early online date2 Apr 2019
DOIs
Publication statusE-pub ahead of print - 2 Apr 2019

Fingerprint

Stein's Method
Preferential Attachment
Fluctuations
Vertex of a graph
Limiting Distribution
Markov processes
Total Variation Distance
Stationary Distribution
Model
Markov chain
Power Law
Rate of Convergence
Directly proportional
Generator
Converge

Keywords

  • random graphs
  • Preferential attachment
  • Stein's method
  • coupling
  • rates of convergence

Cite this

Fluctuations in a general preferential attachment model via Stein's method. / Betken, Carina; Döring, Hanna; Ortgiese, Marcel.

In: Random Structures and Algorithms, 02.04.2019, p. 1-23.

Research output: Contribution to journalArticle

@article{6105b2c5fe3041639ad81eae79e410f9,
title = "Fluctuations in a general preferential attachment model via Stein's method",
abstract = "We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.",
keywords = "random graphs, Preferential attachment, Stein's method, coupling, rates of convergence",
author = "Carina Betken and Hanna D{\"o}ring and Marcel Ortgiese",
year = "2019",
month = "4",
day = "2",
doi = "10.1002/rsa.20852",
language = "English",
pages = "1--23",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Inc.",

}

TY - JOUR

T1 - Fluctuations in a general preferential attachment model via Stein's method

AU - Betken, Carina

AU - Döring, Hanna

AU - Ortgiese, Marcel

PY - 2019/4/2

Y1 - 2019/4/2

N2 - We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.

AB - We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.

KW - random graphs

KW - Preferential attachment

KW - Stein's method

KW - coupling

KW - rates of convergence

U2 - 10.1002/rsa.20852

DO - 10.1002/rsa.20852

M3 - Article

SP - 1

EP - 23

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

ER -