A preferential attachment model for a growing network incorporating deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step $t=1,2,ldots$, with probability $pi_1>0$ a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability $pi_2$ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability $pi_3=1-pi_1-pi_2<1/2$ a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction $p_k$ of vertices with degree $k$, and solving this recursion reveals that, for $pi_3<1/3$, we have $p_ksim k^{-(3-7pi_3)/(1-3pi_3)}$, while, for $pi_3>1/3$, the fraction $p_k$ decays exponentially at rate $(pi_1+pi_2)/2pi_3$. There is hence a non-trivial upper bound for how much deletion the network can incorporate without loosing the power-law behavior of the degree distribution. The analytical results are supported by simulations.
Download