Of Notes

Triangles and the Clustering Coefficient

1 min read · revised 17 October 2026 · referred to by 2 notes · ·

We observe in a network that the number of paths between of length is given by .

With this in mind, we now think of a length equal to which constructs a triangle around some node : .

Taking into account that one path can be traversed there and back we express the triangle count:

Clusters

We abstract the notion of two neighbors being connected to a clustering coefficient . This represents the probability of choosing any two random neighbors and them being connected.

Formally,

Here the Kronecker Delta Function lets us filter for different nodes for which we then "check" if they are connected to the node and to themselves. If this is true then it contributes to the sum.

Simplified Simple Non Directed Graph

For a set of neighbors, the total number of connections is: a single neighbor can connect to neighbors (excluding themselves) which we can repeat for neighbors, therefore the denominator becomes . And the numerator as we discussed above can just be the number of triangles .

Therefore:

Or also writable as:

Node \(i\) has \(k_i = 4\) neighbours, so \(\binom{4}{2} = 6\) pairs among them could be linked (dotted where they are not). Two are, each closing a triangle with \(i\) like the shaded one, so \(C_i = 2/6 = 1/3\).
Fig. 1. Node has neighbours, so pairs among them could be linked (dotted where they are not). Two are, each closing a triangle with like the shaded one, so .
/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card