For any simple connected graph G with at least two vertices, the "clustering coefficient" C(G) measures the extent to which vertices linked to any given vertex v are also linked to each other. Or in other words, are the friends of my friends also my friends?
More formally, consider any simple connected graph G with vertex set V(G) and edge set E(G). For any particular vertex v in V(G), define N(v) to be the neighborhood of v consisting of all vertices v' in V(G) that are directly connected to v through an edge in E(G). (By the assumption of simplicity, v itself is not contained in N(v); and by the assumption of connectivity, N(v) contains at least one node unless V(G) is a singleton.) If N(v) contains 0 or 1 nodes, define the clustering coefficient C(v) for v to be 1. Otherwise, define C(v) to be the number NEActual_v of edges actually existing between vertices in N(v) divided by the number NEPossible_v of all possible edges that could exist between vertices in N(v). That is,
NEActual_v C(v) = -------------- NEPossible_v
The clustering coefficient C(G) for G is then defined to be the average of C(v) over v in V(G).
M | | _ - - | - M = Size | - of the | largest | - component| | - | | - | - |______________________________________________ R 0.50 R = Ratio of Number of Edges to Number of Vertices
Albert-Lázló Barabási,
Linked: The New Science of Networks,
Cambridge, MA: Perseus Publishing
2002, Cloth: ISBN 0-738-20667-9.
Stanley Milgrom, "The Small World Problem", Psychology Today, 1967, Vol. 2, 60-67.
Leigh Tesfatsion, "Introductory Notes on the Structural and Dynamical Analysis of Networks" (pdf,2.3MB).
Leigh Tesfatsion, "Notes on Wilhite (2001)" (pdf,236K).