Structural Analysis of Networks - Methods for Multilevel Analysis and Visualisation of Geographical Networks - page 72

This idea converges with that of Granovetter, in which triads are a key component
in social cohesion ( Granovetter , 1973 ). Other edge metrics that were proposed much
later were designed to achieve similar goals (see Sallaberry & Melançon , 2008 for
more details).
The Jaccard index has a useful interpretation in terms of group cohesion. Note
that when an edge e = { u , v } connects two distinct neighborhoods N G ( u ) ∩ N G ( v )=

0, we have J G ( 0. That is, the Jaccard index seems capable of locating regions

where communities break apart. In the same line of reasoning, one may expect the
clustering coefficient to help locate such transition areas in networks.
The two metrics we have described so far are local , meaning that the value
assigned to a node or edge is computed by examining neighboring nodes and/or
edges. Two other types of metrics can be defined to capture community structures.
A well-known and widely used metric that has recently attracted the attention of
a wide audience through the fertile work of Newman et al. ( Clauset, Newman, &
Moore , 2004 ; Girvan & Newman , 2002 ; Newman , 2001 , 2006 ) is the betweenness
centrality metric extended to the edges of a graph. Recall that the betweenness
centrality Eq. ( 5.8 ) is defined in terms of the number of shortest paths going through
a node (or edge). That is, an edge with a high betweenness centrality can be expected
to act as a bridge between communities. Burt ( 2005 ) also highlights high centrality
edges as bridges passing through structural holes in the network. Bridges have been
exploited as a central component for breaking down a graph into communities (see,
for instance, Amiel, Melançon, & Rozenblat , 2005 ; Auber, Chiricota, Jourdan, &
Melançon , 2003 ; Clausetetal. , 2004 ; Girvan & Newman , 2002 ).

e )=

5.3 Community Dynamics

Finding cohesive subgroups or communities in a network helps obtain a better un-
derstanding of how network entities interact. When performing a visual inspection
or exploration of a network, one will typically compute communities and then
build a simpler graph, the “quotient graph”, from the community structure. More
precisely, let G =( V , E ) be a graph and C be a partition C =( C 1 ,..., C k ) where

C i ⊂ V are distinct subsets ( C i ∩ C j = /0when i = j ) covering V = ∪ i = 1 ,..., k C i .

Then, we can form the quotient graph G / C with vertices { C 1 , ..., C k } ,where

edges connect C i and C j when there is at least one edge e = { u , v } connecting

two nodes u C j .Fig. 5.4 illustrates this construction. Each box shows

the subgraph contained in a cluster, which is shown as a metanode. Metanodes are
connected according to the edges between the nodes they contain.
Providing an overview of all existing graph clustering is beyond the scope of this
topic. The interested reader should see Brandes, Gaertler, and Wagner ( 2007 )and
Schaeffer ( 2007 ), for instance. Here, we shall limit our discussion to a few popular
clustering strategies that rely on network indices (see Amiel et al. , 2005 ; Auber
et al. , 2003 ; Clauset et al. , 2004 ; Girvan & Newman , 2002 ). As mentioned earlier,
centrality indices can be used to identify the bottleneck edges in networks. Hence,

∈ C i and v ∈