Динамические графы и их некоторые приложения

В статье рассматриваются современные подходы к моделированию сетевых систем и в целом сетей с динамической природой. В работе представлен современный класс динамических графов с описанием их практических применений. В качестве процедуры изменения динамического графа представлены базовые или простые операции, среди которых удаление или добавление вершин и ребер. Выделен специальный подкласс предфрактальных графов со свойствами самоподобия. Для класса динамических графов определено понятие траектории, представленное последовательностью классических графов, меняющихся от одного к другому во времени. Инструментарий динамических графов может стать основой для разработки алгоритмов командно-информационного взаимодействия подвижных абонентов в сетевых системах, в том числе сетевых системах непрерывного пространственного мониторинга. Для описания оптимизационных задач на многовзвешенных графах предложена формальная постановка многокритериальной задачи на предфрактальном графе. Описаны множества допустимых решений, парето-оптимальных и полных решений. Предложены некоторые леммы многокритериальной оптимизации для индивидуальных задач, которые обладают свойством полноты, а также ограничения линейной свертки критериев для поиска парето-оптимальных решений. Исследованы наследственные свойства, проявляющиеся в траекториях динамического графа,— а именно наследственность структурно-функциональных характеристик и, как следствие, наследственность решений при переходе от одного графа к другому в траектории динамического графа. Настоящая работа вносит свой вклад в развитие сетевой науки и теорию динамических сетей, предлагая как подходы, так и частные решения на общих и специальных классах графов.

1. Робертс Ф. С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. Пер. с англ. М.: Наука; 1986. 494 с.

2. Westaby J. D. Dynamic Network Theory: How Social Networks Influence Goal. American Psychological Association; 2011. 279 p.

3. Губанов Д.А., Новиков Д.А., Чхартишвили А. Г. Социальные сети: модели информационного влияния, управления и противоборства. М.: Физматлит; 2010. 228 с.

4. Кучерявый А. Е., Прокопьев А. В., Кучерявый Е.А. Самоорганизующиеся сети. СПб.: Любавич; 2011. 311 с.

5. Голдсмит А., Медар М., Эффрос М. Самоорганизующиеся беспроводные сети. В мире науки. 2012;(6):76–81. URL: https://www.elibrary.ru/ocsgzt

6. Визгунов А. Н., Гольденгорин Б. И., Замараев В. А. и др. Применение рыночных графов к анализу фондового рынка России. Журнал Новой экономической ассоциации. 2012;3(15):66–81. URL: https://www.elibrary.ru/pfiuxn

7. Georg C. P. The Effect of Interbank Network Structure on Contagion and Common Shocks. Journal of Banking & Finance. 2013;37(7):2216–2228. DOI: 10.1016/j.jbankfin.2013.02.032

8. Krön B. Growth of self-similar graphs. J. Graph Theory. 2004;45(3):224–239. DOI: 10.1002/jgt.10157

9. Кочкаров А. А. Структурная динамика: свойства и количественные характеристики предфрактальных графов. М.: Вега-Инфо; 2012. 120 с.

10. Кочкаров А. А., Малинецкий Г. Г., Кочкаров Р. А. Некоторые аспекты динамической теории графов. Журнал вычислительной математики и математической физики. 2015;55(9):1623–1629. DOI: 10.7868/S0044466915090094

11. Rozenfeld H. D., Gallos L.K, Song Ch., Makse H. A. Fractal and Transfractal Scale-Free Networks. Mathematics of Complexity and Dynamical Systems. Robert A. Meyers, ed. New York: Springer; 2012. 1858 p. DOI: 10.1007/978-0-387-30440-3_231

12. Кочкаров А. М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО; 1998. 170 с.

13. Казанцев А.М., Кочкаров Р.А., Тимошенко А.В., Сычугов А.А. Некоторые подходы к оценке процесса функционирования структурно-динамических систем мониторинга в условиях внешних воздействий. Моделирование, оптимизация и информационные технологии. 2021;4(35):14. DOI: 10.26102/2316018/2021.35.4.005

14. Кочкаров Р.А. Задачи многокритериальной оптимизации на многовзвешенных предфрактальных графах. М.: Академинновация; 2014. 189 с. URL: https://www.elibrary.ru/tyiygd

15. Перепелица В. А. Многокритериальные модели и методы для задач оптимизации на графах. LAP Lambert Academic Publishing; 2013. 336 с. URL: https://n.eruditor.one/file/1399011/

16. Павлов Д.А. Многокритериальная задача покрытия предфрактального графа простыми цепями. Дисс. … канд. физ.-мат. наук. Таганрог: Таганрогский государственный радиотехнический университет; 2004. 110 с. URL: https://new-disser.ru/_avtoreferats/01002738834.pdf

17. Milgram S. The small world problem. Psychology Today. 1967;(2):60–67. DOI: 10.1007/97-3-658-21742-6_94

18. Подлазов А. В., Щетинина Д. П. Модель роста социальной сети. Препринты ИПМ им. М. В. Келдыша РАН. 2013;(95):1–16. URL: https://keldysh.ru/papers/2013/prep2013_95.pdf

19. Митин Н.А., Подлазов А. В., Щетинина Д. П. Исследование сетевых свойств Живого журнала. Препринты ИПМ им. М. В. Келдыша РАН. 2012;(78):1–16. URL: https://keldysh.ru/papers/2012/prep2012_78.pdf