pith. sign in

arxiv: 1610.04588 · v2 · pith:RASUQZCRnew · submitted 2016-10-14 · 🧮 math.CO

Deletion of oldest edges in a preferential attachment graph

classification 🧮 math.CO
keywords edgesvertexgraphdegreeoldestprobabilityaboveadded
0
0 comments X
read the original abstract

We consider a variation on the Barab\'asi-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\geq 2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.