Distance evolutions in growing preferential attachment graphs

DOI10.1214/22-AAP1789zbMATH Open1504.05080arXiv2003.08856OpenAlexW3011319091MaRDI QIDQ2108892FDOQ2108892

Authors: Joost Jorritsma, Júlia Komjáthy 

Publication date: 20 December 2022

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

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$.

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

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

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)

Cites Work

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

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)