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

Fig. 3.11 Examples of

2-plexes

The following criterion helps to reject such structures by controlling the
minimum number of ties between the subgroup nodes.

3.4.3 Subgroups Built from the Node Degree Criterion

In a subgroup built from node degree criteria, the nodes have to be adjacent to a
“relatively high” number of other nodes.
In this respect, such subgroups are built according to the same rule as cliques
(each node has to be directly linked to other nodes) but with weaker conditions
(each node has to be directly linked to a minimum number of nodes).
This notion seems to be an interesting way to comprehend subgroup vulnerabil-
ity: vulnerability occurs when the relationships between nodes are not sufficiently
redundant, so that removing some target edges causes nodes disconnections. It turns
out that n -cliques are not robust enough in the sense that their structure may be
easily broken by the removal of a single node (a star-shaped structure is a 2-clique
and is vulnerable to the removal of the central node).
In contrast, k -plexes are more robust subgroups because they are built so that
each node has a “relatively high” adjacency number.
A k -plex is defined as a maximal subgroup where each node is adjacent to every
other node of the subgroup except for k nodes at most. 3
In that way, we have identified three 2-plexes on the graph of Fig. 3.11 .Inthese
2-plexes of five nodes, the nodes are adjacent to 3 (or more) other nodes of the
2-plex. In other words, inside the subgroup built from the 2-plex nodes, the nodes
have a degree greater than or equal to 3: the criterion specific to the k-plex is
explicit here.
A clustering method based on a degree criterion has been used by Gleyze
( 2009, September 4-8 ) to identify groups of mutually supportive countries in the
Eurovision Song Contest. In this study, Gleyze first determines which pairs of

3 Subgroups with a similar criterion can also be built by considering the minimum number of
adjacencies (rather than the maximum number of “non-adjacencies”), which we define as the
k -core. A k -core is then a maximal subgroup of n nodes where each node is adjacent to at least
k other nodes ( Moody & White , 2003 ; Wasserman & Faust , 1994 ).