Risk assessment and management of civil infrastructure networks: a systems approach - Seismic Risk Analysis and Management of Civil Infrastructure Systems - page 433

chosen node has degree k . The k -connectivity of a graph is a popular global
measure that indicates the number of independent paths between source
and target nodes, i.e., it indicates the minimum number of nodes that need
to be removed to disconnect the network.
Network modelling poses signifi cant computational challenges. With the
exception of small networks, or certain geometric characteristics (Duenas-
Osorio and Rojo, 2011), analytical and/or numerical closed-form solutions
of connectivity and fl ow effi ciency cannot be easily obtained. The identi-
fi cation of all possible failure scenarios is commonly known as an NP-hard
(nondeterministic polynomial time hard) problem due to the enormous
number of possible states (e.g., a network with n on-off elements has
2 n possible states). In other words, it is unlikely that there is a general
algorithm that can compute all possible cases under reasonable time
constraints.
Several approaches have been proposed to deal with this problem, for
example, Konak et al. (2004) divided alternative approaches in three groups:
(1) state-based techniques, which 'aim to generate state vector more effi -
ciently [. . .] or to introduce negative correlation between sampled state
vectors'; (2) 'sample space of arc permutations instead of the original sample
space S [, which] . . . are particularly effi cient if all arcs have identical reli-
ability'; and (3), bounding techniques, which includes 'stratifi ed and impor-
tant sampling variance reduction techniques' (Konak et al. , 2004).
The proposed approach is motivated by the possibility of detecting
topological features (i.e., a cluster-based hierarchy) of complex systems to
addresses decision-makers' needs by allowing the use of simplifi ed, surro-
gate network models (see Section 17.3). The process of network decomposi-
tion allows redefi ning any network problem in terms of communities and
is not intended to be an approach limited to reliability computation, but to
general network problem solving.
17.3 Hierarchical representation of networks
17.3.1 Basic notions on clustering
Clustering is a pattern recognition technique that can classify a set of unla-
belled data into multiple classes; unlabelled means that the algorithm is not
previously trained to recognize classes (i.e., unsupervised learning). The
objective of network clustering methods is to generate a partition of the
network into k subgroups; essentially, it seeks to maximize intra-cluster
density and inter-cluster sparsity. Each sub-group includes a centroid, which
is representative of the group, and constitutes a zone referred to as a
Voronoi region, which is determined by a convex set containing the nodes