Degree limit theorems for P.A. random graphs with edge-steps – 2019

with C. Alves (U. Leipzig) and D. Valesin (U. Groningen) – preprint


In this work we investigate a random graph model that 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 prove convergence theorems and a CLT for the properly scaled maximum degree, as well as the degree of any given vertex. Our results state that under a summability condition, the maximum degree grows linearly in time and sub-linearly if this condition is dropped. Our condition for linearity is sharp when f is a regularly varying function at infinity. Moreover, as a byproduct of our analysis, we prove that there exists true competition for the leadership only during a finite number of steps, i.e., after a certain point a single vertex becomes the one with maximum degree and maintains this predominance forever. These results also relate to Pólya urns with immigration. We also explore our knowledge about the maximum degree in order to understand infectious process over the graphs generated by this model. We show that for some choices of the parameters the graphs are highly susceptible to the spread of infections, which requires only 4 steps to infect a positive fraction of the whole graph

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 )

Google photo

You are commenting using your Google 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: