0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$
  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)}$$

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