Expected global clustering coefficient for Erdős–Rényi graph

Question

What is the expected global clustering coefficient $\mathbb{E}[C_{GC}]$ for the Erdős–Rényi random graph (ER-graph) $\mathcal{G}(n,p)$ (expectation is over the ensemble of all ER-graphs) as $n \rightarrow \infty$ and $p$ fixed?

The global clustering coefficient $C_{GC}$ is defined as

$C_{GC}={\frac {3\times {\mbox{number of triangles}}}{{\mbox{number of connected triplets of vertices}}}}={\frac {{\mbox{number of closed triplets}}}{{\mbox{number of connected triplets of vertices}}}}$.

A connected triplet is defined to be a connected subgraph consisting of three vertices and two edges. A closed triplet is a connected triplet that induces a triangle.

While it is easy to see that the expected mean local clustering coefficient is $p$ (see next section), the expected global clustering coefficient is not identically $p$ for any $n$.

For example, for $n=3$, $C_{GC} = 1$ only when all edges are present (with probability $p^3$) and is otherwise zero (with probability $1-p^3$). Hence the $\mathbb{E}[E_{GC}] = p^3$ when $n=3$.

Computationally, I have found that $\mathbb{E}[C_{GC}]\approx p$ for large $n$.

Is there a way to prove that $\mathbb{E}[C_{GC}]= p$ as $n\rightarrow\infty$?

My current theory is to use Chebyshev's inequality on this, but I haven't tried it out yet.

Expected local clustering coefficient = p

In contrast, it is easy to see that the expected local clustering coefficient $\mathbb{E}[C_i]$ for any node $i$ is $p$.

The local clustering coefficient $C_i$ of node $i$ (for an undirected network) is defined as

$C_i = \frac{\text{number of triangles that contain $i$}}{k_i (k_i-1)/2}$, where $k_i$ is the degree of $i$.

In other words, it is the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibly exist between them.

We have $\mathbb{E}[C_i]=p$ in an ER-graph because the probability for an edge between any neighbours of the node is $p$, independent for any other edge. (For an alternative answer involving more algebra, see here).

Hence the expected mean local clustering coefficient $\mathbb{E}[\sum_i C_i]$ is $p$ for any $n$.

Answer 1

Unless I'm missing something, this is a standard application of the probabilistic method: just show that the expected number of closed triplets is ${n \choose 3}p^3$ the expected number of connected triplets is ${n \choose 3}(3p(1-p)+p^3)$ and then use a Chebyshev bound to show that as $n \rightarrow \infty$ each converges to its mean so that $C_{GC} \rightarrow 3p^3/(3p^2-p^3) = p/(1-p/3)$.

Answer 2

The idea of the previous message is correct but the derivation is wrong. When we calculate the expected number of connected triples and represent it as the sum of expectations over all the triples, we must remember than for every triple $(i, j, k)$ every triangle should be counted three times if it exists (because every connected triple has its leading node, thus, every triangle can be counted three times as it may be considered in three different ways - as a triangle with leading $i$, a triangle with leading $j$, a triangle with leading $k$). Therefore, the expected number of connected triples is ${n \choose 3} (3p^2(1-p) + 3p^3)$. Finally, $C_{GC} \rightarrow 3p^3 / (3p^2(1-p) + 3p^3) = p$.