Exact Network Reconstruction from Complete SIS Nodal State Infection Information Seems Infeasible
Bastian Prasse (TU Delft - Network Architectures and Services)
P. Van Mieghem (TU Delft - Network Architectures and Services)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The SIS dynamics of the spread of a virus crucially depend on both the network topology and the spreading parameters. Since neither the topology nor the spreading parameters are known for the majority of applications, they have to be inferred from observations of the viral spread. We propose an inference method for both topology and spreading parameters based on a maximum-a-posteriori estimation approach for the sampled-time Markov chain of an SIS process. The resulting estimation problem, given by a mixed-integer optimisation problem, results in exponential computational time if a brute-force approach is employed. By introducing an efficient and accurate, polynomial-time heuristic, the topology of the network can almost always be exactly reconstructed. Notwithstanding, reconstructing the network with a reasonably high accuracy requires a subexponentially increasing number of observations and an exponentially increasing computation time with respect to the number of nodes N. Such long observation periods are hardly realistic, which justifies the claim in the title.