Network Reconstruction for SIS Epidemics in Heterogeneous Populations

Abstract

Exact network reconstruction from observations of the SIS process in discrete time would be very useful if possible, with implications for tracking the spread of infectious diseases, trends and news on social media. It could provide estimates for the strength of links in a network and the contribution of individual nodes to the spread of an epidemic within a network as well as the underlying structure. This Thesis provides a method for evaluating heterogeneous parameters where each node has a randomly distributed curing probability and each link between two nodes has a randomly distributed infection probability. The parameters are computed via maximum likelihood estimation using between 102 and 104 observations of the SIS process on networks ranging in size from 15 to 55 nodes, for both directed Erdős-Rényi and Barabási-Albert graphs. We vary the network size to demonstrate that for a fixed level of accuracy, the number of required observations increases exponentially with the number of nodes for both the whole network and a subset of links and nodes. We further demonstrate that it may require fewer observations to reconstruct certain nodes based on the degree of the node or reconstruct links based on the degree of the node to which the link is incident. Additionally, if we interpret 106 or more observations as the number of required observations where reconstruction becomes infeasible, a network size of 500 would be infeasible for reconstructing the full network and the approximate limit for partial network reconstruction. The Thesis is extended to look at the SI and SIR models, achieving a similar exponential increase in the number of observations required as the network size increases, for a fixed error.