4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Law of large number? $\endgroup$ – RaphaelB4 Feb 9 '18 at 11:23
  • 1
    $\begingroup$ The term 'closed triplet' is not usual contemporary graph-theoretic terminology. You therefore should define it. (IIRC, the definitions, in graph-theoretic terminology, are: 'closed triplet'= 'noninduced three-vertex path-graph','connected triplet'='induced three-vertex path-graph'). Also, it is confusing that immediately after the definition of 'global clustering coefficient' you speak of the 'local clusterian coefficient', and without defining it. $\endgroup$ – Peter Heinig Feb 9 '18 at 11:52
  • 1
    $\begingroup$ Thank you, @PeterHeinig. I have added some more explanation and put the local clustering coefficient part to the end. $\endgroup$ – Fabian Ying Feb 9 '18 at 13:34
  • 1
    $\begingroup$ Thanks. Your definition of 'connected triplet' is correct (and equivalent to, but more elegant than, my suggestion.The unusual term 'closed triplet' is still not defined in the OP though (and should be IMHO). One possibility would be to say 'closed triplet' = 'connected triplet which induces a triangle'. $\endgroup$ – Peter Heinig Feb 9 '18 at 14:48
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It would be better to edit the previous message instead of posting a new one $\endgroup$ – David White Aug 19 '18 at 6:03
  • $\begingroup$ David, I know. I tried to comment the previous message first but the system said I didn't have enough reputation for it. $\endgroup$ – Vladimir Stozhkov Aug 19 '18 at 19:32

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.