Complex networks appear in almost every aspect of our daily life and are widely studied in the fields of physics, mathematics, finance, biology and computer science. This work utilizes percolation theory in statistical physics to explore the percolation properties of complex networks and develops a reinforcement scheme on improving network resilience. This dissertation covers two major parts of my Ph.D. research on complex networks: i) probe—in the context of both traditional percolation and k-core percolation—the resilience of complex networks with tunable degree distributions or directed dependency links under random, localized or targeted attacks; ii) develop and propose a reinforcement scheme to eradicate catastrophic collapses that occur very often in interdependent networks. We first use generating function and probabilistic methods to obtain analytical solutions to percolation properties of interest, such as the giant component size and the critical occupation probability. We study uncorrelated random networks with Poisson, bi-Poisson, power-law, and Kronecker-delta degree distributions and construct those networks which are based on the configuration model. The computer simulation results show remarkable agreement with theoretical predictions. We discover an increase of network robustness as the degree distribution broadens and a decrease of network robustness as directed dependency links come into play under random attacks. We also find that targeted attacks exert the biggest damage to the structure of both single and interdependent networks in k-core percolation. To strengthen the resilience of interdependent networks, we develop and propose a reinforcement strategy and obtain the critical amount of reinforced nodes analytically for interdependent Erdős-Rényi networks and numerically for scale-free and for random regular networks. Our mechanism leads to improvement of network stability of the West U.S. power grid. This dissertation provides us with a deeper understanding of the effects of structural features on network stability and fresher insights into designing resilient interdependent infrastructure networks.

The cyber-physical systems (CPS), such as smart grid and intelligent transportation system, permeate into our modern societies recently. The infrastructures in such systems are closely interconnected and related, e.g., the intelligent transportation system is based on the reliable communication system, which requires the stable electricity provided by power grid for the proper function. We call such mutually related systems interdependent networks. This thesis addresses the cascading failure issue in interdependent cyber physical system. We consider CPS as a system that consists of physical-resource and computational-resource networks. The failure in physical-resource network might cause the failures in computational-resource network, and vice versa. This failure may recursively occur and cause a sequence of failures in both networks. In this thesis, we propose two novel interdependence models that better capture the interdependent networks. Then, we study the effect of cascading failures using percolation theory and present the detailed mathematical analysis on failure propagation in the system. By calculating the size of functioning parts in both networks, we analyze the robustness of our models against the random attacks and failures. The cascading failures in smart grid is also investigated, where two types of cascading failures are mixed. We estimate how the node tolerance parameter T (ratio of capacity to initial workload) affect the system performance. This thesis also explores the small clusters. We give insightful views on small cluster in interdependent networks, under different interdependence models and network topologies.

Stochastic and deterministic approaches for modeling complex networks are presented. The methodology combines analysis of the structure formed by the interconnections among the elements of a network with an assessment of the vulnerability towards the propagation of cascading failures. The goal is to understand the mutual interplay between the structure of the network connections and the propagation of cascading failures. Two fundamental issues related to the optimal design and operation of complex networks are addressed. The first concerns the impact that cascading failures have on networks due to the connectivity pattern linking their components. If the state of load on the network components is high, the risk of cascade spreadings becomes significant. In this case, the needed reduction of the connectivity efficiency to prevent the propagation of failures affecting the entire system is quantified. The second issue concerns the realization of the most efficient connectivity in a network that minimizes the propagations of cascading failures. It is found that a system that routinely approaches the critical load for the onset of cascading failures during its operation should have a larger efficiency value. This allows for a smoother transition to the cascade region and for a reasonable reaction time to counteract the onset of significant cascading failures. The interplay between the structure of the network connections and the propagation of cascading failures is assessed also in interdependent networks. In these systems, the linking among several network infrastructures is necessary for their optimal and economical operation. Yet, the interdependencies introduce weaknesses due to the fact that failures may cascade from one system to other interdependent systems, possibly affecting their overall functioning. Inspired by the global efficiency, a measure of the communication capabilities among interdependent systems, i.e. the interdependency efficiency, is defined. The relations between the structural parameters, i.e. the system links and the interdependency links, and the interdependency efficiency, are also quantified, as well as the relations between the structural parameters and the vulnerability towards the propagation of cascading failures. Resorting to this knowledge, the optimal interdependency connectivity is identified. Similar to the spreading of failures, the formation of a giant component is a critical phenomenon emerging as a result of the connectivity pattern in a network. This structural transition is exploited to identify the formation of macrometastases in the developed model for metastatic colonization in tumor growth. The methods of network theory proves particularly suitable to reproduce the local interactions among tumor cells that lead to the emergent global behavior of the metastasis as a community. This model for intercellular sensing reproduces the stepwise behavior characteristic of metastatic colonization. Moreover, it prompts the consideration of a curative intervention that hinders intercellular communication, even in the presence of a significant tumor cell population. / Ph. D.

