Distance evolutions in growing preferential attachment graphs

DOI10.1214/22-AAP1789MaRDI QIDQ2108892zbMATH OpenOpenAlexFDO

Authors Joost Jorritsma, Júlia Komjáthy

Publication date 20 December 2022

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

preferential attachmentfirst-passage percolationevolution of graphsweighted-distance evolution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Distance in graphs (05C12)

Abstract: We study the evolution of the graph distance and weighted distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with power-law exponent $auin(2,3)$, sample two vertices $u_t,v_t$ uniformly at random when the graph has $t$ vertices, and study the evolution of the graph distance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in $t^{\prime }geqt$, called the distance evolution. We show that there is a tight strip around the function $4fracloglog(t)-log(log(t^{\prime }/t)vee1)|log(au-2)|vee2$ that the distance evolution never leaves with high probability as $t$ tends to infinity. We extend our results to weighted distances, where every edge is equipped with an i.i.d. copy of a non-negative random variable $L$.

Recommendations

• Weighted distances in scale-free preferential attachment models
• Typical distances in ultrasmall random networks
• Diameters in preferential attachment models
• Preferential attachment random graphs with general weight function
• Scale-free property for degrees and weights in a preferential attachment random graph model

Cites work

• 50 Years of First-Passage Percolation
• A critical point for random graphs with a given degree sequence
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A spatial web graph model with local influence regions
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Diameter in ultra-small scale-free random graphs
• Diameters in preferential attachment models
• Distances and large deviations in the spatial preferential attachment model
• Dynamical fitness models: evidence of universality classes for preferential attachment graphs
• Extensive condensation in a model of preferential attachment with fitness
• First passage percolation on random graphs with finite mean degrees
• Metastability for the contact process on the preferential attachment graph
• Nonextensive condensation in reinforced branching processes
• Nonuniversality of weighted random graphs with infinite variance degree
• On a conditionally Poissonian graph process
• On a random graph evolving by degrees
• On the spread of viruses on the Internet
• Percolation phase transition in weight-dependent random connection models
• Preferential attachment random graphs with edge-step functions
• Preferential attachment without vertex growth: emergence of the giant component
• Random Deletion in a Scale-Free Random Graph Process
• Random graphs and complex networks. Volume 1
• Random graphs.
• Random networks with sublinear preferential attachment: degree evolutions
• Random networks with sublinear preferential attachment: the giant component
• Robust analysis of preferential attachment models with fitness
• Robustness of scale-free spatial networks
• Spatial preferential attachment networks: power laws and clustering coefficients
• The age-dependent random connection model
• The average distances in random graphs with given expected degrees
• The diameter of a scale-free random graph
• The power of choice combined with preferential attachement
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Typical distances in ultrasmall random networks
• Vulnerability of robust preferential attachment networks
• Weighted distances in scale-free configuration models
• Weighted distances in scale-free preferential attachment models

Cited in

(3)

• Weighted distances in scale-free preferential attachment models
• Long-range first-passage percolation on the torus
• Distance between two random \(k\)-out digraphs, with and without preferential attachment

This page was built for publication: Distance evolutions in growing preferential attachment graphs

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