Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T07:21:32.227Z Has data issue: false hasContentIssue false
  • English
  • Français

Single-seed cascades on clustered networks

Published online by Cambridge University Press:  02 September 2020

John K. McSweeney Open the ORCID record for John K. McSweeney [Opens in a new window]
John K. McSweeney*
Affiliation:
Rose-Hulman Institute of Technology, Terre Haute, IN47803, USA
*
Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a dynamic network cascade process developed by Duncan Watts applied to a class of random networks, developed independently by Newman and Miller, which allows a specified amount of clustering (short loops). We adapt existing methods for locally tree-like networks to formulate an appropriate two-type branching process to describe the spread of a cascade started with a single active node and obtain a fixed-point equation to implicitly express the extinction probability of such a cascade. In so doing, we also recover a formula that has appeared in various forms in works by Hackett et al. and Miller which provides a threshold condition for certain extinction of the cascade. We find that clustering impedes cascade propagation for networks of low average degree by reducing the connectivity of the network, but for networks with high average degree, the presence of small cycles makes cascades more likely.

Keywords

cascade processconfiguration modelthreshold behaviorclustered network
Type
Research Article
Information
Network Science , Volume 9 , Issue 1 , March 2021 , pp. 59 - 72
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Action Editor: Ulrik Brandes

References

Adler, J. (1991). Bootstrap percolation. Physica A, 171, 453–470.CrossRefGoogle Scholar
Amini, H. (2010). Bootstrap percolation and diffusion in random graphs with given vertex degrees. Electronic Journal of Combinatorics, 17, R25.CrossRefGoogle Scholar
Arthur, W. B. (1989). Competing technologies, increasing returns, and lock-in by historical events. The Economic Journal, 99(394), 116–131.CrossRefGoogle Scholar
Dobson, I., Carreras, B. A., & Newman, D. E. (2005). A loading-dependent model of probabilistic cascading failure. Probability in the Engineering and Informational Sciences, 19, 15–32.CrossRefGoogle Scholar
Durrett, R. (2006). Random graph dynamics. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Feller, W. (1950). An introduction to probability theory and its applications, volume. i (3rd ed.). John Wiley & Sons.Google Scholar
Galstyan, A., & Cohen, P. (2007). Cascading dynamics in modular networks. Physical Review E, 75, 036109.CrossRefGoogle ScholarPubMed
Gleeson, J. P. (2008). Cascades on correlated and modular random networks. Physical Review E, 77, 046117.CrossRefGoogle ScholarPubMed
Gleeson, J. P., & Cahalane, D. J. (2007). Seed size strongly affects cascades on random networks. Physical Review E, 75, 056103.CrossRefGoogle ScholarPubMed
Gleeson, J. P., Melnik, S., & Hackett, A. (2010). How clustering affects the bond percolation threshold in complex networks. Physical Review E, 81, 066114.CrossRefGoogle ScholarPubMed
Hackett, A., Melnik, S., & Gleeson, J. P. (2011). Cascades on a class of clustered random networks. Physical Review E, 83, 056107.CrossRefGoogle ScholarPubMed
Hurd, T. R., & Gleeson, J. P. (2011). A framework for analyzing contagion in banking networks. Michael J. Brennan Irish Finance Working Paper Series, No. 18-14.CrossRefGoogle Scholar
Ikeda, Y., Hasegawa, T., & Nemoto, K. (2010). Cascade dynamics on clustered network. 7th International Conference on Applications of Physics in Financial Analysis, Journal of Physics: Conference Series, 221.Google Scholar
Kosterev, D. N., Taylor, C. W., & Mittelstadt, W. A. (1999). Model validation for the August 10, 1996 WSCC system outage. IEEE Transactions on Power Systems, 14, 967–979.CrossRefGoogle Scholar
McSweeney, J. K. (2016). Crossword puzzle analysis via a random network process. In Beineke, J., & Rosenhouse, J. (Eds.), The mathematics of various entertaining subjects: Research in recreational math. Princeton: Princeton University Press.Google Scholar
Miller, J. C. (2009). Percolation and epidemics in random clustered networks. Physical Review E, 80, 020901.CrossRefGoogle ScholarPubMed
Miller, J. C. (2016a). Equivalence of several generalized percolation models on networks. Physical Review E, 94, 032313.CrossRefGoogle ScholarPubMed
Miller, J. C. (2016b). Complex contagions and hybrid phase transitions. Journal of Complex Networks, 4(2), 201–223.CrossRefGoogle Scholar
Molloy, M., & Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2–3), 161–180.CrossRefGoogle Scholar
Newman, M. E. J. (2009). Random graphs with clustering. Physical Review Letters, 103, 058701.CrossRefGoogle ScholarPubMed
Watts, D. J. (2002). A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, 99(9), 5766–5771.CrossRefGoogle ScholarPubMed
Whitney, D. (2009). A dynamic model of cascades on random networks with a threshold rule. arXiv:0911.4499.Google Scholar