Topological Clustering for Geographical Networks - Methods for Multilevel Analysis and Visualisation of Geographical Networks - page 45

Fig. 3.13 Illustration of the lambda-set notion: the local weakening of a lambda-set (here by
decreasing the degree of some nodes) can lead to a “downgrade” of the set

For this analysis, they compare the sets of nodes that are adjacent to each end of the
edge. If these sets overlap each other enough (in comparison to a given threshold),
then the edge is considered an inner-edge. Finally, the sets of inner edges delimit
several clusters according to a criterion based on an inner/outer edge comparison.
Figure 3.14 shows the Tokyo cluster identified with this method (for a threshold
equal to 1/2).

3.4.5 Subgroups Built from Cut-Sets

As previously mentioned, the notion of connectivity is linked with the minimal cut-
set notion.
Moody and White ( 2003 ) propose to use these notions to identify cohesive
subgroups inside a graph, not by comparing intra- and inter-group connectivity
indexes, but by gradually splitting the graph around its cut-sets.
This “cohesive blocking” method is recursive: for a given graph, it aims to
identify the minimal cut-set, pick out subgraphs on both sides of this cut-set, and
then repeat this process on these subgraphs.
Figure 3.15 is 1-connected: the minimal connectivity index computed on its node
pairs is equal to 1 (additionally, this graph can be disconnected by removing only
one node).
By applying the “cohesive blocking” method, we identify two subgroups on both
sides of this critical node. In the same way, these subgroups are split around their
cut-sets. The new subgroups have connectivity indexes equal to 2 and 3.