Systems such as the power grid, world wide web (WWW), and internet are categorized as complex systems because of the presence of a large number of interacting elements. For example, the WWW is estimated to have a billion webpages and understanding the dynamics of such a large number of individual agents (whose individual interactions might not be fully known) is a challenging task. Complex network representations of these systems have proved to be of great utility. Statistical physics is the study of emergence of macroscopic properties of systems from the characteristics of the interactions between individual molecules. Hence, statistical physics of complex networks has been an effective approach to study these systems. In this dissertation, I have used statistical physics to study two distinct phenomena in complex systems: i) Cascading failures and ii) Shortest paths in complex networks. Understanding cascading failures is considered to be one of the “holy grails“ in the study of complex systems such as the power grid, transportation networks, and economic systems. Studying failures of these systems as percolation on complex networks has proved to be insightful. Previously, cascading failures have been studied extensively using two different models: k-core percolation and interdependent networks. The first part of this work combines the two models into a general model, solves it analytically, and validates the theoretical predictions through extensive computer simulations. The phase diagram of the percolation transition has been systematically studied as one varies the average local k-core threshold and the coupling between networks. The phase diagram of the combined processes is very rich and includes novel features that do not appear in the models which study each of the processes separately. For example, the phase diagram consists of first- and second-order transition regions separated by two tricritical lines that merge together and enclose a two-stage transition region. In the two-stage transition, the size of the giant component undergoes a first-order jump at a certain occupation probability followed by a continuous second-order transition at a smaller occupation probability. Furthermore, at certain fixed interdependencies, the percolation transition cycles from first-order to second-order to two-stage to first-order as the k-core threshold is increased. We setup the analytical equations describing the phase boundaries of the two-stage transition region and we derive the critical exponents for each type of transition. Understanding the shortest paths between individual elements in systems like communication networks and social media networks is important in the study of information cascades in these systems. Often, large heterogeneity can be present in the connections between nodes in these networks. Certain sets of nodes can be more highly connected among themselves than with the nodes from other sets. These sets of nodes are often referred to as ’communities’. The second part of this work studies the effect of the presence of communities on the distribution of shortest paths in a network using a modular Erdős-Rényi network model. In this model, the number of communities and the degree of modularity of the network can be tuned using the parameters of the model. We find that the model reaches a percolation threshold while tuning the degree of modularity of the network and the distribution of the shortest paths in the network can be used as an indicator of how the communities are connected.

Critical infrastructure systems are essential for the continuous functionality of modern global societies. Some examples of these systems include electric energy, potable water, oil and gas, telecommunications, and the internet. Different topologies underline the structure of these networked systems. Each topology (i.e., physical layout) conditions the way in which networks transmit and distribute their flow. Also, their ability to absorb unforeseen natural or intentional disruptions depends on complex relations between network topology and optimal flow patterns. Most of the current research on large networks is focused on understanding their properties using statistical physics, or on developing advanced models to capture network dynamics. Despite these important research efforts, almost all studies concentrate on specific networks. This network-specific approach rules out a fundamental phenomenon that may jeopardize the performance predictions of current sophisticated models: network response is in general interdependent, and its performance is conditioned on the performance of additional interacting networks. Although there are recent conceptual advances in network interdependencies, current studies address the problem from a high-level point of view. For instance, they discuss the problem at the macro-level of interacting industries, or utilize economic input-output models to capture entire infrastructure interactions. This study approaches the problem of network interdependence from a more fundamental level. It focuses on network topology, flow patterns within the networks, and optimal interdependent system performance. This approach also allows for probabilistic response characterization of interdependent networked systems when subjected to disturbances of internal nature (e.g., aging, malfunctioning) or disruptions of external nature (e.g., coordinated attacks, seismic hazards). The methods proposed in this study can identify the role that each network element has in maintaining interdependent network connectivity and optimal flow. This information is used in the selection of effective pre-disaster mitigation and post-disaster recovery actions. Results of this research also provide guides for growth of interacting infrastructure networks and reveal new areas for research on interdependent dynamics. Finally, the algorithmic structure of the proposed methods suggests straightforward implementation of interdependent analysis in advanced computer software applications for multi-hazard loss estimation.

abstract: The critical infrastructures of the nation are a large and complex network of human, physical and cyber-physical systems. In recent times, it has become increasingly apparent that individual critical infrastructures, such as the power and communication networks, do not operate in isolation, but instead are part of a complex interdependent ecosystem where a failure involving a small set of network entities can trigger a cascading event resulting in the failure of a much larger set of entities through the failure propagation process. Recognizing the need for a deeper understanding of the interdependent relationships between such critical infrastructures, several models have been proposed and analyzed in the last few years. However, most of these models are over-simplified and fail to capture the complex interdependencies that may exist between critical infrastructures. To overcome the limitations of existing models, this dissertation presents a new model -- the Implicative Interdependency Model (IIM) that is able to capture such complex interdependency relations. As the potential for a failure cascade in critical interdependent networks poses several risks that can jeopardize the nation, this dissertation explores relevant research problems in the interdependent power and communication networks using the proposed IIM and lays the foundations for further study using this model. Apart from exploring problems in interdependent critical infrastructures, this dissertation also explores resource allocation techniques for environments enabled with cyber-physical systems. Specifically, the problem of efficient path planning for data collection using mobile cyber-physical systems is explored. Two such environments are considered: a Radio-Frequency IDentification (RFID) environment with mobile “Tags” and “Readers”, and a sensor data collection environment where both the sensors and the data mules (data collectors) are mobile. Finally, from an applied research perspective, this dissertation presents Raptor, an advanced network planning and management tool for mitigating the impact of spatially correlated, or region based faults on infrastructure networks. Raptor consolidates a wide range of studies conducted in the last few years on region based faults, and provides an interface for network planners, designers and operators to use the results of these studies for designing robust and resilient networks in the presence of spatially correlated faults. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2016