TY - JOUR

T1 - Adversarial deletion in a scale-free random graph process

AU - Flaxman, A.D.

AU - Frieze, A.M.

AU - Vera, J.

PY - 2007

Y1 - 2007

N2 - 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 xt and m random edges incident with xt, where m is constant. The neighbours of xt 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 δn, where δ is a constant. We show that if δ 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.

AB - 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 xt and m random edges incident with xt, where m is constant. The neighbours of xt 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 δn, where δ is a constant. We show that if δ 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.

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-33847109724&partnerID=MN8TOARS

U2 - 10.1017/S0963548306007681

DO - 10.1017/S0963548306007681

M3 - Article

VL - 16

SP - 261

EP - 270

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 2

ER -