Distribution and Variance of Count of Triangles in Random Graph

Question

Consider an Erdos-Renyi random graph $G=(V(n),E(p))$. The set of $n$ vertices $V$ is labelled by $V = \{1,2,\ldots,n\}$. The set of edges $E$ is constructed by a random process.

Let $p$ be a probability $0<p<1$, then each unordered pair $\{i,j\}$ of vertices ($i \neq j$) occurs as an edge in $E$ with probability $p$, independently of the other pairs.

A triangle in $G$ is an unordered triple $\{i,j,k\}$ of distinct vertices, such that $\{i,j\}$, $\{j,k\}$, and $\{k,i\}$ are edges in $G$.

The maximum number of possible triangles is $\binom{n}{3}$. Define the random variable $X$ to be the observed count of triangles in the graph $G$.

The probability that three links are simultaneously present is $p^3$. Therefore, the expected value of $X$ is given by $E(X) = \binom{n}{3} p^3$. Naively, one may guess that the variance is given by $E(X^2) =\binom{n}{3} p^3 (1-p^3)$, but this is not the case.

The following Mathematica code simulates the problem:

n=50;
p=0.6;
t=100;
myCounts=Table[Length[FindCycle[RandomGraph[BernoulliGraphDistribution[n,p]],3,All]],{tt,1,t}];
N[Mean[myCounts]] // 4216. > similar to expected mean
Binomial[n,3]p^3 // 4233.6
N[StandardDeviation[myCounts]] // 262.078 > not similar to "expected" std
Sqrt[Binomial[n,3](p^3)(1-p^3)] // 57.612
Histogram[myCounts]

What is the variance of $X$?

Answer 1

Let $Y_{ijk}=1$ iff $\{i, j, k\}$ form a triangle. Then $X=\sum_{i, j, k}Y_{ijk}$ and each $Y_{ijk}\sim Bernoulli(p^3)$. This is what you have used to calculate the expected value.

For the variance, the issue is that the $Y_{ijk}$ are not independent. Indeed, write $$X^2=\sum_{i, j, k}\sum_{i', j', k'}Y_{ijk}Y_{i'j'k'}.$$ We need to compute $E[Y_{ijk}Y_{i'j'k'}]$, which is the probability that both triangles are present. There are several cases:

• If $\{i,j,k\}=\{i',j',k'\}$ (same 3 vertices) then $E[Y_{ijk}Y_{i'j'k'}]=p^3$. There will be $\binom{n}{3}$ such terms in the double sum.
• If the sets $\{i,j,k\}$ and $\{i',j',k'\}$ have exactly 2 elements in common, then we need 5 edges present to get the two triangles, so that $E[Y_{ijk}Y_{i'j'k'}]=p^5$. there will be $12 \binom{n}{4}$ such terms in the sum.
• If the sets $\{i,j,k\}$ and $\{i',j',k'\}$ have 1 element in common, then we need 6 edges present, so that $E[Y_{ijk}Y_{i'j'k'}]=p^6$. There will be $30 \binom{n}{5}$ such terms in the sum.
• If the sets $\{i,j,k\}$ and $\{i',j',k'\}$ have 0 element in common, then we need 6 edges present, so that $E[Y_{ijk}Y_{i'j'k'}]=p^6$. There will be $20 \binom{n}{6}$ such terms in the sum.

To verify that we have covered all cases, note that the sum adds up to $\binom{n}{3}^{2}$.

$$\binom{n}{3} + 12 \binom{n}{4} + 30 \binom{n}{5} + 20 \binom{n}{6} = \binom{n}{3}^{2}$$

Remembering to subtract the square of the expected mean, putting this all together gives:

$$E[X^2] - E[X]^2 = \binom{n}{3} p^3 + 12 \binom{n}{4} p^5 + 30 \binom{n}{5} p^6 + 20 \binom{n}{6} p^6 - \binom{n}{3}^2 p^6$$

Using the same numerical values as your example, the following R code calculates the standard deviation, which is reasonably close to the value of 262 from your simulation.

