As we have learned in class we can represent data in the form of networks which we can use to better understand systems. One such useful application of networks is in the analysis of how disease spreads among the population. One study from 2005 called “The Impacts of Network Topology on Disease Spread” uses various random networks to do just that.
In the study it randomly generated four different types of networks of 500 nodes with similar amount of edges, but randomly assigned. The following types of networks were exactly like the ones we learned in class:
(i) – The Erdős–Rényi model (1960) which we learned in class as Gnp. As we know these random networks have low clustering coefficients and a binomial degree distribution.
(ii) – Regular lattices where each node is connect to k nearest neighbours to form either a grid of an array. These networks has a high clustering coefficient, but relatively high average path length since nodes only connect to their nearest neighbours.
(iii) – Rewired lattices (Watts-Strogatz 1998) where we start with a low-dimensional lattice (grid or array) and rewire to introduce randomness (“shortcuts”). By rewiring this introduces more clustering and short paths, thus lowering the average path length.
(iv) – Scale-free networks that have a power-law tail in their degree distribution. These networks have small average path lengths and low clustering.
The following are the properties of the various networks randomly generated with a set amount of vertices (nodes) and similar amount of edges. It is interesting to note that the average path length.
| Network type | n (vertices) | M (edges) | K (degree) | C (clustering) | D (length) | S (significance) |
| Random graph (RG) | 500 | 1905 (33.9) | 7.62 (2.71) | 0.02 (0.00) | 5.67 (2.19) | 4.47 (0.25) |
| Scale-free network (SF) | 500 | 1990 | 7.96 (8.18) | 0.07 (0.00) | 2.93 (0.02) | 5.60 (0.04) |
| 1D lattice (1D) | 500 | 2000 | 8.00 | 0.64 | 31.69 | 1.39 |
| 2D lattice (2D) | 500 | 1865 | 7.46 | 0.23 | 8.00 | 1.84 |
| Rewired 1D lattice (1DR) | 500 | 2000 | 8.00 (0.35) | 0.62 (0.00) | 8.19 (0.45) | 1.59 (0.02) |
| Rewired 2D lattice (2DR) | 500 | 1865 | 7.46 (0.33) | 0.21 (0.00) | 4.95 (0.05) | 1.96 (0.01) |
The nodes in these networks representing susceptible individuals to diseases and the edges representing a potential method of transmission for the disease. An infected node has a certain probability to infect all its neignbours after each time step. After a node infects another node, there is a time delay until that node becomes capable of infecting other nodes. Even after that, there is a time latency until an infected node becomes immune to the disease, thus non-infectious. Initially one node is infected in a network and the researchers analyzed how the disease spread through the network. They ran many simulations with varying infection probability on all of the types of graphs found that network types had an impact on how fast the epidemic spread. From fastest to slowest rate of infection:
- Scale-free network
- The Erdős–Rényi model (1960) (Gnp )
- Rewired 2D lattice
- 2D lattice
- Rewired 1D lattice
- 1D lattice
It is interesting to note that scale-free networks resulted in the largest epidemics for any level of infection. It reached the maximum epidemic size of 500 sooner than the other networks for any probability of infection. 1D lattices never reached the max epidemic size and grew linearly.
It is important to ask why is it that epidemics spread quickly in scale-free networks but spread poorly in 1D lattice networks. The high average path length in 1D lattices and low average path length in scale-free networks helps explain that. In 1D lattices the high average path lengths prevents the infectious nodes from spreading the infection to distant clusters. The infection only grows outwards from the inital cluster. In scale-free networks, the low average path lengths enable infectious nodes to infect far away clusters which help quicken the spread of the infection. It now becomes clear why the rewired 2D lattice and rewired 1D lattice spread infections better than their non-rewired counterpart. The rewiring introduces more shortcut paths which lower the average path length which helps spread the infection faster.
Although the these were simulations on randomly generated networks, they show how understanding networks, random networks in this case, can help us understand real life problems.
References:
Shirley, Mark D.f., and Steve P. Rushton. “The Impacts of Network Topology on Disease Spread.” Ecological Complexity, vol. 2, no. 3, 2005, pp. 287–299., doi:10.1016/j.ecocom.2005.04.005.