Network Reconstruction from a Single Information Cascade

Network representation provides a natural framework for the study of real world complex systems. In many cases, however, a faithful network representation that captures the interaction between individual components is not readily available. With enough data such interactions can be uncovered, but most real-world phenomena manifest in the form of a single cascade of infections or behaviors (more generally referred to as information) that percolates through the network. This problem can be represented as reconstructing a network where node states are visible as they reach a certain threshold. In this paper, we model an information cascade as the step response of a linear time invariant (LTI) directed network of nodes having first order dynamics. This simple representation allows us to solve for individual nodal parameters and the associated combinations of edges using data from a single perturbation. As expected, we obtain more than one valid network solutions that are able to recreate the response. We therefore evaluate the dependence of the number of valid network solutions on the amount of prior knowledge about node dynamics or connectivity. This is particularly relevant in situations where the experimenter may be able to generalize nodal dynamics or local topology within a network. Our results indicate that the number of solutions can be greatly reduced provided some knowledge of nodal parameters and network topology is available.