# Some recent results on scale-free random graphs

**View the full content.**View Full Document

0 0 4 views

**Unformatted text preview: **

Some recent results on scale free random graphs Alan Frieze p 1 Random deletion in a scale free random graph Colin Cooper Alan Frieze Juan Vera p 2 Random deletion in a scale free random graph Colin Cooper Alan Frieze Juan Vera Adversarial deletion in a scale free random graph Abie Flaxman Alan Frieze Juan Vera p 2 Random deletion in a scale free random graph Colin Cooper Alan Frieze Juan Vera Adversarial deletion in a scale free random graph Abie Flaxman Alan Frieze Juan Vera A geometric scale free random graph Abie Flaxman Alan Frieze Juan Vera p 2 Random deletion in a scale free random graph We consider a model where edges are added using preferential attachment and vertices edges are deleted randomly p 3 Random deletion in a scale free random graph We consider a model where edges are added using preferential attachment and vertices edges are deleted randomly Same model considered by Chung and Lu p 3 Gt Vt Et denotes the graph at time t Initialisation Start with G1 with vertices x1 and no edges Step t 2 p 4 Gt Vt Et denotes the graph at time t Initialisation Start with G1 with vertices x1 and no edges Step t 2 A Probability 1 0 delete a randomly chosen vertex p 4 Gt Vt Et denotes the graph at time t Initialisation Start with G1 with vertices x1 and no edges Step t 2 A Probability 1 0 delete a randomly chosen vertex B Probability 0 we delete m randomly chosen edges p 4 Gt Vt Et denotes the graph at time t Initialisation Start with G1 with vertices x1 and no edges Step t 2 A Probability 1 0 delete a randomly chosen vertex B Probability 0 we delete m randomly chosen edges C Probability 1 add new vertex xt and m random neighbours w1 wm d w t 1 Pr wi w 2et 1 1 p 4 Gt Vt Et denotes the graph at time t Initialisation Start with G1 with vertices x1 and no edges Step t 2 A Probability 1 0 delete a randomly chosen vertex B Probability 0 we delete m randomly chosen edges C Probability 1 add new vertex xt and m random neighbours w1 wm d w t 1 Pr wi w 2et 1 1 D Probability 1