Exact Network Reconstruction from Complete SIS Nodal State Infection Information Seems Infeasible

Exact Network Reconstruction from Complete SIS Nodal State Infection Information Seems Infeasible

Prasse, B. (TU Delft Network Architectures and Services)
Van Mieghem, P.F.A. (TU Delft Network Architectures and Services)

2019

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.

Bayesian estimation
network reconstruction
SIS process
spreading parameter estimation

http://resolver.tudelft.nl/uuid:3689aa94-0704-408d-a7ee-0a85792ba8f5

https://doi.org/10.1109/TNSE.2018.2872511

IEEE Transactions on Network Science and Engineering, 6 (4), 748-759

Institutional Repository

journal article

© 2019 B. Prasse, P.F.A. Van Mieghem