Information Technology Reference
In-Depth Information
Fig. 5.3
The figure shows how values of the clustering index (
left
) and Jaccard index (
right
)are
distributed over the nodes/edges of a typical small world graph. Note how both metrics act locally,
as opposed to the metrics in Fig.
5.1
or Fig.
5.2
. The node color changes from
light orange
to
purple
as the values increase. The node size also correlates with the node values (Color figure online)
low average distance (see Eq.
5.5
) between nodes. However, nodes do not split into
distinct communities because the connections are uniformly distributed among the
nodes.
2
In other words, the clustering coefficient of an Erdos-Renyi graph can be
expected to be somewhat small.
Inspired by the popular saying “It's a small world”, Watts and Strogatz developed
different graph models that showed characteristics similar to those of the real world
networks observed by Milgram (
1967
). More precisely, a graph is said to be small
world if its clustering coefficient is high while the average distance between nodes
is low when compared to the values of random Erdos-Renyi graphs with the same
number of nodes and edges.
The clustering index does just what it is expected to do, as it indicates just how
well connected is the neighborhood of a node
u
; the clustering index can thus be
presented as a
cohesion metric
. Another approach is to focus instead on edges and
consider how many common neighbors that the end nodes of an edge
e
=
{
u
,
v
}
have:
)=
|
N
G
(
u
)
∩
N
G
(
v
)
|
J
G
(
e
(5.10)
|
N
G
(
u
)
∪
N
G
(
v
)
|
ThemetricinEq.(
5.10
) was first introduced by Jaccard (
1901
), who studied the
similarity between floral species. However, the Jaccard index can be computed on
sets and can thus be used to compare any type of attribute-based data (Fig.
5.3
). Also
note that, when applied to neighbor sets
N
G
(
, the numerator actually computes the
number of triads (cycle of length 3) in a graph
G
going through an edge
e
.
u
)
2
This being said, a random Erd os-Rényi graph might not be necessarily connected. For more
details, see
Bollobás
(
1985
).
Search WWH ::
Custom Search