Networks: Lecture 3Introduction6.207/14.15: Networks Lecture 3: Erd¨os-Renyi graphs and Branching processes Daron Acemoglu and Asu Ozdaglar MIT September 16, 2009 1Networks: Lecture 3 Introduction Outline Erd¨os-Renyi random graph model Branching processes Phase transitions and threshold function Connectivity threshold Reading: Jackson, Sections 4.1.1 and 4.2.1-4.2.3. 2� ���������� Networks: Lecture 3 Introduction Erd¨os-Renyi Random Graph Model We use G (n, p) to denote the undirected Erd¨os-Renyi graph. Every edge is formed with probability p ∈ (0, 1) independently of every other edge. Let Iij ∈ {0, 1} be a Bernoulli random variable indicating the presence of edge {i, j }. For the Erd¨os-Renyi model, random variables Iij are independent and 1 with probability p,=Iij 0 with probability 1 − p. E[number of edges] = E [∑ Iij ] = n(n2−1) p Moreover, using weak law of large numbers, we have for all α > 0 n(n − 1) 2 n(n − 1) 2∑ Iij −P ≥ α 0,p → as n ∞. Hence, with this random graph model, the number of edges is a →random variable, but it is tightly concentrated around its mean for large n. 3Networks: Lecture 3 Introduction Properties of Erd¨os-Renyi model Recall statistical properties of networks: Degree distributions Clustering Average path length and diameter For Erd¨os-Renyi model: Let D be a random variable that represents the degree of a node. D is a binomial random variable with E[D] = (n − 1)p, i.e., P(D = d) = (n−1)pd (1 − p)n−1−d .d Keeping the expected degree constant as n ∞, D can be →approximated with a Poisson random variable with λ = (n − 1)p, e−λλd P(D = d) = ,d! hence the name Poisson random graph model. This degree distribution falls off faster than an exponential in d, hence it is not a power-law distribution. Individual clustering coefficient≡ Cli (p) = p. Interest in p(n) 0 as n ∞, implying Cli (p) 0.→ → →Diameter:? 4Networks: Lecture 3 Introduction Other Properties of Random Graph Models Other questions of interest: Does the graph have isolated nodes? cycles? Is it connected? For random graph models, we are interested in computing the probabilities of these events, which may be intractable for a fixed n. Therefore, most of the time, we resort to an asymptotic analysis, where we compute (or bound) these probabilities as n ∞.→ Interestingly, often properties hold with either a probability approaching 1 or a probability approaching 0 in the limit. Consider an Erd¨os-Renyi model with link formation probability p(n) (again interest in p(n) → 0 as n → ∞). 50 100 150 200 250 300 350 400 450 5000.010.020.030.040.050.060.070.080.090.10.11np(n)p(n) =lo g nnP (co nn ected) ≈ 0P (c on n ected) ≈ 1The graph experiences a phase transition as a function of graph parameters (also true for many other properties). 5�Networks: Lecture 3 Introduction Branching Processes To analyze phase transitions, we will make use of branching processes. The Galton-Watson Branching process is defined as follows: Start with a single individual at generation 0, Z0 = 1. Let Zk denote the number of individuals in generation k. Let ξ be a nonnegative discrete random variable with distribution pk , i.e., P(ξ = k) = pk , E[ξ] = µ, var (ξ) = 0. Each individual has a random number of children in the next generation, which are independent copies of the random variable ξ. This implies that Z1 Z1 = ξ, Z2 = ∑ ξ(i )(sum of random number of rvs). i=1 and therefore, E[Z1] = µ, E[Z2] = E[E[Z2 | Z1] ] = E[µZ1] = µ 2 , nand E[ Zn] = µ . 6Networks: Lecture 3 Introduction Branching Processes (Continued) Let Z denote the total number of individuals in all generations, Z n=1 Zn.= ∑∞ We consider the events Z < ∞ (extinction) and Z = ∞ (survive forever). We are interested in conditions and with what probabilities these events occur. Two cases: Subcritical (µ < 1) and supercritical (µ > 1) Subcritical: µ < 1 Since E[Zn] = µn, we have � ∞ � ∞ � � 1 E[Z ] = E ∑ Zn = ∑ E Zn = < ∞, n=1 n=1 1 − µ (some care is needed in the second equality). This implies that Z < ∞ with probability 1 and P(extinction) = 1. 7Networks: Lecture 3 IntroductionBranching Processes (Continued)Supercritical: µ > 1Recall p0= P(ξ = 0). If p0= 0, then P(extinction) = 0.Assume p0> 0.We have ρ = P(extinction) ≥ P(Z1= 0) = p0> 0.We can write the following fixed-point equation for ρ:ρ =∞∑k=0pkρk= E[ρξ] ≡ Φ(ρ).We have Φ(0) = p0(using convention 00= 1) and Φ(1) = 1Φ is a convex function (Φ00(ρ) 0 for all ρ [0, 1]), and Φ0(1) = µ > 1.≥ ∈0 0.2 0.4 0.6 0.8 100.20.40.60.81 ρ µρ*Φ ( ρ* )= ρ* p0Figure: The generating function Φ has a unique fixed point ρ∗∈ [0, 1).8Networks: Lecture 3 Introduction 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. 9����� Networks: Lecture 3 Introduction Phase Transition Example Define property A as A = {number of edges > 0}. We are looking for a threshold for the emergence of the first edge. Recall E[number of edges] = n(n2−1) p(n) ≈ n22 p(n) . Assume 2p/(nn) 2 0 as n ∞. Then, E[number of edges] 0, which implies → → → that P(number of edges > 0) 0.→ Assume next that p(n) ∞ as n ∞ . Then, E[number of edges] ∞.2/n2 → → → This does not in general imply that P(number of edges > 0) 1.→ Here it follows because the number of edges can be approximated by a Poisson distribution (just like the degree distribution), implying that P(number of edges = 0) = e−λλk k! = e−λ . k=0 Since the mean number of edges, given by λ, goes to infinity as n ∞, this implies that P(number of edges > 0) 1. → → 10Networks: Lecture 3 Introduction Phase Transitions Hence, the function t(n)