Top

Published in:

2024 | OriginalPaper | Chapter

Edge Dismantling with Geometric Reinforcement Learning

Authors : Marco Grassia, Giuseppe Mangioni

Published in: Complex Networks XV

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The robustness of networks plays a crucial role in various applications. Network dismantling, the process of strategically removing nodes or edges to maximize damage, is a known NP-hard problem. While heuristics for node removal exist, edge network dismantling, especially in real-world scenarios like power grids or transportation networks, remains underexplored. This paper introduces eGDM-RL, a novel framework for edge dismantling based on Geometric Deep Learning and Reinforcement Learning. Unlike previous approaches, this method demonstrates superior performance in terms of the Area Under the dismantling Curve (AUC) with low computational complexity. The proposed model, utilizing a Graph Attention Network (GAT) and a Deep Q-value Network (DQN), outperforms traditional methods such as those based on edge betweenness. Experimental results on real-world networks validate the effectiveness of the proposed eGDM-RL framework, offering insights into critical edge removal for practical applications.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Interpreting Node Embedding Distances Through n-Order Proximity Neighbourhoods

next chapter Public Transit Inequality in the Context of the Built Environment

At the time we are writing this paper the code that implements the method described in [23] is not available, so it is impossible to compare it with our method.

Crime network dataset – KONECT (2017). http://konect.cc/networks/moreno_crime

Albert, R., Jeong, H., Barabási, A.L.: Error and attack tolerance of complex networks. Nature 406(6794), 378–382 (2000)

Artime, O., Grassia, M., De Domenico, M., Gleeson, J.P., Makse, H.A., Mangioni, G., Perc, M., Radicchi, F.: Robustness and resilience of complex networks. Nat. Rev. Phys. 1–18 (2024)

Braunstein, A., Dall’Asta, L., Semerjian, G., Zdeborová, L.: Network dismantling. Proc. Natl. Acad. Sci. 113(44), 12368–12373 (2016)

Bronstein, M.M., Bruna, J., LeCun, Y., Szlam, A., Vandergheynst, P.: Geometric deep learning: going beyond euclidean data. IEEE Signal Process. Mag. 34(4), 18–42 (2017). https://doi.org/10.1109/MSP.2017.2693418CrossRef

Carchiolo, V., Grassia, M., Longheu, A., Malgeri, M., Mangioni, G.: Efficient node pagerank improvement via link-building using geometric deep learning. ACM Trans. Knowl. Discov. Data 17(3), 1–22 (2023)CrossRef

Fan, C., Zeng, L., Sun, Y., Liu, Y.Y.: Finding key players in complex networks through deep reinforcement learning. Nat. Mach. Intell. 2(6), 317–324 (2020). https://doi.org/10.1038/s42256-020-0177-2CrossRef

Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch Geometric. In: ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)

Fujita, Y., Nagarajan, P., Kataoka, T., Ishikawa, T.: Chainerrl: A deep reinforcement learning library. J. Mach. Learn. Res. 22(77), 1–14 (2021). http://jmlr.org/papers/v22/20-376.html

10.

Grassia, M., De Domenico, M., Mangioni, G.: Machine learning dismantling and early-warning signals of disintegration in complex systems. Nat. Commun. 12(1), 5190 (2021)

11.

Grassia, M., Mangioni, G.: wsGAT: weighted and signed graph attention networks for link prediction. In: Complex Networks & Their Applications X: Volume 1, Proceedings of the Tenth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021 10, pp. 369–375. Springer (2022)

12.

Grassia, M., Mangioni, G.: CoreGDM: geometric deep learning network decycling and dismantling. In: Teixeira, A.S., Botta, F., Mendes, J.F., Menezes, R., Mangioni, G. (eds.) Complex Networks XIV, pp. 86–94. Springer Nature Switzerland, Cham (2023)CrossRef

13.

Hayes, B.: Connecting the dots. can the tools of graph theory and social-network studies unravel the next big plot? Am. Sci. 94(5), 400–404 (2006)

14.

Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M.: Playing atari with deep reinforcement learning (2013). https://doi.org/10.48550/ARXIV.1312.5602

15.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)

16.

Morone, F., Makse, H.A.: Influence maximization in complex networks through optimal percolation. Nature 524(7563), 65 (2015)CrossRef

17.

Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford, New York (2010). http://www.amazon.com/Networks-An-Introduction-Mark-Newman/dp/0199206651/ref=sr_1_5?ie=UTF8&qid=1352896678&sr=8-5&keywords=complex+networks

18.

Peixoto, T.P.: The graph-tool python library. figshare (2014)

19.

Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http://networkrepository.com

20.

Ulanowicz, R.E., Heymans, J.J., Egnotovich, M.S.: Network analysis of trophic dynamics in South Florida ecosystems, FY 99: The graminoid ecosystem. Annual Report to the United States Geological Service Biological Resources Division Ref. No.[UMCES] CBL 00-0176, Chesapeake Biological Laboratory, University of Maryland (2000)

21.

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks. In: International Conference on Learning Representations (2018). https://openreview.net/forum?id=rJXMpikCZ

22.

Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(1), 440–442 (1998)CrossRef

23.

Wu, L., Ren, X.L.: Optimal bond percolation in networks by a fast-decycling framework. In: Cherifi, H., Mantegna, R.N., Rocha, L.M., Cherifi, C., Micciche, S. (eds.) Complex Networks and Their Applications XI, pp. 509–519. Springer International Publishing, Cham (2023)CrossRef

24.

Zdeborová, L., Zhang, P., Zhou, H.J.: Fast and simple decycling and dismantling of networks. Sci. Rep. 6(1) (2016). https://doi.org/10.1038/srep37954

Title: Edge Dismantling with Geometric Reinforcement Learning
Authors: Marco Grassia
Giuseppe Mangioni
Publisher: Springer Nature Switzerland
Book: Complex Networks XV
Print ISBN: 978-3-031-57514-3

Electronic ISBN: 978-3-031-57515-0

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-57515-0_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner