MIT 6 207 - Erdos-Renyi Graphs and Phase Transitions (20 pages)

Previewing pages 1, 2, 19, 20 of 20 page document View the full content.
View Full Document

Erdos-Renyi Graphs and Phase Transitions



Previewing pages 1, 2, 19, 20 of actual document.

View the full content.
View Full Document
View Full Document

Erdos-Renyi Graphs and Phase Transitions

32 views

Lecture Notes


Pages:
20
School:
Massachusetts Institute of Technology
Course:
6 207 - Networks

Unformatted text preview:

6 207 14 15 Networks Lecture 4 Erdo s Renyi Graphs and Phase Transitions Daron Acemoglu and Asu Ozdaglar MIT September 21 2009 1 Networks Lecture 4 Outline Phase transitions Connectivity threshold Emergence and size of a giant component An application contagion and di usion Reading Jackson Sections 4 2 2 4 2 5 and 4 3 2 Networks Lecture 4 Phase Transitions for Erdo s Renyi Model Erdo s Renyi model is completely speci ed by the link formation probability p n For a given property A e g connectivity we de ne a threshold function t n as a function that satis es P property A 0 P property A 1 p n 0 and t n if if p n t n This de nition makes sense for monotone or increasing properties i e properties such that if a given network satis es it any supernetwork in the sense of set inclusion satis es it When such a threshold function exists we say that a phase transition occurs at that threshold Exhibiting such phase transitions was one of the main contributions of the seminal work of Erdo s and Renyi 1959 3 Networks Lecture 4 Threshold Function for Connectivity Theorem Erdo s and Renyi 1961 A threshold function for the connectivity of the Erdo s log n and Renyi model is t n n log n To prove this it is su cient to show that when p n n n n 0 we have P connectivity 0 and the converse with log n However we will show a stronger result Let p n n If 1 P connectivity 0 1 If 1 P connectivity 1 2 Proof We rst prove claim 1 To show disconnectedness it is su cient to show that the probability that there exists at least one isolated node goes to 1 4 Networks Lecture 4 Proof Continued Let Ii be a Bernoulli random variable de ned as 1 if node i is isolated Ii 0 otherwise We can write the probability that an individual node is isolated as q P Ii 1 1 p n 1 e pn e log n n n where we use limn 1 na e a to get the approximation 3 Let X ni 1 Ii denote the total number of isolated nodes Then we have E X n n 4 For 1 we have E X We want to show that this implies P X 0 0 In general this is not true Can



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Erdos-Renyi Graphs and Phase Transitions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Erdos-Renyi Graphs and Phase Transitions 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?