# Growing networks with preferential addition and deletion of edges

arXiv: https://arxiv.org/abs/1509.07032 · HTML: https://mlsanity.com/paper/1509.07032/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2015.

## Built on by (most cited first, 1 of 1)

- [Errors are Robustly Tamed in Cumulative Knowledge Processes](https://mlsanity.com/paper/2309.05638/) (2023)

## Abstract (arXiv)

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 π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 π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 π3=1-π1-π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 pk of vertices with degree k, and solving this recursion reveals that, for π3<1/3, we have pk~ k-(3-7π3)/(1-3π3), while, for π3>1/3, the fraction pk decays exponentially at rate (π1+π2)/2π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.