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

Bastian Prasse*, Piet Van Mieghem

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
47 Downloads (Pure)


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.

Original languageEnglish
Article number8476203
Pages (from-to)748-759
Number of pages12
JournalIEEE Transactions on Network Science and Engineering
Issue number4
Publication statusPublished - 2019


  • Bayesian estimation
  • network reconstruction
  • SIS process
  • spreading parameter estimation


Dive into the research topics of 'Exact Network Reconstruction from Complete SIS Nodal State Infection Information Seems Infeasible'. Together they form a unique fingerprint.

Cite this