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

Fig. 3.6 The edge density is not sufficient to describe the cohesion of a group (From Moody and
White ( 2003 ))

The nodes of a group may form a cohesive structure without pair linkages if
there is a sufficient number of relationships symbolized by the edges: in this respect,
cohesion is compared to the ease of reaching one node from another, i.e., to their
“reachability” (this notion is connected to the notion of accessibility in geography).
Another criterion is the association between the group cohesion and the edge
density (or volume) inside the group. Although this parallel at first seems acceptable,
this characterization is actually inadequate: the linear structure and its slightly
modified version in Fig. 3.6 show that the node reachability can differ widely for
constant density.
Although the edge density does not constitute an exclusive indicator to character-
ize cohesion, the edge layout should be uniform to prevent the group from splitting.
If the layout is not uniform, the subgroups with lower edge densities may be more
vulnerable, as slight changes may split them more easily.
In this way, a third set of clustering methods demands that conditions regarding
the node adjacency be fulfilled inside the subgroups: these criteria are based on the
node “degree”.
In terms of adjacency, it can be relevant to take into account not only the edges
inside the group (these “intra-group” edges should have the highest possible density)
but also the edges linking the group nodes with outer nodes (these “inter-group”
edges should have the lowest possible density).
In a more formal way, it is possible to build subgroups, not by gathering nodes
together, but by identifying the sets of edges that separate them from each other. To
that end, it seems worthwhile to take advantage of the structural weakness of these
sets with low densities. Then, these sets become small sets of edges whose removal
splits the graph. This approach matches well with the whole area of graph theory
devoted to the “cut-sets”.
Based on these qualitative elements, we present the clustering methods and their
possible applications in geography according to the following notions:

￿ the edge exhaustiveness;

￿ the closeness or reachability of nodes inside the subgroup;