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

Previewing pages 1, 2, 19, 20 of 20 page document
View Full Document

# Erdos-Renyi Graphs and Phase Transitions

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

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
##### Networks Documents
• 22 pages

• 37 pages

• 73 pages

• 20 pages

• 23 pages

• 38 pages

• 42 pages

• 28 pages

• 22 pages

• 30 pages

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

Unlocking...