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

Fig. 3.4 Examples of a non-valuated graph ( left ) and a valuated graph ( right ) - impact of edge
values on the computation of shortest paths

In practice, the interpretation of edge value depends on the meaning of the
relationship between two nodes. Choosing a threshold (such that every edge with
a greater value is considered unavailable) may be relevant for issues where the
“metric” closeness is a main condition within the context of the study, such that
nodes have to be topologically and geometrically well-connected.
Based on these notions and extensions of graph theory, we now propose to
discuss the meaning of a clustering operation inside a graph and its possible
expressions in terms of graph analysis.

3.3 Identifying Cohesive Subgroups Inside a Graph

Clustering operations inside a graph aim to gather strongly connected nodes
according to criteria on the presence and nature of ties between those nodes.
Secondly, these operations may lead to the replacement of the identified groups
with clustered nodes to produce a simplified representation of the graph (cf.
Fig. 3.5 ). Nevertheless, this simplification represents a topic of research in that
it also requires simplification of the edges and the component attributes (values,
weightings, structural information such as paths, etc.).
Graph theory provides several mathematical tools to carry out node clustering
within a graph. These tools have been widely formalized and developed in sociology