Learnability of complex structure from contagions of various complexities

Determining the structure of complex systems is inferential in nature; relationships between entities in that system are deduced from observational data such as paper co-authorship, proximity sensing, and contact tracing. In particular, time-series data derived from contagion processes can uncover the underlying connection patterns by determining which links best explain the state transitions in the system. Contagion processes are often described in a dichotomous way: a contagion is described as "simple" if it can be spread via a single infected contact, whereas a contagion is called "complex" if more than one exposure is required for transmission to occur. Models of simple contagion are often used in epidemiological settings, whereas complex contagion models are primarily used to describe the adoption of behaviors or opinions. We break this dichotomy by introducing a neighborhood-based susceptible-infected-susceptible (SIS) contagion model and a corresponding measure quantifying how "complex" a contagion is. We use Bayesian inference to reconstruct the contact network from time-series data generated from this contagion model and quantify the learnability of the network structure in terms of the posterior distribution of inferred contact networks. We use this contagion model and inference framework to examine how the complexity of a contagion affects the learnability of complex network structure from time series data. We show that the reconstruction of the original network is sensitive to both the contagion complexity and the average infection probability. Second, we show that the amount of data needed to recover network structure, as measured by the average number of infections per node, also depends on the contagion complexity.