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

Fig. 3.8 Examples of 2-cliques

Fig. 3.9 The graph of the Fig. 3.8 also contains two 2-cliques that are difficult to identify at first

sight

In this connection, the n -clique is defined as a maximal subgraph in which each
pair of nodes is no more than n edges apart (the shortest path may pass through the
outer edges). For this reason, it is impossible 2 to find an outer node that would be
distant from each node of this subgraph with a distance less than or equal to n .
On the example of the Fig. 3.8 , the spatial layout of edges and nodes shows three
obvious 2-cliques.
However, these are not the only 2-cliques of this graph: in Fig. 3.9 we have
identified two other 2-cliques, straddling two of the previously identified 2-cliques.
In this connection, reachability appears to be an extension of edge exhaustiveness
insofar as the node closeness is under control (this criterion no longer concerns the
ties between nodes, but rather the shortest path length).
For example, such a criterion is realistic and relevant in geography for accessi-
bility issues. The need to cluster nodes based on the condition that they are “close
enough” to each other amounts to selecting zones in which the shortest paths are
shorter than a given threshold.

2 As defined, a n -clique may have a diameter greater than n because the shortest paths between its
nodes may pass through the outer edges of the n -clique. Nevertheless, there are variants of this
clustering method that control the subgroup diameter. Subgroups extracted by such methods are
called “ n -clans” and “ n -clubs” (for further information, see Moody & White , 2003 ; Wasserman &
Faust , 1994 ).