Learning Network Structures from Contagion
This work addresses network inference for researchers in computational social science or epidemiology, but it is incremental as it extends existing algorithms to more general network classes.
The paper tackles the problem of learning network structures from contagion processes, proving that a modified algorithm works on networks with large girth and low path growth rate or bounded degree, providing a theoretical explanation for prior empirical results.
In 2014, Amin, Heidari, and Kearns proved that tree networks can be learned by observing only the infected set of vertices of the contagion process under the independent cascade model, in both the active and passive query models. They also showed empirically that simple extensions of their algorithms work on sparse networks. In this work, we focus on the active model. We prove that a simple modification of Amin et al.'s algorithm works on more general classes of networks, namely (i) networks with large girth and low path growth rate, and (ii) networks with bounded degree. This also provides partial theoretical explanation for Amin et al.'s experiments on sparse networks.