Page 333 - Becoming Metric Wise

325
Networks

Figure 10.2 Example network with three groups.

10.2.3 Clustering Coefficients
It may happen that if node a is connected to node b and node b is con-
nected to node c, then also nodes a and c are connected, as in the saying
“a friend of a friend is a friend.” How often this happens in a given net-
(1)
work can be measured by the clustering coefficient C , defined by
(Newman, 2003):

3 ðnumber of triangles in the networkÞ
C ð1Þ 5 (10.8)
number of connected triples of vertices
Here a triangle is a set of three vertices each of which is connected to
the other two and a connected triple is a set of three vertices such that
one vertex is connected to the other two (whether or not these other
(1)
two are connected). It can be shown that 0 # C # 1. This clustering
coefficient is also known as the fraction of transitive triples. Yet, there
(2)
exists another clustering coefficient which will be denoted as C . Its def-
inition starts from a local clustering coefficient, denoted as C j , where
number of triangles connected to node j
C j 5 (10.9)
number of triples centered on node j

If a vertex has degree zero or one, C j is set equal to zero. Then the
clustering coefficient C (2) is the average value of all C j :

1 X
C ð2Þ 5 C j (10.10)
N
j