----
> [!definition] Definition. ([[clustering coefficient]])
The **clustering coefficient** of a [[network]] $G$ is the proportion of length-$2$ [[parameterized curve]]s that are closed in $G$: $C:=\frac{\text{number of closed paths of length 2}}{\text{number of paths of length 2}}.$
Equivalently, $C= \frac{\text{number of triangles} \times 6}{\text{number of paths of length 2}}.$
Equivalently, $C=\frac{\text{number of triangles} \times 3}{\text{number of connected triples}},$
where **connected triple** means three nodes $uvw$ with edges $(u,v)$ and $v,w$. (A 'V' shape.)
Equivalently, $C=\frac{\text{Tr }A^{3}}{2\sum_{i}^{}k_{i}(k_{i}-1)}.$
\
Equivalently, $C$ is the uniform [[probability]] that two neighbors of a node $i$ are themselves connected.
> [!justification]
>
\
We must show the listed equivalences hold.
\
The second holds because since each triangle contains six (closed) paths of length two, to count the number of closed paths of length 2 is just to count the number of triangles.
\
The third holds because we can alternatively consider the number of people with a common friend who are themselves friends.
\
The fourth holds because $[A^{3}]_{ij}$ is the [[number of walks of given length on a network|number of walks from]] node $i$ to $j$ with length $3$, and hence $\text{Tr }A^{3}$ yields the number of length-3 loops. Given a node $i$, the number of pairs of friends of $i$ ('V' shapes rooted by $i$) is ${k_{i} \choose 2}$, where $k_{i}$ is the [[degree]] of $i$. Therefore, total number of