# Distribution and Variance of Count of Triangles in Random Graph

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$?

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

• Actually fairly straightforward. Well done! I have updated your answer slightly, simplifying the expressions and adding Mathematica code. I also ran my simulation 10k times and obtained an std of 295.37, very close to the expected value. – LBogaardt Apr 11 '18 at 9:17
• Thanks for the edit. I'm glad that the simulation with 10k iterations confirms the answer! – Robin Ryder Apr 11 '18 at 9:25
• I found the original reference, for directed graphs: Holland (1970). A Method for Detecting Structure in Sociometric Data. – LBogaardt May 22 '18 at 11:01

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.

$$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}.$$