Network reliability: The effect of local network structure on diffusive processes
- 21 November 2013
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 88 (5), 052810
- https://doi.org/10.1103/physreve.88.052810
Abstract
This paper reintroduces the network reliability polynomial, introduced by Moore and Shannon [Moore and Shannon, J. Franklin Inst. 262, 191 (1956)], for studying the effect of network structure on the spread of diseases. We exhibit a representation of the polynomial that is well suited for estimation by distributed simulation. We describe a collection of graphs derived from Erdős-Rényi and scale-free-like random graphs in which we have manipulated assortativity-by-degree and the number of triangles. We evaluate the network reliability for all of these graphs under a reliability rule that is related to the expected size of a connected component. Through these extensive simulations, we show that for positively or neutrally assortative graphs, swapping edges to increase the number of triangles does not increase the network reliability. Also, positively assortative graphs are more reliable than neutral or disassortative graphs with the same number of edges. Moreover, we show the combined effect of both assortativity-by-degree and the presence of triangles on the critical point and the size of the smallest subgraph that is reliable.Keywords
This publication has 25 references indexed in Scilit:
- Sensitivity of Household Transmission to Household Contact Structure and SizePLOS ONE, 2011
- An individual-based approach to SIR epidemics in contact networksJournal of Theoretical Biology, 2011
- Detail in network models of epidemiology: are we there yet?Journal of Biological Dynamics, 2010
- Modelling disease outbreaks in realistic urban social networksNature, 2004
- Epidemic outbreaks in complex heterogeneous networksZeitschrift für Physik B Condensed Matter, 2002
- Emergence of Scaling in Random NetworksScience, 1999
- The Tutte polynomialRandom Structures & Algorithms, 1999
- On the critical behavior of the general epidemic process and dynamical percolationMathematical Biosciences, 1983
- Reliable circuits using less reliable relaysJournal of the Franklin Institute, 1956
- A contribution to the mathematical theory of epidemicsProceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 1927