Network reliability: The effect of local network structure on diffusive processes

摘要

This paper reintroduces the network reliability polynomial, introduced by Moore and Shannon [Moore andnShannon, J. Franklin Inst. 262, 191 (1956)], for studying the effect of network structure on the spread of diseases.nWe exhibit a representation of the polynomial that is well suited for estimation by distributed simulation. Wendescribe a collection of graphs derived from Erd˝os-R´enyi and scale-free-like random graphs in which we havenmanipulated assortativity-by-degree and the number of triangles. We evaluate the network reliability for all ofnthese graphs under a reliability rule that is related to the expected size of a connected component. Through thesenextensive simulations, we show that for positively or neutrally assortative graphs, swapping edges to increase thennumber of triangles does not increase the network reliability. Also, positively assortative graphs are more reliablenthan neutral or disassortative graphs with the same number of edges. Moreover, we show the combined effectnof both assortativity-by-degree and the presence of triangles on the critical point and the size of the smallestnsubgraph that is reliable.