Plots and simulations

The Preferential Attachment Tree model with Vertex Death (PAVD) is a recursive tree model in which vertices can be killed. Given two sequences b and d with strictly positive and non-negative values, respectively, we construct a sequence (T_n,A_n)_n of trees and alive vertices as follows: 

• Initialise T_1 to be a tree consisting of a single root vertex labelled 1 and A_1={1}.

• Given T_n and A_n, select a vertex i in A_n with probability proportional to 

b(deg_n(i))+d(deg_n(i))

Here, deg_n(i) denotes the in-degree of i in T_n, where we think of edges being directed towards to root.

• Given i and T_n, with probability b(deg_n(i))/(b(deg_n(i))+d(deg_n(i)), introduce a new vertex with label n+1 to the tree, attach n+1 to i by a directed edge, and set A_{n+1}=A_n.

• Otherwise (i.e. with probability d(deg_n(i))/(b(deg_n(i))+d(deg_n(i))), kill vertex i and set A_{n+1}=A_n\{i}.

• Continue this process forever or until all vertex in the tree have died.

Persistence of the maximum degree: Old and Rich vertices

We let O_n=min A_n denote the `oldest' alive vertex in the tree T_n (i.e. the alive vertex with the smallest label), and let I_n=min {v: v in A_n, deg_n(v)=max_{u in A_n} deg_n(u)} denote the `richest' alive vertex in T_n (i.e. the alive vertex with the largest degree). 

We then say Persistence of the maximum degree occurs when 

I_n/O_n is a tight sequence of random variables

Alternatively, we say that Lack of Persistence occurs when

I_n/O_n -> \infty in probability

In current work with Markus Heydenreich we analyse under which conditions persistence or lack of persistence occurs. 

The plot on the top right is a simulation of the case b(i)=i+1 and d(0)=0, d(i)=1 for i\geq 1.

Clearly, the ratio of I_n and O_n is rather large here, and indeed lack of persistence occurs in this case.

The plot on the top left is a simulation of the case b(i)=i+1 and d(i)=1 for i\geq 0. 

Here, I_n and O_n are much closer together, and indeed persistence occurs in this case. 

The curious thing here is that changing a single value of the death sequence d yields radically different behaviour.

The Long-Range Competition process

The long-range competition (LRC) process is a two-type infection process on the complete graph. Here, the vertices of the complete graph are embedded in the d-dimensional torus (d=1 in the GIFs), and the time for either virus (Type 1 or Type 2) to traverse an edge is an exponential random variable, with a rate that depends on the spatial distance in the torus of the vertices the edge connects. To be more precise, the rate to traverse an edge e is λi |e|^(-αi) for Type i, where λ1,λ2>0 and α1,α2 in [0,d) are model parameters, and |e| denotes the length of the edge e, using a norm on the torus. 

In this paper, Neeladri Maitra and I study the scaling limits of the sizes of the infection types, by the time all vertices are infected by one of the two infections types. α2 λ1 λ2The arguments use a coupling of the two infection processes with independent continuous-time branching processes (CTBPs). Our main theoretical contribution is to control the defect between the LRC process and the CTBPs, even when the defect is rather large. 

In the simulations on the right, we see a competition process where d=1, α1=α2=0.5, and  λ1=λ2=1, so that coexistence occurs. In the first GIF on the right, you can see 4 different plots. The LRC process is on the top-left. On the bottom two plots, you see the CTBPs, where the white vertices correspond to birth in these processes that do not occur in the LRC, i.e. the defects of the coupling. In the top right, you see the size of the infections and the size of the defects of either type.

In the GIF on the bottom, you can see an example with 300 vertices, where the edges in the complete graph along which infections take place are omitted for visibility.