Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution

DOI10.1239/AAP/1377868543zbMATH Open1273.05205arXiv1208.1558OpenAlexW2963364593MaRDI QIDQ2856041FDOQ2856041

Authors: Nathan Ross 

Publication date: 23 October 2013

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: For a family of linear preferential attachment graphs, we provide rates of convergence for the total variation distance between the degree of a randomly chosen vertex and an appropriate power law distribution as the number of vertices tends to infinity. Our proof uses a new formulation of Stein's method for the negative binomial distribution, which stems from a distributional transformation that has the negative binomial distributions as the only fixed points.

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

Recommendations

• Fluctuations in a general preferential attachment model via Stein's method
• Degree asymptotics with rates for preferential attachment random graphs
• scientific article; zbMATH DE number 5732563
• Degree distribution nearby the origin of a preferential attachment graph
• Joint degree distributions of preferential attachment random graphs

zbMATH Keywords

power lawrandom graphStein's methodnegative binomial distributionpreferential attachmentdistributional transformation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Vertex degrees (05C07)

Cites Work

• Emergence of Scaling in Random Networks
• Stein's method and the zero bias transformation with application to simple random sampling
• Normal Approximation by Stein’s Method
• An expansion for self-interacting random walks
• The degree sequence of a scale-free random graph process
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of Stein's method
• The Maximum Degree of the Barabási–Albert Random Tree
• The degree sequences and spectra of scale-free random graphs
• Bounds on tail probabilities of discrete distributions
• Degree asymptotics with rates for preferential attachment random graphs
• New rates for exponential approximation and the theorems of Rényi and Yaglom
• Total variation error bounds for geometric approximation
• Stein's method and birth-death processes
• Popularity based random graph models leading to a scale-free degree sequence
• Random trees and general branching processes
• Stein's method for geometric approximation
• Negative binomial approximation with Stein's method
• Archimedes, Gauss, and Stein
• Exact Kolmogorov and total variation distances between some familiar discrete distributions

Cited In (12)

• Joint degree distributions of preferential attachment random graphs
• Consistency of Hill estimators in a linear preferential attachment model
• Nonstandard regular variation of in-degree and out-degree in the preferential attachment model
• A scaling limit for the degree distribution in sublinear preferential attachment schemes
• Scale-free and power law distributions via fixed points and convergence of (thinning and conditioning) transformations
• On nodes of small degrees and degree profile in preferential dynamic attachment circuits
• Degree asymptotics with rates for preferential attachment random graphs
• Generalized gamma approximation with rates for urns, walks and trees
• Fluctuations in a general preferential attachment model via Stein's method
• Tauberian theory for multivariate regularly varying distributions with application to preferential attachment networks
• Some new bounds and approximations on tail probabilities of the Poisson and other discrete distributions
• Pólya urns with immigration at random times

This page was built for publication: Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution

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