Spread of Infection over P.A. random graphs with edge insertion – 2021

with C. Alves (Alfréd Rényi Institute of Mathematics) – accepted for publication at ALEA.


In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph. To prove this result, we rely on a quantitative lower bound for the maximum degree that might be of independent interest.

Find the PDF file at


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: