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:
Using Localized Attacks with Probabilistic Failures to Model Seismic Events over Physical-Logical Interdependent Networks Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

Constructing Provably Robust Scale-Free Networks

verfasst von : Rouzbeh Hasheminezhad, Ulrik Brandes

Erschienen in: Network Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Scale-free networks have been described as robust to random failures but vulnerable to targeted attacks. We show that their degree sequences admit realizations that are, in fact, provably robust against any vertex removal strategy. We propose an algorithm that constructs such realizations almost surely, requiring only linear time and space. Our experiments confirm the robustness of the networks generated by this algorithm against adaptive and non-adaptive vertex removal strategies.

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 Generalized Linear Models Network Autoregression
Nächstes Kapitel Functional Characterization of Transcriptional Regulatory Networks of Yeast Species
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
For an example of such an implementation, see Algorithm 1.2.1 in [22].
 
2
This notion of scaling integer sequences refers to ranks rather than frequencies. Therefore, the scaling factor is one less than the exponent in the corresponding power-law distribution [24].
 
3
Suppose that a BFS of depth two starts from the vertex \(v_1\), where the neighbors of \(v_1\) are \(v_2, v_3, \dots , v_{d_1-2}\), respectively with degrees \(d_2-3, d_3-3, \dots , d_{d_1-2}-3\). This hypothetical scenario provides an upper bound of \(\sum _{i=2}^{d_1-2}(d_i-3)\le \sum _{i=1}^{d_1} d_i\) for the number of visited edges in any BFS of depth two, starting from any vertex in \(G_{\textsf {res}}\). Therefore, \(|F_e(G_{\textsf {res}})|\le 2 \sum _{i=1}^{d_1} d_i\) follows by an application of the union bound.
 
4
In \(G_{\textsf {res}}\) we fix a vertex order \(v_1, v_2, \dots , v_n\) and assume for any edges \(e,e'\) that \(e\le e'\) holds if and only if \(f(e)\le f(e')\), where \(f(\{v_i, v_j\}):=(n-1)\max \{i,j\}+\min \{i,j\}\).
 
5
We consider the variant of GND where removing each vertex has a unit cost, and the goal is to dismantle the network at the lowest possible cost. The implementation we use for this variant of GND was written by Petter Holme in the Python programming language and is publicly available from https://​github.​com/​pholme/​gnd.
 
Literatur
1.
Albert, R., Jeong, H., Barabási, A.L.: Error and attack tolerance of complex networks. Nature 406(6794), 378–382 (2000)CrossRef
2.
3.
Apostol, T.M.: Introduction to analytic number theory. In: Undergraduate Texts in Mathematics, p. 55. Springer, New York (1976)
4.
Asano, T.: An \(\cal{O} (n \log \log n)\) time algorithm for constructing a graph of maximum connectivity with prescribed degrees. J. Comput. Syst. Sci. 51(3), 503–510 (1995)CrossRef
5.
6.
7.
Bollobás, B.: Extremal Graph Theory, dover edition edn., p. 100. Dover Publications, Mineola (2004)
8.
Chungphaisan, V.: Construction of Hamiltonian graphs and bigraphs with prescribed degrees. J. Comb. Theory B 24(2), 154–163 (1978)MathSciNetCrossRefMATH
9.
Doyle, J.C., et al.: The ‘robust yet fragile’ nature of the internet. Proc. Natl. Acad. Sci. (PNAS) 102(41), 14497–14502 (2005)CrossRef
10.
Erdős, P.L., Hartke, S.G., Van Iersel, L., Miklós, I.: Graph realizations constrained by skeleton graphs. Electron. J. Comb. 24(2), P2.47 (2017)
11.
Friedman, J.: A proof of alon’s second eigenvalue conjecture. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 720–724. Association for Computing Machinery, New York (2003)
12.
Frieze, A., Karoński, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2016)CrossRefMATH
13.
Gao, P., Greenhill, C.: Uniform generation of spanning regular subgraphs of a dense graph. Electron. J. Comb. 26(4), P4.28 (2019)
14.
15.
Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10(3), 496–506 (1962)
16.
Hasheminezhad, R., Boudourides, M., Brandes, U.: Scale-free networks need not be fragile. In: Proceedings of the 2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 332–339. IEEE (2020)
17.
Havel, V.: Poznámka o existenci konečnỳch grafŭ (Czech) [A remark on the existence of finite graphs]. Časopis pro pěstování matematiky 080(4), 477–480 (1955)CrossRef
18.
Havil, J.: Gamma: Exploring Euler’s Constant, pp. 117–118. Princeton University Press, Princeton (2003)
19.
Horvát, S., Modes, C.D.: Connectedness matters: construction and exact random sampling of connected networks. J. Phys. Complexity 2(1), 015008 (2021)
20.
21.
Kleitman, D., Wang, D.: Algorithms for constructing graphs and digraphs with given valences and factors. Discret. Math. 6(1), 79–88 (1973)MathSciNetCrossRefMATH
22.
Kocay, W.L., Kreher, D.L.: Graphs, algorithms, and optimization. In: Discrete Mathematics and its Applications, 2nd edn. CRC Press, Boca Raton (2017)
23.
24.
Li, L., Alderson, D., Doyle, J.C., Willinger, W.: Towards a theory of scale-free graphs: definition, properties, and implications. Internet Math. 2(4), 431–523 (2005)MathSciNetCrossRefMATH
25.
Lountzi, A.: Expander Graphs and Explicit Constructions. Master’s thesis, Uppsala University, Algebra and Geometry (2015)
26.
27.
Ren, X.L., Gleinig, N., Helbing, D., Antulov-Fantulin, N.: Generalized network dismantling. Proc. Natl. Acad. Sci. 116(14), 6554–6559 (2019)
28.
Schneider, C.M., Moreira, A.A., Andrade, J.S., Jr., Havlin, S., Herrmann, H.J.: Mitigation of malicious attacks on networks. Proc. Natl. Acad. Sci. (PNAS) 108(10), 3838–3841 (2011)CrossRef
29.
30.
Metadaten
Titel
Constructing Provably Robust Scale-Free Networks
verfasst von
Rouzbeh Hasheminezhad
Ulrik Brandes
Copyright-Jahr
2022
Buch
Network Science

Print ISBN: 978-3-030-97239-4

Electronic ISBN: 978-3-030-97240-0

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-97240-0_10

Premium Partner

    Bildnachweise