TY - JOUR

T1 - On the continuous-time limit of the Barabási–Albert random graph

AU - Pachon, Angelica

AU - Polito, Federico

AU - Sacerdote, Laura

PY - 2020/8/1

Y1 - 2020/8/1

N2 - We prove that, via an appropriate scaling, the degree of a fixed vertex in the Barabási–Albert model appeared at a large enough time converges in distribution to a Yule process. Using this relation we explain why the limit degree distribution of a vertex chosen uniformly at random (as the number of vertices goes to infinity), coincides with the limit distribution of the number of species in a genus selected uniformly at random in a Yule model (as time goes to infinity). To prove this result we do not assume that the number of vertices increases exponentially over time (linear rates). On the contrary, we retain their natural growth with a constant rate superimposing to the overall graph structure a suitable set of processes that we call the planted model and introducing an ad-hoc sampling procedure.

AB - We prove that, via an appropriate scaling, the degree of a fixed vertex in the Barabási–Albert model appeared at a large enough time converges in distribution to a Yule process. Using this relation we explain why the limit degree distribution of a vertex chosen uniformly at random (as the number of vertices goes to infinity), coincides with the limit distribution of the number of species in a genus selected uniformly at random in a Yule model (as time goes to infinity). To prove this result we do not assume that the number of vertices increases exponentially over time (linear rates). On the contrary, we retain their natural growth with a constant rate superimposing to the overall graph structure a suitable set of processes that we call the planted model and introducing an ad-hoc sampling procedure.

KW - Barabási–Albert model

KW - Discrete - and continuous-time models

KW - Planted model

KW - Preferential attachment random graphs

KW - Yule model

U2 - 10.1016/j.amc.2020.125177

DO - 10.1016/j.amc.2020.125177

M3 - Article

AN - SCOPUS:85082683024

VL - 378

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

M1 - 125177

ER -