Inferring network structure from cascades

Many physical, biological, and social phenomena can be described by cascades taking place on a network. Often, the activity can be empirically observed, but not the underlying network of interactions. In this paper we offer three topological methods to infer the structure of any directed network given a set of cascade arrival times. Our formulas hold for a very general class of models where the activation probability of a node is a generic function of its degree and the number of its active neighbors. We report high success rates for synthetic and real networks, for several different cascade models.

Figure 1

Accuracy versus model parameters, for a specific model. We evaluate our success rate using the three reported methods here, for a threshold model $f(m/k)$ that is equal to $\gamma$ for $m/k<f_c$ and $\epsilon$ when $m/k>f_c$. We sweep the parameter space and plot the success rate as a function $\gamma ,\epsilon ,f_c$, (while keeping the other two constant at $\gamma =0.04,\epsilon =0.6,f_c=0.4$). For all runs the edges and network size are $E=1484$ and $N=200$. Number of experiments (cascades) is 2000 for semiempirical and theoretical methods except in the bottom right plot where we plot accuracy vs number of experiments. For the heuristic method, the number of experiments is appropriately chosen according to the bottom right plot to give high accuracy. We evaluate other models $f(m/k)$ in Table 1.

Figure 2

Scalability of our methods, for a specific model. We evaluate our success rate for networks of various sizes and densities. The threshold model with $f_c=0.4,\gamma =0.04$, and $\epsilon =0.6$ is used for cascades. Number of experiments (cascades) is 1600 in the first plot, is equal to the number of edges in the second plot, and is equal to 0.4 times the number of possible edges [i.e., $0.4N(N-1)]$ in the last plot. Edge density is fixed at 4% in the last plot.