5. Random Graphs

Erdos-Renyi Random Graph

Given a positive integer $n\in {\mathbb{Z}}_{+}$ and a probability value $p\in [0,1]$, an Erdos-Renyi random graph $\mathcal{G}(n,p)$ is an undirected graph on $n$ vertices, such that each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges is present independently based on some Bernoulli random variable $P\sim \text{Ber}(p(n))$. Let $\lambda >0$ be some constant for which
$p(n)=\lambda \frac{\ln n}{n}.$
If $\lambda <1$, then $\mathbb{P}(\mathcal{G}(n,p)\text{ is connected})\to 0$. However, if $\lambda >1$, then $\mathbb{P}(\mathcal{G}(n,p)\text{ is connected})\to 1$.

Properties

Examples

II. Random Bipartite Graph

Consider a random bipartite graph with $K$ left nodes and $M$ right nodes. Each of the $K\cdot M$ possible edges of this graph is present independently with probability $p$.

A) Find the distribution of the degree of a particular right node.

A) Solution. $D_m$ be the randomly distributed degree of some right node $m$. Since the graph is bipartite, $m$ can only connect to a maximum of $K$ left nodes. Given that each edge is independently distributed As such, $D_m\sim \mathrm{Bin}(K,p)$.

Let

B) Now fix a left node $u$ and right node $v$. Conditioned on the event that the edge $(u,v)$ is present, find the distribution of the degree of $v$.

B) Solution. $D_v\sim \mathrm{Ber}(K,p)$ be the random variable representing the degree of vertex $v$, and let $E\sim \mathrm{Ber}(p)$ be the indicator of whether $(u,v)$ exists. Then,

Let

\mathbb{P}(D_{v}=d_{v} \mid E=1)&=\frac{\mathbb{P}(E=1 \mid D_{v}=d_{v})\mathbb{P}(D_{v}=d_{v})}{\mathbb{P}(E=1)} \
&= \frac{1}{p}\mathbb{P}(E=1 \mid D_{v}=d_{v})\mathbb{P}(D_{v}=d_{v}) \
&= \frac{d_{v}}{pK}\binom{K}{d_{v}}p^{d_{v}}(1-p)
^{K-d_{v}} \
&= \binom{K-1}{d_{v}-1}p^{d_{v}-1}(1-p)^{K-d_{v}},
\end{align}$$

so $D_v\sim \mathrm{Bin}(K-1,p)+1$.

C) Call a right node with degree one a singleton. What is the expected number of singletons in a random bipartite graph?

C) Solution. $v$, and let $D_v\sim \mathrm{Bin}(K,p)$ represent its degree. Then, $\mathbb{P}(D_v=1)=K\cdot p(1-p{)}^{K-1}.$ Since there are $M$ right nodes, the expected number is $\mathbb{E}[S]=M\cdot \mathbb{P}(D_v=1)$ by the theoretical definition of expectation. For a more rigorous definition, use $S={\sum }_{i=1}^K{1}_{\{D_i=1\}}$.

Fix a a right node

D) Find the expected number of left nodes connected to at least one singleton.

D) Solution.

Let $C_{i,j}$ be the indicator of whether the $i$-th left node and the $j$-th right node are connected. We need to calculate

\mathbb{P}(C_{i,j}=1 \mid D_{j}=1)&=\frac{\mathbb{P}(D_{j}=1 \mid C_{i,j}=1)\mathbb{P}(C_{i,j}=1)}{\mathbb{P}(D_{j}=1)} \\ &= \frac{p}{Kp(1-p)^{K-1}}\mathbb{P}(D_{j}=1 \mid C_{i,j}=1), \\ \end{align}$$ where $\mathbb{P}(D_{j}=1 \mid C_{i,j}=1)$ is >[!example] III. Connected Random Graph > >We start with the empty graph on $n$ vertices. Iteratively, we add an undirected edge, chosen uniformly at random from the edges that are not yet present in the graph, until the graph is connected. > >**A)** Suppose that there are currently $k$ connected components in the graph. Let $X_{k}$ be the number of edges we need to add until there are $k−1$ connected components. Show that $\mathbb{E}(X_{k}) \leq \frac{n-1}{k-1}$. >>[!example]- A) Solution. >[!example] IV. Isolated Vertices > >Consider an Erd˝os–Renyi random graph $\mathcal{G}(n,p(n))$, where$n$ is the number of vertices and $p(n)$ is the probability that any specific edge appears in the graph. Let $X_n$ be the number of isolated vertices in $\mathcal{G}(n,p(n))$. Show that >$$\mathbb{E}(X_n) \xrightarrow[n \to \infty]{} \begin{cases} \infty, & p(n) \ll \frac{\ln n}{n} \\ \exp(-c), & p(n) = \frac{\ln n + c}{n} \\ 0, & p(n) \gg \frac{\ln n}{n} \end{cases}$$ > >[!example] V. Subcritical Forest > >Consider a random graph $\mathcal{G}(n,p(n))$ with $p(n) = o(1/n)$ (this is called the **subcritical phase**). > >**A)** Let $X_{n}$ be the number of cycles in the graph. Show that $\mathbb{E}(X_{n}) \to 0$. >>[!example]- A) Solution. >> > >**B)** Show that the probability that $\mathcal{G}(n,p(n))$ is a forest tends to $1$ as $n \to \infty$. A forest is a possibly disconnected graph which contains no cycles. >>[!example]- B) Solution.