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
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:
[edit] References
1 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. |





