Network Process: How Topology Impacts the Dynamics of Epidemics and Cascading Failures

Network processes model how information, virus, or failures interact and spread in a system or population. The network structure captures relationships or contacts betweenmultiple, interactive agents. Network processes also account for the dynamical characteristics of these interactions. These models can give insights on how to respond to outbreaks as well as on how to design optimal distributed, network structures for engineering purposes.These processes are complex to study because of inherent dependencies between topology and dynamics. The inclusion of finite-size networks introduces combinatorial complexity, making analysis computationally intractable for large networks. Consequently, existing approachesrely on simulation or coarse approximations of the underlying network structures. The thesis presents and studies the scaled SIS process, a model for which the exactnetwork structure can be accounted for exactly. The scaled SIS process is an epidemics-like, binary-state, stochastic process on an arbitrary, undirected network whose nodes represent agents and edges represent contacts. Contagion of healthy agents by infected neighbors can potentially overcome the healing process leading to epidemics. Alternatively, the scaled SIS process can also be used to model cascading failures like blackouts in the power grid.The scaled SIS process has a closed-form steady-state characterization (i.e., equilibrium distribution) of the Gibbs form, making it appropriate to study the effects of networktopology and dynamics on the steady-state behavior of the process. We use the equilibrium distribution to formulate and study network vulnerability on 3 different scales: 1) individual agents, 2) substructures in the network, and 3) overall network. With tools from discrete optimization and Monte Carlo sampling, we can solve or accuratelyapproximate the solutions to these inference problems for network processes on arbitrary, real-world networks in polynomial-time. When infection and healing rates are extreme, the topology of the underlying network is unimportant. For the appropriate range ofdynamics parameters, however, topology becomes an important factor in determining vulnerability;the macroscopic characterization of network vulnerability is not representative of the microscopic vulnerability of the individual agents. We show, using the scaled SIS process, that, when the contagion rate is low, agents with more neighbors have higher probability of being infected at equilibrium. When the contagion rate is high, local characterizations such as the node degree is not sufficient; agent vulnerability depends on membershipin dense subgraphs in the network. Finally, we use the scaled SIS process to study other network process models such as the extended contact process as well as edge-centric network processes like the dynamicbond percolation process.