Near critical preferential attachment networks have small giant components

DOI10.1007/S10955-018-2054-5MaRDI QIDQ1633965zbMATH OpenOpenAlexFDO

Authors Maren Eckhoff, Peter Mörters, Marcel Ortgiese

Publication date 21 December 2018

Published in Journal of Statistical Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Barabási-Albert modelkilled branching random walkpercolationpreferential attachmentscale-free networksurvival probability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Applications of branching processes (60J85) Stochastic network models in operations research (90B15)

Abstract: Preferential attachment networks with power law exponent $au>3$ are known to exhibit a phase transition. There is a value $h{o}_{mc}>0$ such that, for small edge densities $holeqh{o}_c$ every component of the graph comprises an asymptotically vanishing proportion of vertices, while for large edge densities $ho>h{o}_c$ there is a unique giant component comprising an asymptotically positive proportion of vertices. In this paper we study the decay in the size of the giant component as the critical edge density is approached from above. We show that the size decays very rapidly, like $exp(-c/sqrtho-h{o}_c)$ for an explicit constant $c>0$ depending on the model implementation. This result is in contrast to the behaviour of the class of rank-one models of scale-free networks, including the configuration model, where the decay is polynomial. Our proofs rely on the local neighbourhood approximations of [Dereich, Morters, 2013] and recent progress in the theory of branching random walks [Gantert, Hu, Shi, 2011].

Recommendations

• Random networks with sublinear preferential attachment: the giant component
• Preferential attachment without vertex growth: emergence of the giant component
• Emergence of the giant component in preferential-attachment growing networks
• Distances in scale free networks at criticality
• The Small Giant Component in Scale-Free Random Graphs

Cites work

• Asymptotics for the survival probability in a killed branching random walk
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 707209 (Why is no real title available?)
• scientific article; zbMATH DE number 3447884 (Why is no real title available?)
• scientific article; zbMATH DE number 975607 (Why is no real title available?)
• Lectures on the Poisson Process
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• Perturbation theory for linear operators.
• Random networks with sublinear preferential attachment: degree evolutions
• Random networks with sublinear preferential attachment: the giant component
• Slow emergence of the giant component in the growing m‐out graph
• Small Deviations in a Space of Trajectories
• Survival probability of the branching random walk killed below a linear boundary
• The phase transition in the uniformly grown random graph has infinite order
• The Small Giant Component in Scale-Free Random Graphs

Cited in

(4)

• Random networks with sublinear preferential attachment: the giant component
• Distances in scale free networks at criticality
• Emergence of the giant component in preferential-attachment growing networks
• Percolation on preferential attachment models

This page was built for publication: Near critical preferential attachment networks have small giant components

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