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

￿ the degree of the subgroup nodes;

￿ the comparison between intra- and inter-group edges;

￿ the identification of cut-sets.

3.4 Methods for Identifying Subgroups Inside a Graph -

Guidelines for Clustering Geographical Networks

3.4.1 Subgroups Built from the Edge-Exhaustiveness Criterion

The most direct clustering method consists of picking out the subgroups where the
nodes are directly linked in pairs: this criterion corresponds to the clique notion of
graph theory.
A clique is formally a maximal complete subgroup of at least three nodes. In
other words, each node pair of a clique is materialized by an edge, and it is not possi-
ble to find an outer node that would be linked at each node of the clique (cf. Fig. 3.7 ).
By definition, the notion of cliques is restrictive for subgroup definition. The lack
of a single tie between two nodes of a potential clique prevents clique formation. In
practice, cliques are extremely rare inside wide networks, and they are generally
very small: for that reason, this notion has to be extended to highlight larger but less
cohesive structures.

3.4.2 Subgroups Built from the Reachability Criterion

The reachability notion is a useful extension to the clique notion. Reachability
is particularly relevant when studying information networks: in this case, the
issue often consists in identifying subgroups where information can be quickly
transmitted between nodes. Therefore, the nodes do not have to be adjacent to each
other, as they do in a clique (exhaustiveness criterion), but they do have to be close
to each other in terms of shortest path length (reachability criterion).

Fig. 3.7 Identification of
cliques inside a graph (For
this example, we note that the
same node can be part of
several cliques)