Email this article 
ROBUST ALGEBRAIC CONNECTIVITY
- Authors: Kuruzov I.A.1,2, Rogozin A.V.1, Chezhegov S.A.1, Kupavskii A.B.1
-
Affiliations:
- Moscow Institute of Physics and Technology
- Institute for Information Transmission Problems of the RAS (Kharkevich Institute)
- Issue: No 6 (2023)
- Pages: 49-59
- Section: DATA ANALYSIS
- URL: https://rjmseer.com/0132-3474/article/view/675729
- DOI: https://doi.org/10.31857/S0132347423060067
- EDN: https://elibrary.ru/FWLNGZ
- ID: 675729
Cite item
Open Access
Access granted
Subscription Access
Abstract
The second smallest eigenvalue of a graph Laplacian is known as algebraic connectivity of the graph. This value shows how much this graph is connected. But this metric does not take into attention possible changes in graph. Note, that deletion of even one node or edge can lead the graph to be disconnected. This work is devoted to development of a metric that should describe robustness of the graph to such changes. All proposed metrics are based on algebraic connectivity. Besides, we provide generalization of some famous optimization methods for our robust modifications of algebraic connectivity. Moreover, this work contains some numerical experiments demonstrated efficiency of proposed approaches.
About the authors
I. A. Kuruzov
Moscow Institute of Physics and Technology; Institute for Information Transmission Problems of the RAS (Kharkevich Institute)
Author for correspondence.
Email: kuruzov.ia@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9; Russia, 127051, Moscow, Bolshoi Karetny lane, 19, build. 1
A. V. Rogozin
Moscow Institute of Physics and Technology
Author for correspondence.
Email: aleksandr.rogozin@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9
S. A. Chezhegov
Moscow Institute of Physics and Technology
Author for correspondence.
Email: chezhegov.sa@phystech.edu
Russia, 141701, Moscow region, Dolgoprudny, Institutskiy per., 9
A. B. Kupavskii
Author for correspondence.
Email: kypavskii@yandex.ru
References
- Fiedler Miroslav. Algebraic Connectivity of Graphs. Czechoslovak Mathematical Journal. 1973. V. 23. P. 298–305. .https://doi.org/10.21136/CMJ.1973.101168
- Fallat Shaun, Kirkland Steve, Pati Sukanta. On graphs with algebraic connectivity equal to minimum edge density. Linear Algebra and its Applications. 2003. V. 373. P. 31–50. https://doi.org/10.1016/S0024-3795(02)00538-4
- Ghosh Arpita, Boyd Stephen. Growing Well-connected Graphs. Proceedings of the IEEE Conference on Decision and Control. 2007. P. 6605–6611. https://doi.org/10.1109/CDC.2006.377282.
- Kirkland Steve, Neumann M. On Algebraic Connectivity as a Function of an Edge Weight. Linear and Multilinear Algebra. 2004. V. 052. P. 17–33. https://doi.org/10.1080/0308108031000119663
- Feddema John, Byrne Raymond, Abdallah Chaouki. Algebraic connectivity and graph robustness. 2005.https://doi.org/10.2172/973665
- Goyal Sanjeev, Vigier Adrien. Robust Networks. 2011.
- Bala Venkatesh, Goyal, Sanjeev. A Strategic Analysis of Network Reliability. Review of Economic Design. 2000. V. 5. P. 205–228. https://doi.org/10.1007/s100580000019
- Ghayoori A., Leon-Garcia A., “Robust network design,” 2013 IEEE International Conference on Communications (ICC), Budapest, Hungary, 2013. P. 2409–2414. https://doi.org/10.1109/ICC.2013.6654892.
- Lipovetsky Stan. Matrix Analysis, 2nd edition, Roger A. Horn and Charles R. Johnson, book review, Technometrics. 2013. V. 55. № 3. 2013, 376. Technometrics. V. 55. P. 376. book review
- Gregoire Spiers, Peng Wei, Dengfeng Sun, Algebraic Connectivity Optimization of Large Scale and Directed Air Transportation Network, IFAC Proceedings Volumes, Volume 45, Issue 24, 2012, Pages 103-109, ISSN 1474-6670, ISBN 9783902823137, https://doi.org/10.3182/20120912-3-BG-2031.00019
- Zhidong He. Optimization of convergence rate via algebraic connectivity. 2019.
- Orlowski S., Wessaly R., Pioro M., Tomaszewski A. SNDlib 1.0–Survivable network design library. Networks: An International Journal 55.3. 2010. P. 276–286.
Supplementary files
