Ebook: Examining Robustness and Vulnerability of Networked Systems

The complex nature of interdependent, heterogeneous, dynamically evolving networks characterizing modern critical infrastructure is exacerbated by uncertainty of potential component failures that must be addressed in realistic mathematical models. The NATO Advanced Research Workshop on “Examining Robustness and Vulnerability of Critical Infrastructure Networks” was held in Kyiv, Ukraine on June 3-5, 2013. The workshop participants representing 12 countries (Armenia, Germany, Greece, Italy, Lithuania, Portugal, Russia, Spain, Sweden, United Kingdom, Ukraine, and USA) discussed recent progress and promising future research directions on the following topics:

• Mathematical models describing structures that characterize the network's robustness and vulnerability to an attack.

• Probability-based risk measures characterizing a networks vulnerability to edge/node failures.

• Exact, approximate, and heuristic algorithms for designing minimum cost robust network topologies and for detecting robust structures of interest in networks.

• Mathematical models and algorithms for identification of critical network components.

• Optimization techniques to restrict and control the damages and losses associated with various risk factors that affect the operations of interdependent networked systems.

• Case studies with large-scale real-life transportation, communication, and energy networks.

This volume contains contributions by the workshop participants, as well as other invited experts working on related topics. The book will be of interest to researchers, practitioners, and graduate students in mathematics, computer science, and engineering.

We would like to thank the NATO Science for Peace and Security Programme for providing funding for this memorable workshop, and also IOS Press for making this publication possible.

Sergiy Butenko

College Station, TX, USA

Eduardo Pasiliao

Eglin, AFB, FL, USA

Volodymyr Shylo

Kiev, Ukraine

The critical infrastructures of the nation such as the power grid and the communication network are highly interdependent. Also, it has been observed that there exists complex interdependent relationships between individual entities of the power grid and the communication network that further obfuscates the analysis, and mitigation of faults in such multi-layered networks. In recent years, the research community has made significant efforts towards gaining insight and understanding of the interdependency relations in such multi-layered networks, and accordingly, a number of models have been proposed and analyzed towards realizing this goal.

In this chapter we study existing interdependency models proposed in the recent literature and discuss their approach, and inherent features, towards modeling interdependent multi-layer networks. We also provide a brief discussion into the drawbacks of each of these models and propose an alternate model that addresses these drawbacks by capturing the interdependency relationships using a combination of conjunctive and disjunctive relations.

This paper considers the cover by s-defective independent sets problem (or, simply, the s-defective coloring problem), which generalizes the classical coloring problem. In the coloring problem, each color class should induce an edgeless subgraph. The s-defective coloring problem relaxes this requirement, allowing for at most s edges to appear in each color class's induced subgraph. We propose a local search neighborhood and apply the GRASP metaheuristic to the related minimization problem. The quality of the heuristically-generated solutions is evaluated with a commercial MIP solver. The integer programming formulation that we use generalizes the asymmetric representatives formulation.

We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.

For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed efficient label correcting algorithms.

The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

Edge-ratio clustering was introduced in [Cafieri et al., Phys.Rev. E 81(2):026105, 2010], as a criterion for optimal graph bipartitioning in hierarchical divisive algorithms for cluster identification in networks. Exact algorithms to perform bipartitioning maximizing the edge-ratio were shown to be too time consuming to be applied to large datasets. In this paper, we present a Variable Neighborood Search (VNS)-based heuristic for hierarchical divisive edge ratio network clustering. We give a full description including the structure of some algorithmic procedures which are used to implement the main steps of the heuristic. Computational results show that the proposed algorithm is very efficient in terms of quality of the bipartitions, moreover the computing time is much smaller than that one for exact algorithms.

Cluster analysis aims at finding subsets (clusters) of a given set of entities, which are homogeneous and/or well separated. In the last decades, cluster analysis started playing an important role in a wide and heterogeneous range of applications involving different scientific research communities, including genetics, biology, biochemistry, mathematics, and computer science among others. This paper overviews the main types of clustering and criteria for homogeneity or separation, as well as the most popular solution techniques.

