Exploring Watts' Cascade Boundary
Daniel Whitney
MIT
Full text:
PDF
Last modified: October 3, 2007
Abstract
Watts’ “Simple Model of Global Cascades on Random Networks” used long loop/no loop percolation theory to derive a region in which a small trigger causes a finite fraction of an infinite number of nodes to flip from “off” to “on” based on the states of their neighbors according to a simple threshold rule. The the upper boundary of this region (at values of z >> 1 that depend on the threshold) was determined by the resistance of nodes to being flipped due to their many connections to stable nodes. Experiments on finite networks revealed a similar upper boundary, displaced upward from the theoretical boundary toward larger values of z. In this paper we explore this upper boundary region closely via simulations and find that total network cascades or TNCs (cascades that essentially consume the entire finite network) can start when, for example, as few as 2 vulnerable nodes in a network of 10000 nodes are flipped initially by a single seed and no cluster of vulnerable nodes larger than 21 exists. TNCs are not the cascades predicted by long loop/no loop percolation theory, and the mechanism by which TNCs start is not described by that theory. Instead a different mechanism is involved in which a particular short loop motif comprising patterns of linkages between vulnerable and stable nodes must be present in sufficient quantity to allow the cascade to hop from the initially struck clusters to others. While the clusterhopping mechanism is necessary to start the cascade, the emergence of a TNC requires the presence of relatively large clusters of vulnerable nodes, and the shrinkage of the size of these largest clusters relative to network size is a major factor in the disappearance of TNCs as networks with the same nominal z get larger. This kind of cascade is also enhanced if the network is artificially altered by degreepreserving rewiring to have positive degree correlation or increased clustering coefficient. Each enhances the likelihood of TNCs by a different mechanism. Great variability is observed in nominally identical random networks with the same z with respect to properties such as the amount and distribution of the clusterhopping motif and the size of the largest vulnerable cluster. This means that metrics based on first moments of these or other characteristics are unlikely to reveal which networks are susceptible to TNCs.


