Application: The Erdős-Rényi Random Graph

Videos

No videos for today, although reviewing videos from the last two days might help you with the warmup problems.

Reading

No reading for today’s class, although reviewing readings from

Warmup

An Erdős-Rényi random graph \(G(n, p)\) is a graph on \(n\) nodes where each pair of nodes is connected by an edge with probability \(p\), independently of all other edges. One way to think about this is that I start with \(n\) nodes and no edges. Then, I loop through each pair of nodes \(u\) and \(v\) in the vertex set \(V\) and flip a coin that has probability of heads equal to \(p\). If the coin comes up heads, I add edge \(\{u,v\}\) to the edge set \(E\).

Problem 1

Pick a node \(i\). The degree of node \(i\) in an Erdős-Rényi random graph \(G(n, p)\) is a random variable \(X\) that follows a binomial distribution with success probability \(q\) and number of trials \(k\). Give formulas for \(q\) and \(k\) in terms of the number of nodes \(n\) and the probability \(p\).

Hint: Your formulas should be very simple.

Problem 2

Hint: Use indicator variables and the property that if \(X\) and \(Y\) are independent random variables, then \(\mathrm{var}(X + Y) = \mathrm{var}(X) + \mathrm{var}(Y)\). This implies by induction that if the random variables \(X_1, X_2, \ldots, X_n\) are independent, then \(\mathrm{var}(X_1 + X_2 + \cdots + X_n) = \mathrm{var}(X_1) + \mathrm{var}(X_2) + \cdots + \mathrm{var}(X_n)\).

Problem 3

Throughout this problem, let \(G(n,p)\) be an Erdős-Rényi random graph on \(n\) vertices, where each edge is present with probability \(p\).

Part A

Give a formula for the number of sets of 3 distinct vertices that can be formed from the \(n\) vertices in \(G\). It is not necessary for you to simplify your answer in any way.

Part B

Given a set of three distinct vertices \(u\), \(v\), and \(w\), what is the probability that all the edges \(\{u,v\}\), \(\{v,w\}\), and \(\{u,w\}\) are present in \(G\)?

Part C

A triangle in a graph \(G\) is a set of three vertices \(u\), \(v\), and \(w\) such that all the edges \(\{u,v\}\), \(\{v,w\}\), and \(\{u,w\}\) are present in \(G\). Compute the expected number of triangles in \(G\).

Hint: Let \(X_{uvw}\) be the indicator random variable for the event that the triangle \(\{u,v,w\}\) is present in \(G\).