Growth of preferential attachment random graphs via continuous-time branching processes

DOI10.1007/S12044-008-0036-2MaRDI QIDQ949467zbMATHOpenAlexFDO

Authors Sunder Sethuraman, K. B. Athreya, Arka P. Ghosh

Publication date 21 October 2008

Published in Proceedings of the Indian Academy of Sciences. Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

preferential attachmentscale-free graphspower-law degree distributionRandom graph process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Discrete-time Markov processes on general state spaces (60J05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Vertex degrees (05C07)

Abstract: A version of ``preferential attachment random graphs, corresponding to linear ``weights with random ``edge additions, which generalizes some previously considered models, is studied. This graph model is embedded in a continuous-time branching scheme and, using the branching process apparatus, several results on the graph model asymptotics are obtained, some extending previous results, such as growth rates for a typical degree and the maximal degree, behavior of the vertex where the maximal degree is attained, and a law of large numbers for the empirical distribution of degrees which shows certain ``scale-free or ``power-law behaviors.

Recommendations

• Random graphs associated to some discrete and continuous time preferential attachment models
• Preferential attachment random graphs with general weight function
• Growing random graphs with a preferential attachment structure
• Random trees and general branching processes
• Degree asymptotics with rates for preferential attachment random graphs

Cites work

• scientific article; zbMATH DE number 3816788 (Why is no real title available?)
• scientific article; zbMATH DE number 2119076 (Why is no real title available?)
• scientific article; zbMATH DE number 3272753 (Why is no real title available?)
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• A general model of web graphs
• A survey of random processes with reinforcement
• Complex graphs and networks
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Emergence of Scaling in Random Networks
• Measure Theory and Probability Theory
• ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
• On random trees
• On the equivalence of conditions on a branching process in continuous time and on its offspring distribution
• Random trees and general branching processes
• Statistical mechanics of complex networks
• The Maximum Degree of the Barabási–Albert Random Tree
• The Structure and Function of Complex Networks
• The degree sequence of a scale-free random graph process

Cited in

(29)

• Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point
• A preferential attachment process approaching the Rado graph
• Random networks with heterogeneous reciprocity
• Random networks with preferential growth and vertex death
• Growing random graphs with a preferential attachment structure
• Preferential attachment processes approaching the Rado multigraph
• Local weak convergence for PageRank
• Random graphs associated to some discrete and continuous time preferential attachment models
• A continuous-time N -interaction random graph model
• On Bollobás‐Riordan random pairing model of preferential attachment graph
• Large deviations for the degree structure in preferential attachment schemes
• Competing growth processes with random growth rates and random birth times
• Preferential attachment random graphs with general weight function
• Twitter event networks and the superstar model
• Asymptotic behavior and distributional limits of preferential attachment graphs
• A continuous-time network evolution model describing 3-interactions
• The dynamics of power laws: fitness and aging in preferential attachment trees
• A scaling limit for the degree distribution in sublinear preferential attachment schemes
• Degree growth rates and index estimation in a directed preferential attachment model
• Asymptotic dependence of in- and out-degrees in a preferential attachment model with reciprocity
• A phase transition for preferential attachment models with additive fitness
• Large deviations for the leaves in some random trees
• Supercritical percolation on large scale-free random trees
• From trees to graphs: collapsing continuous-time branching processes
• Consistency of Hill estimators in a linear preferential attachment model
• Large degrees in scale-free inhomogeneous random graphs
• Nongrowing preferential attachment random graphs
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Condensation phenomena in preferential attachment trees with neighbourhood influence

This page was built for publication: Growth of preferential attachment random graphs via continuous-time branching processes

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