Impact of community structure on information transfer

The observation that real complex networks have internal structure has important implication for dynamic processes occurring on such topologies. Here we investigate the impact of community structure on a model of information transfer able to deal with both search and congestion simultaneously. We show that networks with fuzzy community structure are more efficient in terms of packet delivery than those with pronounced community structure. We also propose an alternative packet routing algorithm which takes advantage of the knowledge of communities to improve information transfer and show that in the context of the model an intermediate level of community structure is optimal. Finally, we show that in a hierarchical network setting, providing knowledge of communities at the level of highest modularity will improve network capacity by the largest amount.

Figure 1

(Color online) Each point represents the number of packets averaged over 100 realizations in the steady state of the dynamics. (a) Number of floating packets as a function of $\rho$ using the original search algorithm in networks with one level of community structure. The different colors denote varying levels of community strength as controlled by the parameter $Z_{\text{in}}$ and the vertical lines correspond to the analytical prediction of the onset of congestion [Sec. 2, Eq. (1)]. (b) Onset of congestion ${\rho }_c$ for varying $Z_{\text{in}}$.

Figure 2

(Color online) Number of floating packets as a function of $\rho$ using the original search in networks with hierarchical community structure on two levels. The vertical lines correspond to analytical prediction of the onset of congestion.

Figure 3

(Color online) Comparison of the original search algorithm with the modified search algorithm for the same networks with community structure. The number of floating packets is plotted against $\rho$. The four panels depict four networks with varying community strength controlled by the parameter $Z_{\text{in}}$, and the red points show the original search algorithm and the black points denote the modified algorithm incorporating community information.

Figure 4

(Color online) Onset of collapse for the modified search algorithm as applied to networks with community structure at a single level. (a) Number of floating packets as a function of $\rho$ for the modified search. Different colors denote varying community strengths, controlled by parameter $Z_{\text{in}}$ and the vertical lines now denote the estimate of the onset of congestion ${\rho }_c$. (b) ${\rho }_c$ as a function of internal connectivity $Z_{\text{in}}$ for both the original model (denoted $r=1$) and the modified model (denoted $r=1$ com).

Figure 5

(Color online) Number of floating packets in networks with hierarchical community structure. The number of floating packets is shown as a function of $\rho$ for three slightly different hierarchical networks, (a) 13-4, (b) 14-3, and (c) 15-2. For each, the level of community hierarchy information packets are given as varied between no information given $i=0$, information given at the first level $i=4$, and information given at the second level $i=16$. The vertical lines represent the analytical calculation as in Sec. 2 for the original search algorithm.