Information Technology Reference
In-Depth Information
3.2
Definitions and Notations
Building clusters inside a graph requires the identification of structures that fulfill
criteria related to graph theory. In that respect, the following paragraphs briefly
present the graph theory concepts required to understand the clustering methods
(for further information, see
Berge
,
1973
;
Bollobás
,
1998
).
3.2.1
Specific Notions of Graph Theory
A subgraph (or subgroup) corresponds to the union of a subset of nodes and of the
edges linking those nodes.
A subgraph is called “maximal” in relation to a given property if it follows this
property, and if every extension of this subgraph in which one or several outer nodes
are added leads the graph to no longer follow this property.
Symmetrically, a subgraph is called “minimal” in relation to a given property if it
follows this property and if every restriction of this subgraph in which one or several
of its nodes are removed leads the graph to no longer follow this property.
A path between two nodes is a sequence of nodes and edges linking those nodes.
The length of a path is given by the number of its edges. Two nodes are reachable
from each other if there is at least one path between the nodes. The length of
the shortest path(s) between two nodes corresponds to the distance between them
(cf. Fig.
3.1
).
Two nodes are said to be “connected” if there is at least one path between them.
The graph is said to be “connected” if each pair of nodes is connected.
Two paths between
i
and
j
are independent if and only if they do not share any
edges.
The number of independent paths between two nodes
i
and
j
corresponds to the
minimum number of edges to be removed to disconnect
i
and
j
: this number is
the connectivity index of the node pair
, and it provides information about the
robustness of the paths between
i
and
j
on the graph (cf. Fig.
3.2
).
{
i
,
j
}
Fig. 3.1
Example of a
shortest path on a graph
Search WWH ::
Custom Search