clustering coefficient

Watts and Strogatz (1998) introduce 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

n

vertices

V={v_1,v_2,...v_n}

and a set of edges

E

, where

e_{ij}

denotes an edge between vertices

v_i

and

v_j

. Below we assume

v_i

v_j

and

v_k

are members of V. We define the neighbourhood N for a vertex

v_i

as its immediately connected neighbours as follows:

N_i = \{v_j\} : e_{ij} \in E.

The degree

k_i

of vertex is the number of vertices in its neighbourhood

|N_i|

. The clustering coefficient

C_i

for a vertex

v_i

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,

e_{ij}

is distinct from

e_{ji}

, and therefore for each neighbourhood

N_i

there are

k_i(k_i-1)

links that could exist among the vertices within the neighbourhood. Thus, the clustering coefficient is given as:

C_i = \frac{|\{e_{jk}\}|}{k_i(k_i-1)} : v_j,v_k \in N_i, e_{jk} \in E.

This measure is 1 if every neighbour connected to

v_i

is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to

v_i

connects to any other vertex that is connected to

v_i

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

\overline{C} = \frac{1}{n}\sum_{i=1}^{n} C_i.

References

Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature 393, 440--442 (4 June 1998).

<< Previous

Word Browser

Next >>

khashbaatar tsagaanbaatar
ares (magazine)
twist serve
william coddington
the chair
john pitcairn
urbanity
sweat suit
salt lake community college
vatul
three kings dbc

lobsterbacks
canadian pacific railway limited
s.t.a.r.s.
mountain hemlock
1938 atlantic hurricane season
flint (automobile)
yomiko readman
spencer mansion
list of world war ii evacuations
wciu tv
ddrmax2: dance dance revolution 7thmix

caspian tiger
bellbird (cocktail)
keiji honda
sta
kyrgyz air
mirabello
lady devimon
mount batten
emmanuel j. siyes
dan goodwin
james lafferty

star (automobile)
list of greek clergymen
gotcha
1937 atlantic hurricane season
temp
signaling connection control part
list of greek entrepreneurs
vini vidi vici
foxtrax
gordon craig
benjamin peret