In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes (Holland and Leinhardt, 1971;[1] Watts and Strogatz, 1998[2]).
Two versions of this measure exist: the global and the local. The global version was designed to give an overall indication of the clustering in the network, whereas the local gives an indication of the extent of "clustering" of a single node.
The local clustering coefficient of a vertex (node) in a graph quantifies how close its neighbours are to being a clique (complete graph). Duncan J. Watts and Steven Strogatz introduced the measure in 1998 to determine whether a graph is a small-world network.
A graph
G=(V,E)
V
E
eij
vi
vj
Ni
vi
Ni=\{vj:eij\inE\loreji\inE\}.
We define
ki
|Ni|
Ni
vi
The local clustering coefficient
Ci
vi
eij
eji
Ni
ki(ki-1)
ki
Ci=
| |\{ejk:vj,vk\inNi,ejk\inE\ | |
| |}{k |
i(ki-1)}.
An undirected graph has the property that
eij
eji
vi
ki
| ki(ki-1) | |
| 2 |
Ci=
| 2|\{ejk:vj,vk\inNi,ejk\inE\ | |
| |}{k |
i(ki-1)}.
Let
λG(v)
v\inV(G)
G
λG(v)
G
v
\tauG(v)
v\inG
\tauG(v)
v
v
Ci=
| λG(v) | |
| \tauG(v) |
.
It is simple to show that the two preceding definitions are the same, since
\tauG(v)=C({ki},2)=
| 1 | |
| 2 |
ki(ki-1).
These measures are 1 if every neighbour connected to
vi
vi
vi
Since any graph is fully specified by its adjacency matrix A, the local clustering coefficient for a simple undirected graph can be expressed in terms of A as:[3]
| C | ||||
|
\sumj,kAijAjkAki
where:
ki=\sumjAij
and Ci=0 when ki is zero or one. In the above expression, the numerator counts twice the number of complete triangles that vertex i is involved in. In the denominator, ki2 counts the number of edge pairs that vertex i is involved in plus the number of single edges traversed twice. ki is the number of edges connected to vertex i, and subtracting ki then removes the latter, leaving only a set of edge pairs that could conceivably be connected into triangles. For every such edge pair, there will be another edge pair which could form the same triangle, so the denominator counts twice the number of conceivable triangles that vertex i could be involved in.
The global clustering coefficient is based on triplets of nodes. A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties. A triangle graph therefore includes three closed triplets, one centred on each of the nodes (n.b. this means the three triplets in a triangle come from overlapping selections of nodes). The global clustering coefficient is the number of closed triplets (or 3 x triangles) over the total number of triplets (both open and closed). The first attempt to measure it was made by Luce and Perry (1949).[4] This measure gives an indication of the clustering in the whole network (global), and can be applied to both undirected and directed networks (often called transitivity, see Wasserman and Faust, 1994, page 243[5]).
The global clustering coefficient is defined as:
C=
| numberofclosedtriplets | |
| numberofalltriplets(openandclosed) |
The number of closed triplets has also been referred to as 3 × triangles in the literature, so:
C=
| 3 x numberoftriangles | |
| numberofalltriplets |
A generalisation to weighted networks was proposed by Opsahl and Panzarasa (2009),[6] and a redefinition to two-mode networks (both binary and weighted) by Opsahl (2009).[7]
Since any simple graph is fully specified by its adjacency matrix A, the global clustering coefficient for an undirected graph can be expressed in terms of A as:
| C= | \sumi,j,kAijAjkAki | |||
|
where:
ki=\sumjAij
and C=0 when the denominator is zero.
As an alternative to the global clustering coefficient, the overall level of clustering in a network is measured by Watts and Strogatz as the average of the local clustering coefficients of all the vertices
n
\bar{C}=
| 1 | |
| n |
| n | |
| \sum | |
| i=1 |
Ci.
It is worth noting that this metric places more weight on the low degree nodes, while the transitivity ratio places more weight on the high degree nodes.
A generalisation to weighted networks was proposed by Barrat et al. (2004),[9] and a redefinition to bipartite graphs (also called two-mode networks) by Latapy et al. (2008)[10] and Opsahl (2009).[7]
Alternative generalisations to weighted and directed graphs have been provided by Fagiolo (2007)[11] and Clemente and Grassi (2018).[12]
This formula is not, by default, defined for graphs with isolated vertices; see Kaiser (2008)[13] and Barmpoutis et al.[14] The networks with the largest possible average clustering coefficient are found to have a modular structure, and at the same time, they have the smallest possible average distance among the different nodes.
For a random tree-like network without degree-degree correlation, it can be shown that such network can have a giant component, and the percolation threshold (transmission probability) is given by
pc=
| 1 | |
| g1'(1) |
g1(z)
In networks with low clustering,
0<C\ll1
(1-C)-1
pc=
| 1 | |
| 1-C |
| 1 | |
| g1'(1) |
.
This indicates that for a given degree distribution, the clustering leads to a larger percolation threshold, mainly because for a fixed number of links, the clustering structure reinforces the core of the network with the price of diluting the global connections. For networks with high clustering, strong clustering could induce the core–periphery structure, in which the core and periphery might percolate at different critical points, and the above approximate treatment is not applicable.[16]
For studying the robustness of clustered networks a percolation approach is developed.[17] [18]