Stochastic spreading processes on networks

Doctor of PhilosophyDepartment of Electrical and Computer EngineeringCaterina M. ScoglioSpreading processes appear in diverse natural and technological systems, such as the spread of infectious diseases and the dissemination of information. It has been demonstrated that the structure of interaction among population members can dramatically influence spreading dynamics. Therefore, researchers have focused on studying spreading processes over complex networks, where interaction among individuals could be highly heterogeneous. This dissertation aims to add to the current understanding of networked spreading processes by investigating various aspects of the Susceptible-Infected-Susceptible (SIS) model. Our first contribution is related to the inverse problem of continuous time SIS spreading over a graph. In other words, we show the possibility of inferring the underlying network from observations on the node states through time. We formulate the inverse problem as a Bayesian inference problem and find the posterior probabilities for the existence of uncertain links. Second, we study the SIS spreading process over time dependent networks, where the contact network's links are not permanent. To analyze the effect of link durations on the epidemic threshold of the SIS process, we develop a temporal network model. In this model, the temporal links result from the transition of nodes between two auxiliary node states, namely active and inactive. Combining the dynamics of the network and the spreading process, we derive the mean-field equations that describe SIS spreading processes over such temporal networks. The analysis of these equations reveals the effect of link durations on the epidemic threshold in the SIS process. Third, we study the localization of epidemics in the SIS process. In general, the SIS model has an absorbing state where all individuals are healthy. However, depending on the infection rate value, this process can reach a metastable state, where the infection does not die out. In this metastable state, some parts of the network can be disproportionately infected. We quantify the infection dispersion in the network, and formulate a convex optimization problem to find an upper bound for the dispersion of infection in the network. Finally, we focus on the estimation of spreading data from partially available information. In general, various spreading-related functions are defined over the nodes of a network. Assuming access to the values of a function for a subset of the nodes, we use the concept of effective resistance distance and feed forward neural networks, to estimate the function for the remaining nodes. Although this dissertation focuses on the SIS model, the methods we have presented and developed here are applicable to a broad range of stochastic networked spreading processes. The exact mathematical treatment of such processes is intractable due to their exponential space size, and therefore there are still various unknown aspects of their behavior that require further work. Our studies in this dissertation advance the current knowledge about networked spreading models