Clustering coefficient

From Psychology Wiki

Community portal · Tasks to do · News · Help

Clinical · Educational · Ind&Org · Other fields · Professional · Transpersonal · World

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language
Personality | Philosophy | Research Methods | Social | Statistics

Statistics: Scientific method · Research methods · Experimental design · Undergraduate statistics courses · Statistical tests · Game theory · Decision theory

Example clustering coefficient on an undirected graph for the shaded node i. Black edges are nodes connecting neighbors of i, and dotted red edges are for unused possible edges.

Duncan J. Watts and Steven Strogatz (1998) introduced the clustering coefficient¹ graph measure to determine whether or not a graph is a small-world network.

First, let us define a graph in terms of a set of vertices and a set of edges , where denotes an edge between vertices and . Below we assume , and are members of V.

We define the neighbourhood N for a vertex as its immediately connected neighbours as follows:

The degree of a vertex is the number of vertices, , in its neighbourhood .

The clustering coefficient for a vertex is the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibly exist between them. For a directed graph, is distinct from , and therefore for each neighbourhood there are links that could exist among the vertices within the neighbourhood. Thus, the clustering coefficient is given as:

An undirected graph has the property that and are considered identical. Therefore, if a vertex has neighbours, edges could exist among the vertices within the neighbourhood. Thus, the clustering coefficient for undirected graphs can be defined as:

Let be the number of triangles on for undirected graph . That is, is the number of subgraphs of with 3 edges and 3 vertices, one of which is . Let be the number of triples on . That is, is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is and such that is incident to both edges. Then we can also define the clustering coefficient as:

It is simple to show that the two preceding definitions are the same, since .

These measures are 1 if every neighbour connected to is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to connects to any other vertex that is connected to .

The clustering coefficient for the whole system is given by Watts and Strogatz as the average of the clustering coefficient for each vertex:

[edit] References

¹ Watts, D. J. and Strogatz, S. H. "Collective dynamics of 'small-world' networks." [1]

de:Clusterkoeffizient

he:מקדם התקבצות

This page uses content from the English-language version of Wikipedia. The original article was at Clustering coefficient. The list of authors can be seen in the page history. As with Psychology Wiki, the text of Wikipedia is available under the GNU Free Documentation License.