- Physical Review Journals
All JournalsPhysics Magazine

Physical Review Research

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Mastering percolation-like games with deep learning

Michael M. Danziger1, Omkar R. Gojala2, and Sean P. Cornelius3,*

  • 1AI for Healthcare, IBM Research, Haifa, Israel
  • 2Network Science Institute, Northeastern University, Boston, Massachusetts, 02115, USA
  • 3Department of Physics, Toronto Metropolitan University, Toronto, Ontario M5B 2K3, Canada

  • *To whom correspondence should be addressed: cornelius@ toronotmu.ca
PDF

Phys. Rev. Research 6, 013067 – Published 17 January, 2024

DOI: https://doi.org/10.1103/PhysRevResearch.6.013067

Abstract

Though robustness of networks to random attacks has been widely studied, intentional destruction by an intelligent agent is not tractable with previous methods. Here we devise a single-player game on a lattice that mimics the logic of an attacker attempting to destroy a network. The objective of the game is to disable all nodes in the fewest number of steps. We develop a reinforcement learning approach using deep Q-learning that is capable of learning to play this game successfully, and in so doing, to optimally attack a network. Because the learning algorithm is universal, we train agents on different definitions of robustness and compare the learned strategies. We find that superficially similar definitions of robustness induce different strategies in the trained agent, implying that optimally attacking or defending a network is sensitive to the particular objective. Our method provides an approach to understand network robustness, with potential applications to other discrete processes in disordered systems.

View figure in article

Physics Subject Headings (PhySH)

Article Text

Supplemental Material

References (36)

  1. R. Albert, H. Jeong, and A.-L. Barabási, Error and attack tolerance of complex networks, Nature 406, 378 (2000).
  2. R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Resilience of the internet to random breakdowns, Phys. Rev. Lett. 85, 4626 (2000).
  3. S. Kirkpatrick, Percolation and conduction, Rev. Mod. Phys. 45, 574 (1973).
  4. D. Stauffer, Introduction to Percolation Theory (Taylor & Francis, London, 1985).
  5. A. Bunde and S. Havlin, Fractals and Disordered Systems, 2nd ed. (Springer-Verlag, New York, 1996).
  6. R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Breakdown of the internet under intentional attack, Phys. Rev. Lett. 86, 3682 (2001).
  7. R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Phys. Rev. Lett. 86, 3200 (2001).
  8. R. Cohen, S. Havlin, and D. ben-Avraham, Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett. 91, 247901 (2003).
  9. D. A. Kim, A. R. Hwong, D. Stafford, D. A. Hughes, A. J. O'Malley, J. H. Fowler, and N. A. Christakis, Social network targeting to maximise population behaviour change: A cluster randomised controlled trial, The Lancet 386, 145 (2015).
  10. M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, Identification of influential spreaders in complex networks, Nature Phys. 6, 888 (2010).
  11. F. Morone and H. A. Makse, Influence maximization in complex networks through optimal percolation, Nature 524, 65 (2015).
  12. F. Coghi, F. Radicchi, and G. Bianconi, Controlling the uncertain response of real multiplex networks to random damage, Phys. Rev. E 98, 062317 (2018).
  13. D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, Mastering the game of go with deep neural networks and tree search, Nature 529, 484 (2016).
  14. D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis, Mastering the game of go without human knowledge, Nature 550, 354 (2017).
  15. Z. Yang and J. Yao, Cluster dimensionality in the game of go, Physica A 176, 447 (1991).
  16. J. Yan, H. He, X. Zhong, and Y. Tang, Q-learning-based vulnerability analysis of smart grid against sequential topology attacks, IEEE Trans. Info. Forensics Sec. 12, 200 (2017).
  17. X. Li, W. Hu, P. Hou, T. Shang, X. Gao, and D. Li, Optimal attack strategy of power grid based on double Q-learning algorithm, in Proceedings of the 2021 IEEE 5th Conference on Energy Internet and Energy System Integration (EI2) (IEEE, New York, 2021), pp. 2460–2465.
  18. N. L. Dehghani, A. B. Jeddi, and A. Shafieezadeh, Intelligent hurricane resilience enhancement of power distribution systems via deep reinforcement learning, Appl. Energy 285, 116355 (2021).
  19. D. Li, B. Fu, Y. Wang, G. Lu, Y. Berezin, H. E. Stanley, and S. Havlin, Percolation transition in dynamical traffic network with evolving critical bottlenecks, Proc. Natl. Acad. Sci. 112, 669 (2015).
  20. A. Margolina, H. Herrmann, and D. Stauffer, Size of largest and second largest cluster in random percolation, Phys. Lett. A 93, 73 (1982).
  21. A. Braunstein, L. Dall'Asta, G. Semerjian, and L. Zdeborová, Network dismantling, Proc. Natl. Acad. Sci. 113, 12368 (2016).
  22. X.-L. Ren, N. Gleinig, D. Helbing, and N. Antulov-Fantulin, Generalized network dismantling, Proc. Natl. Acad. Sci. 116, 6554 (2019).
  23. C. Fan, L. Zeng, Y. Sun, and Y.-Y. Liu, Finding key players in complex networks through deep reinforcement learning, Nature Mach. Intell. 2, 317 (2020).
  24. M. Grassia, M. De Domenico, and G. Mangioni, Machine learning dismantling and early-warning signals of disintegration in complex systems, Nature Commun. 12, 5190 (2021).
  25. D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó, Positional Games (Springer, Basel, 2014).
  26. http://blue.mmdanziger.com/.
  27. See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevResearch.6.013067 for additional details on agents trained across multiple board sizes, and visualizations of example games.
  28. P. L. Leath and G. R. Reich, Scaling form for percolation cluster sizes and perimeters, J. Phys. C 11, 4017 (1978).
  29. R. F. Voss, The fractal dimension of percolation cluster hulls, J. Phys. A: Math. Gen. 17, L373 (1984).
  30. C. Vanderzande, Surface fractal dimension of two-dimensional percolation, J. Phys. A: Math. Gen. 21, 833 (1988).
  31. Y. Yang and A. E. Motter, Cascading failures as continuous phase-space transitions, Phys. Rev. Lett. 119, 248302 (2017).
  32. T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks, arXiv:1609.02907.
  33. H. Sanhedrai, J. Gao, A. Bashan, M. Schwartz, S. Havlin, and B. Barzel, Reviving a failed network through microscopic interventions, Nature Phys. 18, 338 (2022).
  34. D. P. Kingma and J. Ba, Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR), 2015.
  35. V. Hasselt, Deep reinforcement learning with double Q-learning, Assoc. Adv. Artif. Intell. 2, 5 (2016).
  36. Our source code can be found at https://github.com/spcornelius/blue_zero.

Outline

Information

Phys. Rev. Research 6, 013067– Published 17 January, 2024
  • Received 13 July 2023
  • Accepted 6 November 2023
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation