2024 №1 - перейти к содержанию номера...

Постоянный адрес этой страницы - https://voenvestnik.ru/3es124.html

Полный текст статьи в формате PDF (объем файла: 931.7 Кбайт)

Ссылка для цитирования этой статьи:

Лозоватский И. М. Граничное ранжирование графов в транспортных сетях с использованием нейронной сети // Экономика и безопасность. — 2024 №1. — URL: https://voenvestnik.ru/PDF/3ES124.pdf

Граничное ранжирование графов в транспортных сетях с использованием нейронной сети

Лозоватский Илья Маркович
ассистент кафедры компьютерных технологий и
программной инженерии (Кафедра 43)
ФГАОУ ВО «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП)
г. Санкт-Петербург, Россия

Аннотация. Многие сети, такие как транспорт, электроэнергетика и водоснабжение, могут быть представлены в виде графов. Решающей задачей в представлении графов является определение важности (ранжирование) границ графа и их влияния на общую производительность с точки зрения эффективности сети и потока информации. Например, важными границами транспортной сети являются те дороги, воздействие на которые существенно изменит общую эффективность всей сети. Обычно используемый подход к поиску таких важных ребер – это «центрирование ребер между границами» (ЦРГ) – мера ранжирования границ для определения влиятельных ребер графа на основе связности и распространения информации. Вычисление ЦРГ с использованием общего алгоритма Брандеса [1] включает вычисление кратчайших путей для каждой пары узлов, что является достаточно трудоемким, дорогостоящим и ограниченным в вычислительном отношении методом, особенно для больших графов. Любые изменения параметров графа, например веса ребра или добавление и удаление узлов или ребер, требуют пересчета ЦРГ. В качестве основного нововведения в данной статье предложен приближенный метод оценки ЦРГ с использованием нейронной сети графов (НСГ), подхода, основанного на глубоком обучении. Аргументировано положение о том, что он более эффективен в вычислительном отношении по сравнению с традиционным методом, особенно для больших графов. Предлагаемый метод ранжирования ребер на основе НСГ оценивается на нескольких синтезированных графах и реальном наборе транспортных данных. Показано, что эта структура может оценить приблизительный рейтинг ребер намного быстрее по сравнению с традиционным методом, предложенным Брандесом [1]. Этот подход является индуктивным, т. е. обучение и тестирование выполняются на разных наборах графов с различным количеством узлов и ребер. Предлагаемый метод особенно подходит для приложений в крупномасштабных сетях, где требуется периферийная информация, например, в проектах улучшения городской инфраструктуры, анализе устойчивости сетей электро- и водоснабжения, а также оптимизации распределения ресурсов в инженерных сетях.
Ключевые слова: транспортная сеть, распределение ресурсов, ранжирование ребер графа, нейронная сеть, глубокое обучение

Скачать