Программная реализация алгоритма Дейкстры при графоструктурном моделировании организационных систем с использованием метаграфов

С появлением социальных сетей, различных систем сбора и хранения данных и накоплением больших объемов информации графовые структуры получили очередной стимул для развития, так как одно из их основных преимуществ заключается в возможности получить компактные и понятные модели сложных систем. Графоструктурный подход является особенно продуктивным при решении задач, связанных с анализом сетей различной природы, таких как социальные сети, веб-графы, транспортные дорожные сети и другие. Такие объекты характеризуются большим объемом и сложной структурой, поэтому вопрос использования для их описания обобщенных графовых структур весьма актуален. В качестве обоснования можно выделить ряд преимуществ: сокращение размерности исходных данных без потери информации, снижение сложности интерпретации промежуточных результатов, возможность моделирования задачи на нескольких этапах и другие. Данная статья посвящена вопросам, связанным с развитием математического аппарата для построения графоструктурных моделей сложных систем. Рассматриваются обобщения понятия графа, такие как неориентированные и ориентированные гиперграфы и метаграфы. Приводится пример программной реализации иерархической системы на основе метаграфа. Данный подход позволяет варьировать степень детализации данных без их модификации при решении различных задач управления организационными системами.

1. Биггс Н. Алгебраическая теория графов. Издательство Камбриджского университета. 1993 г.

2. Эвен Ш. Графические алгоритмы: второе издание. Издательство Камбриджского университета, 2012 г.

3. Бретто А. Теория гиперграфа: Введение. Спрингер, Гейдельберг. 2013.

4. Каталюрек Ю.В., Боман Э.Г., Дивайн К.Д., Боздаг Д. Динамическая нагрузка на основе гиперграфа. Балансировка для адаптивных научных вычислений. В: 2007 IEEE International Parallel и Симпозиум по распределенной обработке. Рим. 2007 г.

5. Кван Х., Ли К. Нечеткий гиперграф и нечеткое разбиение. Транзакции IEEE в системах, Человек и кибернетика. 1995; 25 (1): 196-201.

6. Ли Дж., Чо М., Ли К.М. Сопоставление гиперграфов с помощью случайных блужданий с повторным взвешиванием. В: CVPR 2011. Провиденс, Род-Айленд. 2011 г.

7. Хуан Ю., Лю К., Чжан С., Метаксас Д. Н. Поиск изображений с помощью вероятностного гиперграфа рейтинг. В: Конференция компьютерного общества IEEE 2010 года по компьютерному зрению и шаблонам. Признание. Сан-Франциско, Калифорния. 2010 г.

8. Басу А., Бланнинг Р. Метаграфы: инструмент для моделирования систем поддержки принятия решений. Наука управления. 1994; 40 (12): 1579-1763.

9. Фанг Й., Лин В., Чжэн В. В., Ву М. Поиск семантической близости на графах с помощью обучения на основе метаграфов. В: 32-я Международная конференция IEEE по инженерии данных (ICDE). Хельсинки. 2016 г.

10. Чжао Х., Яо К., Ли Дж., Сон Й., Ли Д. Слияние рекомендаций на основе мета-графов Гетерогенные информационные сети. В: KDD '17: Материалы 23-го ACM Международная конференция SIGKDD по открытию знаний и интеллектуальному анализу данных. Канада. 2017 г.

11. Гаур Д., Шастри А., Бисвас Р. Разработка образцов субструктуры на основе метаграфов. В: Международная конференция по передовой компьютерной теории и инженерии. Пхукет. 2008 г.

12. Мирошников А., Жбанова Н. Описание структур социально-экономических систем с помощью метаграфов. В: 1-я Международная конференция по системам управления и математическому моделированию. Автоматизация и энергоэффективность. Липецк, Россия. 2019.

13. Блюмин С.Л. Графы, гиперграфы, метаграфы, ассоциированные с 2D-системами. Материалы Междунар. науч.-практ. конф. «Cовременная математика и ее приложения». Стерлитамак. 2017.

14. Блюмин С.Л. Графоструктурное моделирование. Метаграфы и их матрицы. Вестник ЛГТУ. 2015;1(23):7-13.

15. Герасименко О.Н., Мирошников А.И. Задачи управления производственными организационными системами с учетом сезонного воздействия окружающей среды. Экология Центрально-Черноземной области Российской Федерации. 2012;2:87-88.