Degree asymptotics with rates for preferential attachment random graphs
From MaRDI portal
(Redirected from Publication:1950267)
Abstract: We provide optimal rates of convergence to the asymptotic distribution of the (properly scaled) degree of a fixed vertex in two preferential attachment random graph models. Our approach is to show that these distributions are unique fixed points of certain distributional transformations which allows us to obtain rates of convergence using a new variation of Stein's method. Despite the large literature on these models, there is surprisingly little known about the limiting distributions so we also provide some properties and new representations, including an explicit expression for the densities in terms of the confluent hypergeometric function of the second kind.
The authors study the distribution of the degree of a fixed vertex in two preferential attachment models \(G_n\). Let \(W_{n,i}\) be the degree of vertex \(i\) in \(G_n\). They show the optimal rates of convergence in the Kolmogrov metric of \(W_{n,i}/(\operatorname{E}W^2_{n,i})^{1/2}\) to the asymptotic distribution of its distribution limit \(K_s\) as \(n\) goes to infinity. The distribution function \(K_s\) is defined by its density as \[ k_s(x)=\Gamma(s)\sqrt{\frac{2}{s\pi}}\exp\left(\frac{-x^2}{2s}\right)U\left(s-1,0.5,\frac{x^2}{2s}\right) \] for \(x>0\) and \(s\geq1/2\). Here, \(\Gamma\) and \(U\) represent the gamma function and the confluent hypergeometric function of the second kind, respectively. The main approach is a development of Stein's method for the distribution \(K_s\) using fixed points of distributional transformations.
Recommendations
- Joint degree distributions of preferential attachment random graphs
- Fluctuations in a general preferential attachment model via Stein's method
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
- Degree distribution nearby the origin of a preferential attachment graph
Cites work
- L^1 bounds in normal approximation
- Additive properties of the Dufresne laws and their multivariate extension
- Archimedes, Gauss, and Stein
- Conceptual proofs of L L criteria for mean behavior of branching processes
- Emergence of Scaling in Random Networks
- EXPLOITING THE WAITING TIME PARADOX: APPLICATIONS OF THE SIZE-BIASING TRANSFORMATION
- Fundamentals of Stein's method
- scientific article; zbMATH DE number 50805 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- LENGTH-BIASING, CHARACTERIZATIONS OF LAWS AND THE MOMENT PROBLEM
- Limit distribution of degrees in random family trees
- Limit theorems for triangular urn schemes
- Moments of gamma type and the Brownian supremum process area
- New rates for exponential approximation and the theorems of Rényi and Yaglom
- Normal Approximation by Stein’s Method
- On Gamma Function Inequalities
- Probability. Theory and examples.
- Random graph dynamics
- Stein's method and the zero bias transformation with application to simple random sampling
- The degree sequence of a scale-free random graph process
- The Maximum Degree of the Barabási–Albert Random Tree
- The Structure and Function of Complex Networks
- Total variation error bounds for geometric approximation
- Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument
Cited in
(52)- Multivariate regular variation of discrete mass functions with applications to preferential attachment networks
- Products of normal, beta and gamma random variables: Stein operators and distributional theory
- Stein's method and approximating the quantum harmonic oscillator
- Pólya urns with immigration at random times
- Stein operators for variables form the third and fourth Wiener chaoses
- An algebra of Stein operators
- Large deviations for the degree structure in preferential attachment schemes
- Total variation error bounds for geometric approximation
- A bound on the Wasserstein-2 distance between linear combinations of independent random variables
- Some new Stein operators for product distributions
- Persistence of hubs in growing random networks
- Geometry of weighted recursive and affine preferential attachment trees
- On algebraic Stein operators for Gaussian polynomials
- On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
- \( \gamma \)-variable first-order logic of preferential attachment random graphs
- On nodes of small degrees and degree profile in preferential dynamic attachment circuits
- On rereading Stein's lemma: its intrinsic connection with Cramér-Rao identity and some new identities
- Wasserstein and Kolmogorov error bounds for variance-gamma approximation via Stein's method. I
- Dickman approximation in simulation, summations and perpetuities
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Convergence properties of the degree distribution of some growing network models
- Stein factors for variance-gamma approximation in the Wasserstein and Kolmogorov distances
- Zero bias enhanced Stein couplings
- Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
- Joint vertex degrees in the inhomogeneous random graph model \(\mathcal g(n, \{p_{ij}\})\)
- Parametric Stein operators and variance bounds
- Distance between two random \(k\)-out digraphs, with and without preferential attachment
- Approximating dependent rare events
- A Stein characterisation of the generalized hyperbolic distribution
- On martingale tail sums in affine two-color urn models with multiple drawings
- Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
- Fluctuations in a general preferential attachment model via Stein's method
- Distributional transformations without orthogonality relations
- Joint degree distributions of preferential attachment random graphs
- Asymptotic degree distribution in preferential attachment graph models with multiple type edges
- The asymptotic degree distributions of random fast growth models for treelike networks
- Stein's method for the beta distribution and the Pólya-Eggenberger urn
- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
- A scaling limit for the degree distribution in sublinear preferential attachment schemes
- On a memory game and preferential attachment graphs
- scientific article; zbMATH DE number 7662449 (Why is no real title available?)
- Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
- Asymptotic normality of degree counts in a general preferential attachment model
- A flexible approach for normal approximation of geometric and topological statistics
- Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
- Approximation of stable law in Wasserstein-1 distance by Stein's method
- Dickman approximation of weighted sums of independent random variables in the Kolmogorov distance
- Non-uniform Berry-Esseen bounds for exchangeable pairs with applications to the mean-field classical N-vector models and Jack measures
- Generalized gamma approximation with rates for urns, walks and trees
- Stein characterizations for linear combinations of gamma random variables
- Beta-gamma tail asymptotics
- Growth of preferential attachment random graphs via continuous-time branching processes
This page was built for publication: Degree asymptotics with rates for preferential attachment random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950267)
