Morphological inversion of complex diffusion

Epidemics, neural cascades, power failures, and many other phenomena can be described by a diffusion process on a network. To identify the causal origins of a spread, it is often necessary to identify the triggering initial node. Here, we define a new morphological operator and use it to detect the origin of a diffusive front, given the final state of a complex network. Our method performs better than algorithms based on distance (closeness) and Jordan centrality. More importantly, our method is applicable regardless of the specifics of the forward model, and therefore can be applied to a wide range of systems such as identifying the patient zero in an epidemic, pinpointing the neuron that triggers a cascade, identifying the original malfunction that causes a catastrophic infrastructure failure, and inferring the ancestral species from which a heterogeneous population evolves.

Figure 1

Example of classical erosion (a,b), our generalization (c,d), erosion on a network (e). (a) The structuring element (“stencil”) is placed on individual pixels whose neighborhoods are checked for a match or mismatch. (b) Pixels are eroded if there is a mismatch with the stencil. In the end, shapes lose their outer layers. (c) The network and candidate set (solid fill) is given while the seed (dark star) is unknown. (d) The erosion stencil (gradient fill) for candidate i (light star) is applied over the network. Smiley faces show the locations where the stencil matches the given network state, question marks show locations of high variability, and sad faces show regions where the stencil does not match the candidate set. Note that the planar representation for the stencils does not mean that our stencils are limited to planar graphs. All nodes are part of the stencil for any given node for a general diffusion dynamic. (e) An example of deterministic diffusion of a single seed for one discrete time step. The necessary stencil is one in which all neighbors are affected by the diffusion but no one else because there is not enough time to reach anything outside of direct neighbors. For this reason, the node in the top left was also eroded.

Figure 2

Performance on different networks and models as a function of the transmission probability $\lambda$, for $T=5$ (larger is better). The protein interaction network ($n=3744,m=7749$), power grid network ($n=4941,m=6594$), and scale-free network ($n=4941,m=6601$) are shown in each column. The four dynamic models are shown in each row. Note the difference between the uniform transmission probability, $\lambda$, for isotropic diffusion and the neutral transmission probability, $p_0$, for anisotropic diffusion. Our performance (solid lines) is almost always better than centrality-based methods (dashed and dotted lines of the same color) based on a total of 500 runs. Light red and dark blue curves denote whether the true seed is the top one or within top three choices returned, respectively. For the power grid network, both cases overlapped because the candidate set is small. The error bars represent $\pm$ one expected standard deviation for an average of 100 runs. In general, our performance closely matches the two centrality methods but becomes noticeably better as $\lambda$ or $p_0$ increases.

Figure 3

Probability that the true seed is a high-ranked node for all models and dynamics using $\lambda =0.6$ ($p_0=0.6$) $T=5$ (lower rank is better). The protein interaction network ($n=3744,m=7749$), power grid network ($n=4941,m=6594$), and scale-free network ($n=4941,m=6601$) are shown in each column. The four dynamic models are shown in each row. The protein and scale-free networks have larger spreads than the grid network and therefore will have a larger distribution for the rank sizes. Our method (solid lines) generally outperforms the two centrality methods based on a total of 500 runs. Note that Jordan centrality provides much better performance than distance (closeness) centrality. The error bars represent $\pm$ one expected standard deviation for an average of 100 runs.

Figure 4

Our method vs the Jaccard-Gaussian method developed by Antulov-Fantulin et al. in Ref. [13] on the scale-free graph ($n=4941, m=6601$). (a) Probability of finding the true seed within top 1 (light red) and top 1% (dark blue) candidate nodes. Overall, the Jaccard-Gaussian method has better performance when $\lambda <0.5$, after which our method is better. In all cases, both methods were limited to using the same set of 134 simulated runs (stencil), where each data point was generated from independent test sets of 500 runs. However, only runs which satisfies the Jaccard-Gaussian convergence condition [Eq. (3)] were used in these plots. (b) How often a highly ranked node is the true seed ($\lambda =0.7, T=5$). Both methods used the same set (stencil) of 667 simulated runs for their algorithms. The spectrum is generated from testing the performance of each method for 500 runs. Additionally, the error bars were generated by randomly selecting 100 runs and calculating the deviation from average across all runs. Therefore, the error bars represent the expected standard deviation for a sample size of 100 runs.

Figure 5

Error distance $\delta$ for the power grid network ($n=4941, m=6594$). $\delta$ is the distance between the top candidate and the true origin.

Figure 6

Error distance $\delta$ for the scale-free network ($n=4941, m=6601$). $\delta$ is the distance between the top candidate and the true origin.

Figure 7

Error distance $\delta$ for the protein interaction network ($n=3744, m=7749$). $\delta$ is the distance between the top candidate and the true origin.

Figure 8

Average diffusion sizes.