Carnegie Mellon University
Browse

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

Download (10.82 MB)
thesis
posted on 2015-09-24, 00:00 authored by June Zhang
Network processes model how information, virus, or failures interact and spread in a system or population. The network structure captures relationships or contacts between
multiple, 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 approaches
rely on simulation or coarse approximations of the underlying network structures. The thesis presents and studies the scaled SIS process, a model for which the exact
network 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 network
topology 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 accurately
approximate 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 of
dynamics 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 membership
in 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 dynamic
bond percolation process.

History

Date

2015-09-24

Degree Type

  • Dissertation

Department

  • Electrical and Computer Engineering

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

José M. F. Moura