Networks: Lecture 46.207/14.15: Networks Lecture 4: Erd¨os-Renyi Graphs and Phase Transitions Daron Acemoglu and Asu Ozdaglar MIT September 21, 2009 1Networks: Lecture 4 Outline Phase transitions Connectivity threshold Emergence and size of a giant component An application: contagion and diffusion Reading: Jackson, Sections 4.2.2-4.2.5, and 4.3. 2Networks: Lecture 4 Phase Transitions for Erd¨os-Renyi Model Erd¨os-Renyi model is completely specified by the link formation probability p(n). For a given property A (e.g. connectivity), we define a threshold function t(n) as a function that satisfies: P(property A) → 0 if p(n) t(n) → 0, and P(property A) → 1 if p(n) t(n) → ∞. This definition makes sense for “monotone or increasing properties,” i.e., properties such that if a given network satisfies it, any supernetwork (in the sense of set inclusion) satisfies 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 Erd¨os and Renyi 1959. 3Networks: Lecture 4 Threshold Function for Connectivity Theorem (Erd¨os and Renyi 1961) A threshold function for the connectivity of the Erd¨os and Renyi model is t(n) = logn (n) . To prove this, it is sufficient to show that when p(n) = λ(n) logn (n) with λ(n) 0, we have P(connectivity) 0 (and the converse). → → However, we will show a stronger result: Let p(n) = λ logn (n) . If λ < 1, P(connectivity) → 0, (1) If λ > 1, P(connectivity) → 1. (2) Proof: We first prove claim (1). To show disconnectedness, it is sufficient 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 defined 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−λ , (3) � �n where we use limn ∞ 1 − na = e−a to get the approximation. →Let X = ∑in =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 we use a Poisson approximation (as in the example from last lecture)? No, since the random variables Ii here are dependent. We show that the variance of X is of the same order as its mean. 5�� � Networks: Lecture 4 Proof (Continued) We compute the variance of X , var(X ): =i ij=i = nvar(I1) + n(n − 1)cov(I1, I2) = nq(1 − q) + n(n − 1) E[I1I2] − E[I1]E[I2] , where the second and third equalities follow since the Ii are identically distributed Bernoulli random variables with parameter q (dependent). We have E[I1I2] = P(I1 = 1, I2 = 1) = P(both 1 and 2 are isolated) 2 = (1 − p)2n−3 =(1 q− p) . Combining the preceding two relations, we obtain � 2 � var(X ) = nq(1 − q) + n(n − 1)(1 q− p) − q 2 ∑ 2= nq(1 − q) + n(n − 1) 1 q− pp . var(X ) var(Ii ) +∑ ∑ cov(Ii , Ij ) 6Networks: Lecture 4 Proof (Continued) For large n, we have q 0 [cf. Eq. (3)], or 1 − q 1. Also p 0. Hence, → → → var(X ) nq + n 2 q 2 1 − pp ∼ nq + n 2 q 2 p∼ = nn−λ + λn log(n)n−2λ ∼ nn−λ = E[X ], where a(n) ∼ b(n) denotes ba((nn)) → 1 as n → ∞. This implies that E[X ] ∼ var(X ) ≥ (0 − E[X ])2P(X = 0), and therefore, P(X = 0) ≤ EE[[XX ]] 2 = E[1 X ] → 0. It follows that P(at least one isolated node) 1 and therefore, →P(disconnected) 1 as n ∞, completing the proof. → → 7� � Networks: Lecture 4 Converse We next show claim (2), i.e., if p(n) = λ logn (n) with λ > 1, then P(connectivity) 1, or equivalently P(disconnectivity) 0.→ → From Eq. (4), we have E [X ] = n n−λ 0 for λ > 1.· → This implies probability of having isolated nodes goes to 0. However, we need more to establish connectivity. The event “graph is disconnected” is equivalent to the existence of k nodes without an edge to the remaining nodes, for some k ≤ n/2. We have P({1, . . . , k} not connected to the rest) = (1 − p)k(n−k), and therefore, P(∃ k nodes not connected to the rest) = n (1 − p)k(n−k). k 8Networks: Lecture 4 Converse (Continued) Using the union bound [i.e. P(∪i Ai ) ≤ ∑i P(Ai )], we obtain n/2 � n � P(disconnected graph) ≤ ∑ (1 − p)k(n−k). kk=1 � �k Using Stirling’s formula k! ∼ ke , which implies (kn) ≤ ( nk k )k in the e preceding relation and some (ugly) algebra, we obtain P(disconnected graph) 0, → completing the proof. 9Networks: Lecture 4 Phase Transitions — Connectivity Threshold Figure: Emergence of connectedness: a random network on 50 nodes with p = 0.10. 10Networks: Lecture 4 Giant Component We have shown that when p(n) << logn (n) , the Erd¨os-Renyi graph is disconnected with high probability. In cases for which the network is not connected, the component structure is of interest. We have argued that in this regime the expected number of isolated nodes goes to infinity. This suggests that the Erd¨os-Renyi graph should have an arbitrarily large number of components. We will next argue that the threshold p(n) = λ n plays an important role in the component structure of the graph. For λ < 1, all components of the graph are “small”. For λ > 1, the graph has a unique giant component, i.e., a component that contains a constant fraction of the nodes. 11Networks: Lecture 4 Emergence of the Giant Component—1 λ( ) = We will analyze the component structure in the vicinity of p n nusing a branching process approximation. We assume p(n) = λ λ n . Let B( n, probability λ n ) denote a binomial random variable with n trials and success n. Consider starting from an arbitrary node (node 1 without loss of generality), and exploring the graph. B(n − 1, λ n) B(n − 4, λ n1 )B(n, λ n) B(n, λ )n1 k = 0 k = 1 k = 2 k = 0 k = 1 k = 2 (a) Erdos-Renyi graph process. (b) Branching Pro cess Approx. 12Networks: Lecture 4 Emergence of the Giant Component—2 We first consider the case when λ < 1. Let ZGkand ZBkdenote the number of individuals at stage k for the graph process and the branching process approximation, respectively. In view of the “overcounting” feature of the branching process, we have ZGk≤ ZBkfor all k. From branching