Deletion of oldest edges in a preferential attachment graph

Abstract

We consider a variation on the Barabási-Albert random graph process with fixed parameters $m\in \mathbb{N}$ and $1/2<p<1$. With probability $p$ a vertex is added along with $m$ edges, randomly chosen proportional to vertex degrees. With probability $1-p$, the oldest vertex still holding its original $m$ edges loses those edges. It is shown that the degree of any vertex either is zero or follows a geometric distribution. If $p$ is above a certain threshold, this leads to a power law for the degree sequence, while a smaller $p$ gives exponential tails. It is also shown that the graph contains a unique giant component whp if and only if $m\ge 2$.

38 pages. Slightly improved results

References in corpus (1)

• The Anatomy of the Facebook Social Graph

Cited by in corpus (1)

• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities