  Predicting the viral dynamics of an epidemic process requires the knowledge
of the underlying contact network. However, the network is not known for most
applications and has to be inferred from observing the viral state evolution
instead. We propose a polynomial-time network reconstruction algorithm for the
discrete-time NIMFA model based on a basis pursuit formulation. Given only few
initial viral state observations, the network reconstruction method allows for
an accurate prediction of the further viral state evolution of every node
provided that the network is sufficiently sparse.
