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 coefficient1 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:
References[]
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). |