Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Modularity of the ABCD Random Graph Model with Community Structure Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

The Vertex-Edge Separator Transformation Problem in Network-Dismantling

verfasst von : Xiao-Long Ren

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In complex networks, network-dismantling aims at finding an optimal set of nodes (or edges) such that the removal of the set from the network will lead to the disintegration of the network, that is, the size of the giant/largest connected component is not bigger than a specific threshold (for instance, \(1\%\) of the original network size). Existing algorithms addressing this topic can be divided into two closely related but different categories: vertex separator-oriented algorithms and edge separator-oriented algorithms. There has been a lot of research on these two categories, respectively. However, to the best of our knowledge, less attention has been paid to the relation between the vertex separator and edge separator. In this paper, we studied the separator transformation (ST) problem between the separator of the vertexes and edges. We approximated the transformation from edge separator to vertex separator using Vertex Cover algorithm, while approximated the transformation from vertex separator to edge separator using an Explosive Percolation (EP) approach. Moreover, we further analyzed the results of the vertex-edge separator transformation through the explosive percolation method in detail. The transformation problem in network-dismantling opens up a new direction for understanding the role of the vital nodes set and edges set as well as the vulnerability of complex systems.

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 Robustness of Preferential-Attachment Graphs: Shifting the Baseline
Nächstes Kapitel Gig Economy and Social Network Analysis: Topology of Inferred Network
Literatur
1.
Barabási, A.-L.: Network Science. Cambridge University Press (2016)
2.
Newman, M.E.J.: Networks. Oxford University Press (2018)
3.
Moreno, Y., Pastor-Satorras, R., Vespignani, A.: Epidemic outbreaks in complex heterogeneous networks. Eur. Phys. J. B-Condens. Matter Complex Syst. 26(4), 521–529 (2002)CrossRef
4.
Gladwell, M.: The Tipping Point: How Little Things can Make a Big Difference. Little, Brown (2006)
5.
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., Zhou, T.: Vital nodes identification in complex networks. Phys. Rep. 650, 1–63 (2016)CrossRef
6.
Jiang, J., Huang, Z.-G., Seager, T.P., Lin, W., Grebogi, C., Hastings, A., Lai, Y.-C.: Predicting tipping points in mutualistic networks through dimension reduction. Proc. Nat. Acad. Sci. U.S.A. 115(4), E639–E647 (2018)CrossRefMATH
7.
Liu, X., Li, D., Ma, M., Szymanski, B.K., Stanley, H.E., Gao, J.: Network resilience. Phys. Rep. 971, 1–108 (2022)CrossRefMATH
8.
Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., Makse, H.A.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888–893 (2010)CrossRef
9.
Morone, F., Makse, H.A.: Influence maximization in complex networks through optimal percolation. Nature 524(7563), 65–68 (2015)CrossRef
10.
Liu, Y.-Y., Barabási, A.-L.: Control principles of complex systems. Rev. Mod. Phys. 88(3), 035006 (2016)CrossRef
11.
Amani, A.M., Jalili, M., Yu, X., Stone, L.: Controllability of complex networks: choosing the best driver set. Phys. Rev. E 98(3), 030302 (2018)CrossRef
12.
Zhang, Y., Garas, A., Schweitzer, F.: Control contribution identifies top driver nodes in complex networks. Advan. Complex Syst. 22(07n08), 1950014 (2019)
13.
Del Ferraro, G., Moreno, A., Min, B., Morone, F., Pérez-Ramírez, Ú., Pérez-Cervera, L., Parra, L.C., Holodny, A., Canals, S., Makse, H.A.: Finding influential nodes for integration in brain networks using optimal percolation theory. Nat. Commun. 9(1), 2274 (2018)CrossRef
14.
Tahmassebi, A., Amani, A.M., Pinker-Domenig, K., Meyer-Baese, A.: Determining disease evolution driver nodes in dementia networks. In: Medical Imaging 2018: Biomedical Applications in Molecular, Structural, and Functional Imaging, vol. 10578, p. 1057829. International Society for Optics and Photonics (2018)
15.
Janson, S., Thomson, A.: Dismantling sparse random graphs. Comb. Probab. Comput. 17(2), 259–264 (2008)CrossRefMATH
16.
Braunstein, A., Dall’Asta, L., Semerjian, G., Zdeborová, L.: Network dismantling. Proc. Nat. Acad. Sci. U.S.A. 113(44), 12368–12373 (2016)CrossRef
17.
Ren, X.-L., Gleinig, N., Helbing, D., Antulov-Fantulin, N.: Generalized network dismantling. Proc. Nat. Acad. Sci. U.S.A. 116(14), 6554–6559 (2019)CrossRefMATH
18.
Fan, C., Zeng, L., Sun, Y., Liu, Y.-Y.: Finding key players in complex networks through deep reinforcement learning. In: Nature Machine Intelligence, pp. 1–8 (2020)
19.
Albert, R., Jeong, H., Barabási, A.-L.: Error and attack tolerance of complex networks. Nature 406(6794), 378–382 (2000)CrossRef
20.
Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136–145 (2008)CrossRef
21.
Zdeborová, L., Zhang, P., Zhou, H.-J.: Fast and simple decycling and dismantling of networks. Sci. Rep. 6, 37954 (2016)CrossRef
22.
Motter, A.E., Lai, Y.-C.: Cascade-based attacks on complex networks. Phys. Rev. E 66(6), 065102 (2002)CrossRef
23.
Altarelli, F., Braunstein, A., Dall’Asta, L., Wakeling, J.R., Zecchina, R.: Containing epidemic outbreaks by message-passing techniques. Phys. Rev. X 4(2), 21024 (2014)
24.
Mugisha, S., Zhou, H.-J.: Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94, 012305 (2016)CrossRef
25.
Qin, S.-M., Ren, X.-L., Lü, L.: Efficient network dismantling via node explosive percolation. Commun. Theor. Phys. 71(6), 764 (2019)CrossRefMATH
26.
Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)CrossRefMATH
27.
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM (JACM) 56(2), 1–37 (2009)CrossRefMATH
28.
Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23(2), 298–305 (1973)CrossRefMATH
29.
Guattery, S., Miller, G.L.: On the quality of spectral separators. SIAM J. Matrix Anal. Appl. 19(3), 701–719 (1998)CrossRefMATH
30.
Grassia, M., De Domenico, M., Mangioni, G.: Machine learning dismantling and early-warning signals of disintegration in complex systems. Nat. Commun. 12(1), 1–10 (2021)CrossRef
31.
Bichot, C.-E., Siarry, P.: Graph Partitioning. Wiley (2013)
32.
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Algorithm Engineering, pp. 117–158 (2016)
33.
Wandelt, S., Sun, X., Feng, D., Zanin, M., Havlin, S.: A comparative analysis of approaches to network-dismantling. Sci. Rep. 8(1), 1–15 (2018)CrossRef
34.
Pei, S., Wang, J., Morone, F., Makse, H.A.: Influencer identification in dynamical complex systems. J. Complex Netw. 8(2) (2019)
35.
Bellingeri, M., Bevacqua, D., Scotognella, F., Alfieri, R., Nguyen, Q., Montepietra, D., Cassi, D.: Link and node removal in real social networks: a review. Front. Phys. 8, 228 (2020)CrossRef
36.
Ren, X.-L., Antulov-Fantulin, N.: Ensemble approach for generalized network dismantling. In: International Conference on Complex Networks and Their Applications, pp. 783–793. Springer (2019)
37.
Fan, C., Zeng, L., Feng, Y., Xiu, B., Huang, J., Liu, Z.: Revisiting the power of reinsertion for optimal targets of network attack. J. Cloud Comput. 9(24), 1–13 (2020)
38.
Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981)CrossRefMATH
39.
König, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok 38(1031), 116–119 (1931)
40.
Pothen, A., Simon, H.D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430–452 (1990)CrossRefMATH
41.
Achlioptas, D., D’Souza, R.M., Spencer, J.: Explosive percolation in random networks. Science 323(5920), 1453–1455 (2009)CrossRefMATH
42.
Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001)CrossRefMATH
43.
Altarelli, F., Braunstein, A., Dall’Asta, L., Zecchina, R.: Optimizing spread dynamics on graphs by message passing. J. Stat. Mech.: Theory Exp. 2013(09), P09011 (2013)CrossRefMATH
44.
Ren, X.-L.: The dismantling problem in complex networks and its applications. Ph.D. thesis. ETH Zurich (2021)
45.
Holme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65, 056109 (2002)CrossRef
46.
Trajanovski, S., Scellato, S., Leontiadis, I.: Error and attack vulnerability of temporal networks. Phys. Rev. E 85, 066105 (2012)CrossRef
Metadaten
Titel
The Vertex-Edge Separator Transformation Problem in Network-Dismantling
verfasst von
Xiao-Long Ren
Copyright-Jahr
2023
Buch
Complex Networks and Their Applications XI

Print ISBN: 978-3-031-21130-0

Electronic ISBN: 978-3-031-21131-7

Copyright-Jahr: 2023

DOI
https://doi.org/10.1007/978-3-031-21131-7_36

Premium Partner

    Bildnachweise