Optimal information diffusion in stochastic block models

We use the linear threshold model to study the diffusion of information on a network generated by the stochastic block model. We focus our analysis on a two-community structure where the initial set of informed nodes lies only in one of the two communities and we look for optimal network structures, i.e., those maximizing the asymptotic extent of the diffusion. We find that, constraining the mean degree and the fraction of initially informed nodes, the optimal structure can be assortative (modular), core-periphery, or even disassortative. We then look for minimal cost structures, i.e., those for which a minimal fraction of initially informed nodes is needed to trigger a global cascade. We find that the optimal networks are assortative but with a structure very close to a core-periphery graph, i.e., a very dense community linked to a much more sparsely connected periphery.

Figure 1

Different structures generated by the stochastic block model, namely disassortative, assortative, and core-periphery networks. Group 1 is described by white nodes and group 2 by yellow nodes.

Figure 2

(a) Phase diagram for the mean value of the density $\rho \left(\infty \right)$ obtained simulating the LTM dynamics in the case: $N=1000,n=2,z=20,\theta =0.4,{\rho }_1\left(0\right)=0.34$. (b) Phase diagram describing $\rho \left(\infty \right)$ computed from the treelike approximation of Eq. (A4). The hexagram stands for the Erdős-Rényi graph. The star-dotted red segment represents the parametric region studied by Nematzadeh et al. [19], i.e., the symmetric modular structure (Sym. Mod.). We use a mesh $N\mathrm{\Delta }{p}_{11}=N\mathrm{\Delta }{p}_{12}=1$.

Figure 3

(a), (b), and (c) show the asymptotic densities $\rho \left(\infty \right), {\rho }_1\left(\infty \right), {\rho }_2\left(\infty \right)$ as a function of the initial density of informed nodes ${\rho }_1\left(0\right)$, for the case $N=1000,n=2,z=20,\theta =0.4$. The legend reports the values of the parameter $N{p}_{12}$. The internal connectivity of group 1 is constant: $N{p}_{11}=4$. We use a mesh $N\mathrm{\Delta }{p}_{11}=N\mathrm{\Delta }{p}_{12}=4$. The dark vertical dotted line indicates the value ${\rho }_1\left(0\right)=0.34$, corresponding to asymptotic densities showed in Fig. 2.

Figure 4

(a), (b), and (c) show the asymptotic densities $\rho \left(\infty \right), {\rho }_1\left(\infty \right), {\rho }_2\left(\infty \right)$ as a function of the initial density of informed nodes ${\rho }_1\left(0\right)$, for the case $N=1000,n=2,z=20,\theta =0.4$. The legend reports the values of the parameter $N{p}_{12}$. The internal connectivity of group 1 is constant: $N{p}_{11}=20$. We use a mesh $N\mathrm{\Delta }{p}_{11}=N\mathrm{\Delta }{p}_{12}=4$. The dark vertical dotted line indicates the value ${\rho }_1\left(0\right)=0.34$, corresponding to asymptotic densities showed in Fig. 2.

Figure 5

Values of the tipping points ${\rho }_c$ of the initial density of group 1 for $\rho \left(\infty \right)$, i.e., the global network, are shown in (a) and for ${\rho }_2\left(\infty \right)$, i.e., the initially uninformed component, are shown in (b) as a function of the network structure. The values of $\rho \left(\infty \right)$ obtained by solving numerically the treelike equations are shown in (c). We report results relative to the simulations in the case $N=1000,n=2,z=20,\theta =0.4$. The white region near $(0,0)$ indicates the absence of tipping points. The white region above the main diagonal indicates the not feasible region where $p_{22}<0$. The area bounded by the black thick line corresponds to SBMs where a global cascade $\left[\rho \right(\infty )=1]$ is observed. Finally, the red crosses ($Cos{t}_{\min }$) correspond to the optimal structures.