Устойчивая алгебраическая связность
- Авторы: Курузов И.А.1,2, Рогозин А.В.1, Чежегов С.А.1, Купавский А.Б.1
-
Учреждения:
- Московский физико-технический институт
- Институт проблем передачи информации РАН им. А.А. Харкевича
- Выпуск: № 6 (2023)
- Страницы: 49-59
- Раздел: АНАЛИЗ ДАННЫХ
- URL: https://journals.rcsi.science/0132-3474/article/view/148119
- DOI: https://doi.org/10.31857/S0132347423060067
- EDN: https://elibrary.ru/FWLNGZ
- ID: 148119
Цитировать
Аннотация
Алгебраическая связность графа определяется как второе собственное число лапласиана. Данная величина является одной из численных характеристик, показывающих насколько граф связен. Однако данная метрика не учитывает возможных изменений для графа. При этом, стоит заметить, что удаление даже одной вершины или ребра может сделать граф несвязным. Данная работа посвящена разработке метрик на основе алгебраической связности, которые принимают во внимание возможность таких модификаций и дают представление об устойчивости сети. Кроме этого, мы приводим обобщения некоторых известных методов оптимизации для наших версий робастной алгебраической связности. Также данная работа содержит некоторые численные эксперименты, демонстрирующие эффективность предложенных подходов.
Об авторах
И. А. Курузов
Московский физико-технический институт; Институт проблем передачи информации РАН им. А.А. Харкевича
Автор, ответственный за переписку.
Email: kuruzov.ia@phystech.edu
Россия, 141701, г. Долгопрудный, Институтский пер., 9; Россия, 127051, г. Москва, Большой Каретный пер., 19, стр. 1
А. В. Рогозин
Московский физико-технический институт
Автор, ответственный за переписку.
Email: aleksandr.rogozin@phystech.edu
Россия, 141701, г. Долгопрудный, Институтский пер., 9
С. А. Чежегов
Московский физико-технический институт
Автор, ответственный за переписку.
Email: chezhegov.sa@phystech.edu
Россия, 141701, г. Долгопрудный, Институтский пер., 9
А. Б. Купавский
Автор, ответственный за переписку.
Email: kypavskii@yandex.ru
Список литературы
- 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.