We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Adversarial Deletion in a Scale-Free Random Graph Process.
- Authors
ABRAHAM D. FLAXMAN; ALAN M. FRIEZE; JUAN VERA
- Abstract
We study a dynamically evolving random graph which adds vertices and edges using preferential attachment and is ‘attacked by an adversary’. At time $t$, we add a new vertex $x_t$ and $m$ random edges incident with $x_t$, where $m$ is constant. The neighbours of $x_t$ are chosen with probability proportional to degree. After adding the edges, the adversary is allowed to delete vertices. The only constraint on the adversarial deletions is that the total number of vertices deleted by time $n$ must be no larger than $\delta n$, where $\delta$ is a constant. We show that if $\delta$ is sufficiently small and $m$ is sufficiently large then with high probability at time $n$ the generated graph has a component of size at least $n/30$.
- Subjects
RANDOM graphs; GRAPHIC methods; PROBABILITY theory; POSSIBILITY; MATHEMATICS
- Publication
Combinatorics, Probability & Computing, 2007, Vol 16, Issue 2, p261
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548306007681