Social network analysis is an area of research that is gathering interest and importance since the turn of the century, especially with increased technology proliferation. Graph theory is predominantly being used in the analysis of social networks. The maximum k-plex problem, which belongs to the category of clique relaxation problems has been studied by researchers in this field. This problem is known to be NP-hard. This paper proposes an amalgamation of a greedy randomized adaptive search procedure and tabu search metaheuristic to solve the problem. The performance of the proposed hybrid metaheuristic is tested on well-known instances of graphs and the computational results are reported.

The structure of a network can significantly affect the course of infections on it. For example, a human-to-human contact network affects the epidemiology of infectious diseases, affecting both the rate of new infections and the sizes of outbreaks. Related results are also known for infrastructure systems like communication and power transmission systems that experience cascading breakdowns. Despite this dependence, some characteristics of outbreaks are predictable based only on the infection being transmitted. Here we consider SIR-like infections, and give an elementary proof that for any network, increasing the probability of transmission monotonically increases the mean outbreak size. We also introduce a simple model, termed 2FleeSIR, in which susceptibles protect themselves by avoiding contacts with infectees. The dynamics of 2FleeSIR are fundamentally different from SIR dynamics because 2FleeSIR seems to exhibit no outbreak transition in densely-connected networks. Moreover, 2FleeSIR exhibits non-monotonic phenomena: for some networks, increasing transmissibility actually decreases the final extent. We show that in non-monotonic epidemics, public health officials might be able to intervene in a fundamentally new way to change the network so as to control the effect of unexpectedly-high transmissibility. However, interventions that decrease transmissibility might actually cause more people to become infected.

A wide range of applications require or can benefit from collaborative behavior of a group of agents. The technical challenge addressed in this chapter is the development of a decentralized control strategy that enables each agent to independently navigate to ensure agents achieve a collective goal while the system maintains network connectivity. Specifically, cooperative controllers are developed for networked agents that have both limited sensing and network connectivity constraints. By modeling the interaction among the agents as a graph, several different approaches to address the problems of preserving network connectivity are presented, with the focus on a method that utilizes navigation function frameworks. By modeling network connectivity constraints as artificial obstacles in navigation functions, a decentralized control strategy is presented in two particular applications, formation control and rendezvous for a system of autonomous agents, which ensures global convergence to the unique minimum of the potential field (i.e., desired formation or desired destination) while preserving network connectivity. Simulation results are provided to demonstrate the developed strategy.

A network with unreliable edges is considered. All failed edges can be repaired. Distribution functions of failure-free operation and repair time of edges are supposed to be of general type. A fast simulation method producing unbiased estimates for the network failure (interruption of connection between two given nodes s and t in a given time interval) is developed. It is proved that under some weak conditions these estimates have a bounded relative error with increasing reliability of components. Numerical examples demonstrate the efficiency of the proposed method.

This chapter surveys early studies and recent developments in the broad area of analysis and design of robust network clusters with bounded diameter. Low diameter (small number of intermediaries in the shortest path between any two nodes) is a desired property of various infrastructure networks (communication/information exchange, transportation/supply, etc.) However, in addition to low diameter, a network cluster may need to be able to withstand multiple disruptions or failures of their elements (nodes and/or links), which is not always a guaranteed property for networks with low diameter. We review mathematical modeling and optimization aspects of studying network clusters with bounded diameter, including basic models (referred to as k-clique and k-club), as well as generalized models with improved failure/attack tolerance characteristics (i.e., R-robust k-club).

Routing has always been of immense importance in communication networks due to its impact on the network performance. The significance of scalable and adaptive routing has sky-rocked during the last decade as a consequence of the ever increasing demand for Internet and mobile communications. A routing algorithm selects one or more paths over which devices communicate with each other. In this paper, a new Multiobjective Particle Swarm Optimization (MOPSO) algorithm, with a new velocity equation, for the solution of the Multiobjective Multicast Routing Problem is proposed and tested. A number of variants of the proposed algorithm with global and local exploration abilities are presented and compared with each other. In order to estimate the quality of the methodology, experiments are conducted using classic Euclidean Traveling Salesman Problem benchmark instances taken from the TSP library, modified suitably for the selected problem. The preliminary results indicate the efficiency of the proposed method.

