nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Edge Dismantling with Geometric Reinforcement Learning

verfasst von : Marco Grassia, Giuseppe Mangioni

Erschienen in: Complex Networks XV

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Interpreting Node Embedding Distances Through n-Order Proximity Neighbourhoods

Nächstes Kapitel 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

Titel: Edge Dismantling with Geometric Reinforcement Learning
verfasst von: Marco Grassia
Giuseppe Mangioni
Verlag: Springer Nature Switzerland
Buch: Complex Networks XV
Print ISBN: 978-3-031-57514-3

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner