· · · Institutional Repository

Our society depends more strongly than ever on large networks such as transportation networks, the Internet and power grids. Engineers are confronted with fundamental questions such as “how to evaluate the robustness of networks for a given service?”, “how to design a robust network?”, because networks always affect the functioning of a service. Robustness is an important issue for many complex networks, on which various dynamic processes or services take place. In this work, we define robustness as follows: a network is more robust if the service on the network performs better, where performance of the service is assessed when the network is either (a) in a conventional state or (b) under perturbations, e.g. failures, virus spreadings etc. In this thesis, we survey a particular line of network robustness research within our general framework: robustness quantification, optimization and the interplay between service and network. Significant progress has been made in understanding the relationship between the structural properties of networks and the performance of the dynamics or services taking place on these networks. We assume that network robustness can be quantified by a topological measure of the network. A brief overview of the topological measures is presented. Each measure may represent the robustness of a network with respect to a certain performance aspect of a service. We focus on the measure known as algebraic connectivity. Evidence collected from literature shows that the algebraic connectivity characterizes network robustness with respect to synchronization of dynamic processes at nodes, random walks on graphs and the connectivity of a network. Moreover, we illustrate that, on a given diameter, graphs with large algebraic connectivity tend to be dense in the core and sparse at the border. Such structures distribute traffic homogeneously and are thus robust in terms of traffic engineering. How do we design a robust network with respect to the metric algebraic connectivity? First, the complete graph has the maximal algebraic connectivity, while its high link density makes it impractical to use due to the cost of constructing links. Constraints on other network features are usually set up to incorporate realistic requirements. For example, constraint on the diameter may guarantee certain end-to-end quality of service levels such as the delay. We propose a class of clique chain structures which optimize the algebraic connectivity and many other robust features among all graphs with diameter D and size N. The optimal graph within the class can be determined either analytically or numerically. Second, complete replacement of an existing infrastructure is expensive. Thus, we design strategies for robustness optimization using minor topological modifications. These strategies are evaluated in various classes of graphs. The robustness quantification, or equivalently, the association of the performance of a service with a topological measure, may be implicit. In this case, we explore the interplay between topology and service in determining the overall performance. Many services on communications and transportation networks are based on shortest path routing. The weight of a link, such as delay or bandwidth, is generally a metric optimized via shortest path routing. Thus, link weight tuning, a mechanism to control traffic, is also considered as part of the service. The interplay between service (shortest path routing and link weight tuning) and topology is investigated for the following performance aspects: (a) the structure of the transport overlay network, which is the union of shortest paths between all node pairs and (b) the traffic distribution in the overlay network. Important new findings are (i) the universal phase transition in overlay structures as we tune the link weight structure over different classes of networks and (ii) the power law traffic distribution in the overlay networks when link weights vary strongly in various classes of networks. Furthermore, we consider the service that measures a network topology as the union of shortest paths among a set of testboxes (nodes). The measured topology is a subgraph of the overlay network, which is again a subgraph of the actual network. The performance in terms of the sampling bias of measuring a network topology is investigated. Our work contributes substantially to a better understanding of the effect of the service (testbox selection) and the actual network structure on the performance with respect to sampling bias. Our investigations on the interplay between service and network reveal again the association between the performance of a service and certain topological feature, and thus, contribute to the quantification of network robustness. The multidisciplinary nature of this research lies not only in the presence of robustness issues in many complex networks, but also in that advances in other disciplines such as graph theory, combinatorics, linear algebra and statistical physics are widely applied throughout the thesis to study optimization problems and the performance of large networks.

Network robustness is the ability of a road network functioning properly facing unpredictable and exceptional incidents. A systematical framework with combined dynamic traffic assignment (DTA) models is designed for the analysis of road network robustness. With this framework, network performance considering travelers' (route) choice behavior under both normal traffic condition and incident condition can be properly described. So the robustness of road networks against incidents can be analyzed comprehensively. Based on such knowledge, road networks robustness can be improved from the planning stage or with suitable measures.

The robustness of a network is depending on the type of attack we are considering. In this paper we focus on the spread of viruses on networks. It is common practice to use the epidemic threshold as a measure for robustness. Because the epidemic threshold is inversely proportional to the largest eigenvalue of the adjacency matrix, it seems easy to compare the robustness of two networks. We will show in this paper that the comparison of the robustness with respect to virus spread for two networks actually depends on the value of the effective spreading rate τ. For this reason we propose a new metric, the viral conductance, which takes into account the complete range of values τ can obtain. In this paper we determine the viral conductance of regular graphs, complete bipartite graphs and a number of realistic networks.

Robustness of a network is a main objective for road network managers these days, and has therefore become an important study area for transportation scientists. This article discusses one specific aspect in assessing road network robustness: the consequences of the closure of a link. These spillback effects have been examined in a dedicated traffic simulator in which the representation of spillback can be switched on and off. The impacts are studied in a simulation study of a road network of a regional size in which sequentially links are blocked. Two scenarios for route choice are considered: a fixed route choice based on a daily congestion pattern and a route choice adapted to the actual congestion caused by the closure. The study has also shown the influence of information which makes travellers adapt their routes. Road network robustness and characteristics of vulnerable links are evaluated for both spillback and non-spillback cases. It is found that a valid spillback modelling is a prerequisite for correctly analysing the robustness of the network as a whole, as well as for correctly indicating the locations in the network where a closure causes the largest delays. Furthermore, without simulating spillback, it is not possible to identify correctly the most vulnerable links for the network performance.

Serious epidemics, both in cyber space as well as in our real world, are expected to occur with high probability, which justifies investigations in virus spread models in (contact) networks. The N-intertwined virus spread model of the SIS-type is introduced as a promising and analytically tractablemodel of which the steady-state behavior is fairly completely determined. Compared to the exact SIS Markov model, the N-intertwined model makes only one approximation of a mean-field kind that results in upper bounding the exact model for finite network size N and improves in accuracy with N. We review many properties theoretically, thereby showing, besides the flexibility to extend the model into an entire heterogeneous setting, that much insight can be gained that is hidden in the exact Markov model.

There is a growing awareness that road networks, are becoming more and more vulnerable to unforeseen disturbances like incidents and that measures need to be taken in order to make road networks more robust. In order to do this the following questions need to be addressed: How is robustness defined? Against which disturbances should the network be made robust? Which factors determine the robustness of a road network? What is the relationship between robustness, travel times and travel time reliability? Which indicators can be used to quantify robustness? How can these indicators be computed? This paper addresses these questions by developing a consistent framework for robustness in which a definition, terms related to robustness, indicators and an evaluation method are included. By doing this, policy makers and transportation analyst are offered a framework to discuss issues that are related to road network robustness and vulnerability which goes beyond the disconnected definitions, indicators and evaluation methods used so far in literature. Furthermore, the evaluation method that is presented for evaluating the robustness of the road network against short term variations in supply (like incidents) contributes to the problem of designing robust road networks because it has a relatively short computation time and it takes spillback effects and alternative routes into account.

Transport networks in major urban areas are becoming more and more vulnerable to unforeseen disturbances in transport networks, like incidents. For the near future, we expect an increasing number of incidents with a large impact due to the overall increase of the traffic load. In this paper the hypothesis is tested that, if no measures are taken, the impact of incidents increases in the future and, therefore, the vulnerability of the road network increases. It is shown that the current network of the area The Hague-Rotterdam in the Netherlands is already vulnerable. If the demand increases, the increase in total travel time is more than linear with the increase in demand in the situation without an incident. The impact of incidents also increases when the level of demand increases. This results in the overall conclusion that it is necessary to make the road network more robust.

Power transmission networks are large scale complex distributed and networked systems, situated in dynamic environments. Managing such systems is essentially decentralized and distributed. The main function of power transmission grids is to assure the security and reliability of the network and to avoid blackouts. Key elements that can determine the security and reliability in transmitting power are the grids topological structures as well as their physical and operational behaviors and states. The capacity of a network to cope with disturbance imposed on it defines its degree of robustness. In assessing power grids reliability, their robustness and vulnerability against failures (both random failures and intentional attacks) must be taken into account. The secure delivery of power as well as the ability to protect and react to power outage and failures must be done in a distributed environment. Improving the robustness of the grids in distributed environment with no centralized control and management is a challenge. This work propose an effective theoretical method based on complex network approaches for improving robustness of power transmission networks dynamically by reducing their vulnerability in a decentralized and distributed environment. The method is applied to test a grid system to demonstrate its effectiveness on improving the networks robustness.

Al jaren wordt er gespeculeerd over de toekomst van het Schenkviaduct in Den Haag. De staat en de leeftijd van het viaduct spelen hierin een belangrijke rol en de positie van het viaduct in het wegennetwerk. Diepgaande studies naar de toekomst van het Schenkviaduct zijn er tot nu toe nog niet geweest. De bijkomstigheid van vele factoren op het gebied van verkeerskunde en stedenbouwkunde maakt een studie naar het Schenkviaduct tot een complexe opgave. Tevens wil Den Haag zich profileren als internationale stad van vrede, recht en veiligheid. Het is dan van belang dat de bereikbaarheid van Den Haag op orde is, dat het infrastructuurnetwerk robuust is en dat het woon- en leefklimaat in Den Haag goed is. Dit moet internationale instanties verleiden om zich in Den Haag te gaan vestigen. Op het gebied van verkeer en infrastructuur valt in Den Haag nog volop winst te behalen. Het Schenkviaduct vormt een belangrijk onderdeel in de verkeersstructuur van Den Haag. De vraag van de gemeente Den Haag is dan ook of de verkeersstructuur rondom het Schenkviaduct zodanig verbeterd kan worden zodat dit bijdraagt aan een robuuster wegennet en een beter woon- en leefklimaat? Deze thesis onderzoekt hoe de robuustheid van een stedelijk wegennet vergroot kan worden. Aan de hand daarvan is een methode ontwikkeld die op het Schenkviaduct is toegepast. De methodiek heeft geleid tot een aantal alternatieven die in deze thesis op robuustheid, bereikbaarheid, leefbaarheid en ruimtelijke kwaliteit zijn getoetst.

Wireless sensor and actuator networks (WSANs) suffer from interference making them unfeasible for actuators that require reliability. This asks for an IEEE 802.15.4 behavior analysis for building automation actuators and a robust WSAN solution. This thesis uses the IEEE 802.15.4 based JenNet communication stack for experiments to define, measure, and create robustness. Failures are classified between soft and hard to identify the impact on the system. Equations are introduced to show the failure probabilities based on packet arrival probabilities. Experiments show the impact of interference on the failure rate with an increased failure rate during office hours, and a ratio between hard and soft failures ranging from 1:5 to 1:25 for single hops depending on the link quality. A setpoint based heartbeat solution is proposed that solves hard failures and copes with soft failures. Equations show the impact of different heartbeat properties on the performance of the heartbeat solution. The solution is implemented and experiments show that it meets the robust properties required by WSANs. To make a WSAN predictable and adaptive to its environment, future implementations could monitor the environment and reconsider timing properties, based on gathered data and hopcount.

This thesis focuses on the topological characterization of complex networks. It specifically focuses on those elementary graph measures that are of interest when quantifying topology-related aspects of the robustness of complex networks. This thesis makes the following contributions to the field of complex networks. Firstly, the thesis analyses the relationships among a variety of graph measures and proposes a definite set, capable of expressing the most relevant topological properties of complex networks. Secondly, the thesis relies on spectral measures to initiate a classification of the qualitative topological properties that characterize specific classes of complex networks. Thirdly, the thesis illustrates the use of spectral measures in a quantitative characterization of topology-related aspects of the network robustness. Finally, this thesis demonstrates the use of spectral measures in a quantitative characterization of the extent to which the robustness to different types of failures manifests itself in the underlying complex networks structure.