Shared-channel communication networks, e.g., a wireless local area network, are susceptible to congestion that can adversely affect performance and stability of systems operating over a network due to packet loss and time-delays. In addition to poor network service quality, congestion can result in partial or complete network collapse. The detrimental effects of congestion on a network and the systems operating over the network can be mitigated by designing a controller to reduce the reliance of systems on the network by reducing channel utilization. In this chapter, a context-aware communication policy that stabilizes a class of nonlinear networked control systems (NCS) operating over a bandwidth-limited shared-channel is developed to reduce channel utilization. The NCS under consideration is also assumed to be affected by an unmodeled, nonlinear, exogenous disturbance. The control objective is to stabilize a nonlinear NCS in the presence of uncertainties while minimizing the network usage. The informational value of the output states can be analyzed in the context of system stability using model-based approaches. When fused with event-based triggering, the context-aware communication policy results in aperiodic feedback signals that guarantee uniformly ultimately bounded tracking of output states of an uncertain perturbed system along the desired time-varying trajectory. The proposed NCS is validated using simulations for nonlinear scalar and coupled MIMO systems.

Hop constraints are used to limit the number of links between two given points in a network, this way improving the quality of service by increasing the availability and reliability of the network. They have been applied to a limited number of problems, although their application can be of the greatest importance both from the academical and practical points-of-view. In this work, we survey relevant and recent works on hop-constrained problems focusing on problems with tree shaped solutions.

The cell model for the search of moving objects under conflict condition is advanced as demonstrated herein. The necessary conditions for the probability of detection in a finite time are derived. The various episodes of search, based on corresponding number with groups of controlled objects as participants, are analyzed in a unified scheme. The mathematical techniques for the creation of information technologies concerning the search of moving objects in condition of imperfect information is developed.

In this work, we consider a risk-averse maximum weighted k-club problems. It is assumed that vertices of the graph have stochastic weights whose joint distribution is known. The goal is to find the k-club of minimum risk contained in the graph. A stochastic programming framework that is based on the formalism of coherent risk measures is used to find the corresponding subgraphs. The selected representation of risk of a subgraph ensures that the optimal solutions are maximal k-clubs. A combinatorial branch-and-bound solution algorithm is proposed and solution performances are compared with an equivalent mathematical programming counterpart problem for instances with k = 2.

This paper presents a method for distributed attacks detection in corporate computer networks. The method is designed according to the modern requirements of attack detection and can be used to reveal existing and modified attacks. A mathematical model of the system is developed using hybrid neural networks. Hybrid networks are presented as an integration of two artificial networks – a multilayer neural network and a self-organizing map or Kohonen network. The model can be applied in corporate networks for increasing efficiency of security management. Corporate networks formed the environment of network economy and disseminate critical managerial, business and financial information, which needs to be protected from dynamically changing computer attacks. The developed methodology was applied to analysis of the Armenian commercial banking system.

We study NP-hard placement optimization problems, which cover a wide spectrum of industrial applications, including space engineering. The review paper considers phi-functions as an analytical tool for describing placement constraints, including containment, non-overlapping, allowable distances, prohibited areas, object translations and rotations. A mathematical model of a basic placement problem is presented as a non-smooth optimization problem. We consider two solution algorithms for optimization placement problems. The reader will get acquainted with two subsequent problems of the basic placement problem encountered in space engineering.

The open nature of wireless networks makes them vulnerable to attacks by external or internal users of the network. Wireless networks have applications in military, disaster and commercial areas. It is important to find ways to defend against such attacks. While there are many studies dealing with different types of attacks and defense strategies, there are no tutorials available in literature that introduces the security issues in wireless networks to an operations research audience. In this paper we provide an introduction to the different attacks and defense strategies in wireless networks. We also discuss modeling constructs and give several modeling examples aimed to help new researchers become acquainted with this area of research.

In this chapter we discuss a common derandomized approximation algorithm for yielding a constant-tunable approximation bound to two variants of the critical node detection problem. The goal of the respective problems is to reduce total pairwise connectivity or number of vertices to delete in order to achieve bounded component sizes in the residual graph, respectively. Our algorithms are built upon previous research and improved by an efficient local search algorithm that incorporates the closeness centrality. We show that the original approximation algorithm bounds remain in tact, while the practical performance is greatly improved. To highlight the results we utilize five common network data sets of various sizes.