Spread of information and infection on finite random networks

The modeling of epidemic-like processes on random networks has received considerable attention in recent years. While these processes are inherently stochastic, most previous work has been focused on deterministic models that ignore important fluctuations that may persist even in the infinite network size limit. In a previous paper, for a class of epidemic and rumor processes, we derived approximate models for the full probability distribution of the final size of the epidemic, as opposed to only mean values. In this paper we examine via direct simulations the adequacy of the approximate model to describe stochastic epidemics and rumors on several random network topologies: homogeneous networks, Erdös-Rényi (ER) random graphs, Barabasi-Albert scale-free networks, and random geometric graphs. We find that the approximate model is reasonably accurate in predicting the probability of spread. However, the position of the threshold and the conditional mean of the final size for processes near the threshold are not well described by the approximate model even in the case of homogeneous networks. We attribute this failure to the presence of other structural properties beyond degree-degree correlations, and in particular clustering, which are present in any finite network but are not incorporated in the approximate model. In order to test this “hypothesis”  we perform additional simulations on a set of ER random graphs where degree-degree correlations and clustering are separately and independently introduced using recently proposed algorithms from the literature. Our results show that even strong degree-degree correlations have only weak effects on the position of the threshold and the conditional mean of the final size. On the other hand, the introduction of clustering greatly affects both the position of the threshold and the conditional mean. Similar analysis for the Barabasi-Albert scale-free network confirms the significance of clustering on the dynamics of rumor spread. For this network, though, with its highly skewed degree distribution, the addition of positive correlation had a much stronger effect on the final size distribution than was found for the simple random graph.

Figure 1

Comparison of final size distributions as percentages of the total population for the homogeneous network using the approximate and full models on a network with 1000 nodes, $\lambda =1$, $k=6$, $p=0.1$; p_sp is the probability of spreading to above $1\%$ of the population; mean_sp is the conditional mean final size, given that the rumor has spread to above $1\%$ of the population.

Figure 2

Thresholds for the homogeneous network with $\lambda k$ fixed at 6, $p=0.1$.

Figure 3

Final size distributions as a percentage of total population for different network structures with 1000 nodes, $\lambda =1$, $k=6$, $p=0.1$; p_sp is the probability of spreading to above $1\%$ of the population; mean_sp is the conditional mean final size, given that the rumor has spread to above $1\%$ of the population.

Figure 4

A comparison of the full and the approximate models for different network structures; all have 1000 nodes; $\lambda k=6$, $p=0.1$.

Figure 5

Illustration of the effect of correlation and clustering on network structure.

Figure 6

Final size distributions as a percentage of total population for the ER network with added correlation or clustering; 1000 nodes, $\lambda =1$, $k=6$, $p=0.1$; p_sp is the probability of spreading to above $1\%$ of the population; mean_sp is the conditional mean final size, given that the rumor has spread to above $1\%$ of the population.

Figure 7

The impact of correlation and clustering on the conditional spread (expressed as a percentage of the total population) for networks with a Poisson degree distribution; networks have 1000 nodes; $\lambda k=6$, $p=0.1.$

Figure 8

The impact of correlation and clustering on the conditional spread (expressed as a percentage of the total population) for scale-free networks; networks have 1000 nodes; $\lambda k=6$, $p=0.1.$