Audio fingerprints can be seen as hashes of the perceptual content of an audio excerpt. Applications include linking metadata to unlabeled audio, watermark support, and broadcast monitoring. Existing systems identify a song by comparing its fingerprint to pre-computed fingerprints in a database. Small changes of the audio induce small differences in the fingerprint. The song is identified if these fingerprint differences are small enough. In addition, we found that distances between fingerprints of the original and a compressed version can be used to estimate the quality (bitrate) of the compressed version. In this paper, we study the relationship between compression bit-rate and fingerprint differences. We present a comparative study of the response to compression using three fingerprint algorithms (each representative for a larger set of algorithms), developed at Philips, Polytechnic University of Milan, and Microsoft, respectively. We have conducted experiments both using the original algorithms and using versions modified to achieve similar operation conditions, i.e., the fingerprints use the same number of bits per second. Our study shows similar behavior for these three algorithms.

The Dutch road network is, like many other road networks in the world, congested in the morning and evening peaks. The locations of congestion are quite often the same; this makes it relatively easy to take the delay of this regular congestion into account when planning a trip. However, as a result of disturbances, also unexpectedly large delays occur. If no measures are taken, the Dutch road network, especially in major urban areas, is becoming more and more vulnerable to disturbances like incidents. This PhD study proposes a framework for robustness analysis that includes definitions, indicators and a set of measures that can be applied to make the road network robust against incidents. Furthermore, a method is developed by which robust road networks can be designed given these measures. The method combines expert knowledge with advanced modelling techniques. The quality of the method is proven by applying it to a small test network. Finally, this thesis shows how the method can be applied to a large realistic network of Amsterdam and surroundings. The practical value of the research appears from the fact that parts of it have already been used in projects for the ANWB, Verkeer en Waterstaat, de Raad voor Verkeer en Waterstaat, DVS, de stadregio Amsterdam en Bart Egeter Advies. This research is supported by the TU Delft, TNO, NGI, Transumo and TRAIL.

Biological networks exhibit intriguing topological properties such as small-worldness. In this paper, we investigate whether the topology of a metabolic network is related to its robustness. We do so by perturbing a metabolic system in silico, one reaction at a time and studying the correlations between growth, as predicted by flux balance analysis, and a number of topological metrics, as computed from three network representations of the metabolic system. We find that a small number of metrics correlate with growth and that only one of the network representations stands out in terms of correlated metrics. The most correlated metrics point to the importance of hub nodes in this network: so-called "currency metabolites". Since they are responsible for interconnecting distant functional modules in the network, they are important points in the networks for predicting if reaction removal affects growth. Source code and data are available upon request.

In this thesis, the main focus is on the study of a real-world transportation problem with uncertainties, and on the comparison of a centralized and a distributed solution approach in the context of this problem. We formalize the real-world problem, and provide a general framework to extend it with different sources of uncertainty. We apply computer simulations to compare the two solution approaches, and provide experimental results for three uncertainty types. In release-time uncertainty instances, new orders arrive at random times during the execution of previously planned orders. In service-time uncertainty cases, the time spent by the trucks at pick-up or delivery locations are defined according to a random distribution. In truck-breakdown uncertainty instances, some of the trucks break down at random times. Finally, we also examine cases with different combinations of these uncertainties.

There is a growing awareness that road networks, especially in major urban areas, are becoming more and more vulnerable to unforeseen disturbances like incidents because of the fact that the level of congestion keeps growing. Therefore, robustness measures have to be taken. In this paper the robust road network design problem is presented as well as a solution algorithm for solving the problem. The solution algorithm combines expert knowledge with advanced modeling techniques. In this way the method can be applied to large scale networks. This paper shows the quality of the algorithm for a test network.

This thesis has two main topics. On the one hand it discusses how the robustness of a network can be increased as efficient as possible, where connectivity is treated as a robustness measure. On the other hand It treats capacity management of a network when it is still in its design phase. In particular, it shows how bandwidth management can be done on the network edges, while it also gives an implication to prioritize the vertices based on their relative importance. One of KPN's mobile core networks is treated as a case study.