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

DOI10.1002/RSA.20852zbMATH Open1433.05273arXiv1805.01341OpenAlexW2962961994WikidataQ128107153 ScholiaQ128107153MaRDI QIDQ5216178FDOQ5216178

Authors: Carina Betken, Hanna Döring, Marcel Ortgiese 

Publication date: 14 February 2020

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• Degree evolution in a general growing network
• On a memory game and preferential attachment graphs
• Consistency of Hill estimators in a linear preferential attachment model
• 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)