Civil Engineering Reference
In-Depth Information
17.3.2 Hierarchical model of infrastructure networks
Building a hierarchy that represents network communities at different
levels is the core idea behind the proposed approach. This is carried out by
a process of successive clustering of the network. Therefore, a recursive
implementation of clustering is necessary to construct a hierarchy. More-
over, variations in parameters may be necessary from level to level in order
to achieve different levels of detail and cluster sizes.
A clustering
C
{
C
1
, . . . ,
C
k
} of a graph
G
is a partition of the node-set
V
into non-empty (disjoint) subsets
C
i
such that
V
is given by the union of
them. The set
E
(
C
i
,
C
j
) represents the set of edges with origin in cluster
C
i
and destination in cluster
C
j
;
E
(
C
i
) is the short notation for
E
(
C
i
,
C
i
). Then,
E
(
C
) is the set of intra-cluster edges
E
(
C
), thus
E
/
E
(
C
) (node-set without),
is the set of inter-cluster edges (Brandes and Erlebach, 2005). A clustering
is a refi nement of other if it is a partitioning of higher resolution, or a
coarsening in the opposite case. Cases where the number of clusters
k
is
equal to 1 or the number of nodes
n
are referred to as a trivial clusterings.
A chain of clusterings is called a hierarchy. Multi-level network clustering
provides structured organization of a system, which enhances knowledge
of network properties.
Aiming to provide a model for a highly complex system, it is proposed
that networks are partitioned recursively based on pertinent criteria (Gómez
et al.
, 2011a). Each level of recursion (i.e., each different partitioning of the
network) denotes a level of abstraction. The hierarchical clustering leads to
a system representation in the form of a tree, also called a dendrogram
(from Greek
dendron
'tree' and gramma 'drawing'). The concept of hierar-
chical representation of a system has been widely discussed for hard (e.g.,
infrastructure) and soft (e.g., sociological) systems (Blockley and Godfrey,
2000; Scott 2000).
=
Fictitious nodes:
Clusters at all levels defi ne fi ctitious nodes. Let
V
(
lv
)
be
the
i
th node at the hierarchical level
lv
. Then, at the top of the hierarchy
(i.e.,
lv
1), the network is interpreted as a single unit (i.e., one fi ctitious
node), which consists of all actual nodes
v
i
and all links between them:
V
(1)
=
{
v
1
,
v
2
, . . . ,
v
n
,
E
}, where
E
is the set of links of the graph
G
(
V
,
E
).
In the second level (
lv
=
2), the network is described by
d
fi ctitious
nodes:
V
(2)
,
V
(2)
, . . . ,
V
(2)
, with
V
(2)
,
V
(2)
, . . . ,
V
(2)
being a subset of
V
1
(1)
.
Notice that the
n
actual nodes, contained in the fi ctitious node
V
(1)
at
the fi rst level, are distributed among the
d
fi ctitious nodes at the second
level.
=
Fictitious links:
A fi ctitious link
E
i
(
lv
)
, which connects
V
(
lv
)
and
V
(
lv
)
,
describes how clusters at a hierarchical level
lv
are connected to each
other, and is constructed as the parallel arrangement of all actual links
Search WWH ::
Custom Search