10
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
4
+50
$\begingroup$

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
| cite | improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – LBogaardt Apr 11 '18 at 9:17
  • 1
    $\begingroup$ Thanks for the edit. I'm glad that the simulation with 10k iterations confirms the answer! $\endgroup$ – Robin Ryder Apr 11 '18 at 9:25
  • $\begingroup$ I found the original reference, for directed graphs: Holland (1970). A Method for Detecting Structure in Sociometric Data. $\endgroup$ – LBogaardt May 22 '18 at 11:01
0
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.