View Full Document

# Some recent results on scale-free random graphs

View Full Document
View Full Document

3 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

## Access the best Study Guides, Lecture Notes and Practice Exams

Unlocking...
Sign Up

Join to view Some recent results on scale-free random graphs and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?