Clustering Formulas for Networks

Question

Consider an undirected, unweighted graph 𝐺=(𝑉,𝐸). I want to compute the clustering coefficient of each node. In the publicly available lecture from stanford, the following formula for computing the clustering coefficient $e_v$ for a node $v$ is given as:

$$e_v = \frac {\#\text{edges among neighboring nodes}} {\#\text {node pairs among } k_v \text {neighboring nodes}} = \frac {\#\text{edges among neighboring nodes}}{{k_v \choose 2}} \in [0,1]$$

while in the documentation of the library networkX for python, defines the clustering coefficient as follows:

$$c_u = \frac {2T(u)} {deg(u) (deg(u)-1)}$$

where $T(u)$ is the number of triangles through node $u$ and $𝑑𝑒𝑔(𝑢)$ is the degree of $𝑢$.

I calculated a few examples (Erdös-Renyi Networks) and both gave the same result for every node in the example graphs. Can somebody give me the intuition behind that observation?

Answer 1

1. $\#\text{edges among neighboring nodes}$ is the same as $T(v)$ since a triangle through $v$ means that the side opposite to $v$ in the triangle is incident on two neighboring nodes.
2. $k_{v} = deg(v)$. Therefore, ${k_v \choose 2} = \frac{k_{v}(k_{v}-1)}{2} = \frac{deg(v)(deg(v)-1)}{2}$

Therefore, $$e_v = \frac {\#\text{edges among neighboring nodes}}{{k_v \choose 2}} = \frac {2T(v)} {deg(v) (deg(v)-1)}$$