nach oben

Programming and Computer Software

Erschienen in:

01.12.2023

Robust Algebraic Connectivity

verfasst von: I. A. Kuruzov, A. V. Rogozin, S. A. Chezhegov, A. B. Kupavskii

Erschienen in: Programming and Computer Software | Ausgabe 6/2023

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The second smallest eigenvalue of the Laplacian is known as the algebraic connectivity of a graph. It shows degree of graph connectivity. However, this metric does not take into account possible changes in the graph. The removal of even one node or edge can make it disconnected. This work is devoted to the development of a metric that should describe robustness of a graph to such changes. All proposed metrics are based on the algebraic connectivity. In addition, we generalize some well-known optimization methods for our robust modifications of the algebraic connectivity. The paper also reports results of some numerical experiments demonstrating the efficiency of the proposed approaches.

Vorheriger Artikel On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

Nächster Artikel Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition

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

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+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 "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

Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J., 1973, vol. 23, pp. 298–305. https://doi.org/10.21136/CMJ.1973.101168MathSciNetCrossRefMATH

Fallat, Sh., Kirkland, S., and Pati, S., On graphs with algebraic connectivity equal to minimum edge density, Linear Algebra Appl., 2003, vol. 373, pp. 31–50. https://doi.org/10.1016/S0024-3795(02)00538-4MathSciNetCrossRefMATH

Ghosh, A. and Boyd, S., Growing well-connected graphs, Proc IEEE Conf. Decision and Control, 2007, pp. 6605–6611. https://doi.org/10.1109/CDC.2006.377282

Kirkland, S. and Neumann, M., On algebraic connectivity as a function of an edge weight, Linear Multilinear Algebra, 2004, vol. 52, pp. 17–33. https://doi.org/10.1080/0308108031000119663MathSciNetCrossRefMATH

Feddema, J., Byrne, R., and Abdallah, Ch., Algebraic connectivity and graph robustness, 2005. https://doi.org/10.2172/973665

Goyal, S. and Vigier, A., Robust networks, 2011.

Bala, V. and Goyal, S., A strategic analysis of network reliability, Rev. Econ. Des., 2000, vol. 5, pp. 205–228. https://doi.org/10.1007/s100580000019CrossRef

Ghayoori, A. and Leon-Garcia, A., Robust network design, Proc. IEEE Int. Conf. Communications (ICC), Budapest, 2013, pp. 2409–2414. https://doi.org/10.1109/ICC.2013.6654892

Lipovetsky, S., Matrix Analysis book review, Technometrics, 2013, vol. 55, no. 3.

10.

Spiers, G., Wei, P., and Sun, D., Algebraic connectivity optimization of large scale and directed air transportation network, IFAC Proc. Vols., 2012, vol. 45, no. 24, pp. 103–109. https://doi.org/10.3182/20120912-3-BG-2031.00019.

11.

He, Zh., Optimization of convergence rate via algebraic connectivity, 2019.

12.

Orlowski, S., Wessaly, R., Pioro, M., and Tomaszewski, A., SNDlib 1.0: Survivable network design library, Networks: Int. J., 2010, vol. 55.3, pp. 276–286.

Titel: Robust Algebraic Connectivity
verfasst von: I. A. Kuruzov
A. V. Rogozin
S. A. Chezhegov
A. B. Kupavskii
Publikationsdatum: 01.12.2023
Verlag: Pleiades Publishing
Erschienen in: Programming and Computer Software / Ausgabe 6/2023
Print ISSN: 0361-7688
Elektronische ISSN: 1608-3261
DOI: https://doi.org/10.1134/S0361768823060051

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 "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2023

Adaptive Methods for Variational Inequalities with Relatively Smooth and Reletively Strongly Monotone Operators

Decentralized Conditional Gradient Method on Time-Varying Graphs

Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition

On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

Adaptive Variant of the Frank–Wolfe Algorithm for Convex Optimization Problems

Premium Partner