n=50
p=0.6
sqrt(choose(n, 3)*p^3+choose(n, 2)*(n-2)*(n-3)*p^5+(choose(n, 3)*choose(n-3, 3)+n*choose(n-1, 2)*choose(n-3, 2))*p^6-4233.6^2)
298.7945

The following Mathematica code also calculates the standard deviation, which gives the same result.

mySTD[n_,p_]:=Sqrt[Binomial[n,3]p^3+12Binomial[n,4]p^5+30 Binomial[n,5]p^6+20Binomial[n,6]p^6-(Binomial[n,3]p^3)^2]
mySTD[50,0.6] // gives 298.795

Answer 2

I provide a slightly different approach of deriving $\mathrm{X}^{2}$.

With the same case distinction as Robin Ryder did:

• If $\{i, j, k\} = \{i', j', k'\}$ i.e. the 3 vertices are the same, thus we must pick 3 vertices out of n possible $\Rightarrow \binom{n}{3}$. We must have 3 edges present $\Rightarrow \mathrm{p}^{3}$. Combined: $\binom{n}{3}\mathrm{p}^{3}$

• If $\{i, j, k\}$ and $\{i', j', k'\}$ have two vertices in common, that means $\exists v \in \{i, j, k\}$ for which $v \notin \{i', j', k'\}$ and vice versa (each triangle has one vertex that is not part of the other triangle). W.l.o.g. imagine $v = k$ and $v' = k'$ are the mentioned disjunct vertices and $i$ = $i'$, $j$ = $j'$. To achieve $i$ = $i'$, $j$ = $j'$, we must pick the same two vertices out of n possible $\Rightarrow \binom{n}{2}$. For $k \neq k'$ we must pick two more out of the vertices that are left. First one: $(n-2)$ and second one: $(n-3)$. Because the edge $\{i, j\}$ and $\{i', j'\}$ is the same, we must have 5 edges present $\Rightarrow \mathrm{p}^{5}$. Combined: $\binom{n}{2}(n-2)(n-3)\mathrm{p}^{5}$

• If $\{i, j, k\}$ and $\{i', j', k'\}$ have just one vertex in common, then 4 are disjunct. Imagine, w.l.o.g., that $i$ = $i'$. That means, out of n possible vertices, we must pick 1 $\Rightarrow n$. For the triangle $\{i, j, k\}$ we pick 2 vertices out of the remaining $(n-1) \Rightarrow \binom{n-1}{2}$. For the triangle $\{i', j', k'\}$ we pick 2 out of the remaining $(n-3) \Rightarrow \binom{n-3}{2}$, this is due to the assumption that $j'\notin\{i, j, k\}$ and $k'\notin\{i, j, k\}$. Because we only have one vertex in common, we must have 6 edges present $\Rightarrow \mathrm{p}^{6}$. Combined: $n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6}$

• For the last case: If $\{i, j, k\}$ and $\{i', j', k'\}$ have no vertex in common, then the 2 triangles are disjunct. We pick the first triangle, 3 vertices out of n possible $\Rightarrow \binom{n}{3}$. And the second triangle, 3 vertices out of $(n-3)$ remaining $\Rightarrow \binom{n-3}{3}$. The triangles are disjunct, i.e. they share no edges and vertices, thus 6 edges must be present $\Rightarrow \mathrm{p}^{6}$. Combined: $\binom{n}{3}\binom{n-3}{3}\mathrm{p}^{6}$

As in Robin Ryder's approach, we can also verify that:

$\binom{n}{3} + \binom{n}{2}(n-2)(n-3) + n\binom{n-1}{2}\binom{n-3}{2} + \binom{n}{3}\binom{n-3}{3} = \mathrm{\binom{n}{3}}^{2}$ holds.

This leads to:

$Var[X] = E[\mathrm{X}^{2}] - \mathrm{E[X]}^{2} = \binom{n}{3}\mathrm{p}^{3} + \binom{n}{2}(n-2)(n-3)\mathrm{p}^{5} + n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6} + \binom{n}{3}\binom{n-3}{3}\mathrm{p}^{6} - \mathrm{\binom{n}{3}}^{2}\mathrm{p}^{6}.$