Small Worlds and Large Diameters

A small world network is characterized by a low average path length between any two nodes, and high clustering. Most real networks, including biological networks like protein interaction networks, are  known to have this property. Since random networks are also known to have the property of low diameter, one might think that real world networks have even shorter diameters than their random counterparts. The reason for this is that short diameters can potentially increase the network efficiency of exchanging mass and/or information, not only in biological networks (e.g. the metabolic network) but also in transportation, communication and computer networks. However, studies at the  Department of Ecology and Evolutionary Biology, University of Michigan have shown that the observed diameter in real world networks is greater than the random expectation. The following are some of the salient observations of this study.

Real networks have greater-than-expected diameters

The diameter of a real network was compared to that of its randomly rewired network in which the connections between nodes were randomized while the degree of every node remained unchanged. A total of 13 real networks examined, including two linguistic, three technological, four social, and four biological networks, were found to have diameters greater than their random expectations (Table 1). An analysis of the frequency distribution of diameters showed that the greater than expected diameters are not caused by presence of some extremely long paths, but due to the presence of many elongated minimal paths. Overall, the diameters of real networks were found to be  2.3–128.3% greater than their random expectations, with a median difference of 17.4%. Albert and Barabási had also noted earlier that many real networks have longer diameters than those computed under the power-law degree distribution.

Table 1

Real networks have greater-than-expected clustering coefficients

Small world networks have high clustering coefficients. We all have seen this in the case of protein interaction networks. In 12 of the 13 real networks examined (except the dolphin association network), the clustering coefficient C was found to be greater than the expected value determined from its randomly rewired networks, and this difference is statistically significant in 7 cases (Table 2). However, there is no consistent relationship between clustering coefficient and diameter among the randomly rewired networks of each real network (Table 2), suggesting that the greater-than-expected diameters of real networks cannot be explained by the greater-than-expected clustering coefficients. Furthermore, across the 13 real networks, the correlation between the expected C and expected D from their randomly rewired networks appears negatively (Spearman's R = −0.57, P = 0.047), while the correlation between the Z-score for C and Z-score for D is not significant (Spearman's R = −0.13, P = 0.68).

Table 2

Network modularization enlarges the diameter

If shorter diameters are beneficial to at least some networks, why do all networks have longer diameters than expected by chance? It was hypothesized that this phenomenon might relate to modularity (Newman and Girvan) in networks. Simulations were conducted to find the relation between diameter and modularity for a network with a fixed amount of nodes and edges. It was observed  that the network diameter increases as the modularity increases in these simulated networks (Fig 1a). But the relationship between diameter and modularity is not linear; when the diameter is short, a small percentage increase in diameter allows a substantial percentage increase in modularity (Fig 1a). A similar concave curve is observed when the increases in diameter and modularity are measured by Z-scores, rather than the absolute values (Fig 1b). Using a similar simulation, the relationship between modularity and diameter using networks with a fixed number of modules but different mean degrees was also confirmed.

If modularization is truly the cause of the higher-than-expected diameters of real networks, all real networks should have modularities greater than expected from their randomly rewired networks. This is indeed the case (Table 1). The percentage excess in modularity (compared to the random expectation) ranges from 4.8 to 206.9% for the 13 networks, with a median of 40.8%. This percentage excess exceeds that for diameter in 10 of the 13 networks, a nonrandom pattern that is consistent with the simulation result in Fig 1 (P = 0.046, one-tail binomial test).

 Fig 1

Implications

All networks studied, including biological networks, have diameters greater than their random expectations. This suggests that modularization may well be a universal characteristic of real networks, due to the advantages it brings to network multi-functionality, robustness and evolvability. As a consequence, the network diameter has to be sacrificed to accommodate modular structures. Because shorter diameters could provide higher functional efficiency, the result suggests a tradeoff between network efficiency and multi-functionality, robustness, and/or evolvability. Although there are many networks unstudied in this work, this analysis covers major types of networks and the results are likely to reflect a general pattern of real networks. It would be an interesting study to look for those rare real world networks for whom the diameter is actually less than their random expections and examine in what way are they different from general real world networks.

References:

[1] Zhang Z, Zhang J (2009) A Big World Inside Small-World Networks. PLoS ONE 4(5): e5686. doi:10.1371/journal.pone.0005686