# Clustering coefficient

*34,203*pages on

this wiki

Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language |
Individual differences |
Personality |
Philosophy |
Social |

Methods |
Statistics |
Clinical |
Educational |
Industrial |
Professional items |
World psychology |

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

Duncan J. Watts and Steven Strogatz (1998) introduced the **clustering coefficient**^{1} 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:

## ReferencesEdit

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

- de:Clusterkoeffizient
- he:מקדם התקבצות

This page uses Creative Commons Licensed content from Wikipedia (view authors). |