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

DOI10.1002/RSA.20852MaRDI QIDQ5216178zbMATH OpenOpenAlexWikidataFDO

Authors Carina Betken, Hanna Döring, Marcel Ortgiese

Publication date 14 February 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.01341

zbMATH Keywords

Stein's methodcouplingrandom graphsrates of convergencepreferential attachment

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We consider a general preferential attachment model, where the probability that a newly arriving 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, this model can show power law, but also stretched exponential behaviour. Using Stein's method we provide rates of convergence for the total variation distance. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.

Recommendations

• Degree asymptotics with rates for preferential attachment random graphs
• Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
• Preferential attachment random graphs with edge-step functions
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Joint degree distributions of preferential attachment random graphs

Cites work

• scientific article; zbMATH DE number 4080508 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• A spatial web graph model with local influence regions
• Degree asymptotics with rates for preferential attachment random graphs
• Emergence of Scaling in Random Networks
• Fundamentals of Stein's method
• Joint degree distributions of preferential attachment random graphs
• Markov Chains
• On the rate of Poisson convergence
• Poisson approximation for dependent trials
• Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
• Random graphs and complex networks. Volume 1
• Random networks with sublinear preferential attachment: degree evolutions
• Random networks with sublinear preferential attachment: the giant component
• Random trees and general branching processes
• Stein's method and birth-death processes
• The degree sequence of a scale-free random graph process
• Total variation error bounds for geometric approximation
• Vertices of high degree in the preferential attachment tree

Cited in

(8)

• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• Degree evolution in a general growing network
• Consistency of Hill estimators in a linear preferential attachment model
• On a memory game and preferential attachment graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Degree asymptotics with rates for preferential attachment random graphs
• Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
• Asymptotic normality of degree counts in a general preferential attachment model

This page was built for publication: Fluctuations in a general preferential attachment model via Stein's method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216178)