Научный архив: статьи

В статье предложен теоретически обоснованный и вычислительно эффективный алгоритм для выявления критически значимых («мостовых») ребер в многослойных социальных графах. суть подхода заключается в последовательном применении трех процедур: 1) cпектральное укрупнение каждого слоя графа - сжатие с сохранением ключевых спектральных свойств (в частности, лапласиана) и локальной резистивной структуры; 2) приближенная оценка реберной посреднической центральности - расчет значимости ребер с учетом весов слоев и кросс-слойных взаимодействий; 3) жадное покрытие кратчайших путей - итеративный отбор ребер, максимизирующих фрагментацию графа при минимальном числе удалений. определены ключевые свойства алгоритма: сохраняет надпороговую связность остаточного графа (через контроль второго собственного значения лапласиана); ограничивает рост эффективного диаметра после удаления ребер; обеспечивает (1-1/e) - аппроксимацию оптимального покрытия кратчайших путей; устойчив к шумовым возмущениям и вариациям весов слоев; имеет асимптотическую сложность O(Ln log n + km log n), что существенно ниже классических методов. Практическая значимость - в задачах мониторинга распространения информации, оценки структурной уязвимости сетей и прогнозирования каскадных сбоев в многослойных структурах (социальные платформы, транспортные и коммуникационные сети). ограничения связаны с предположением о распространении по кратчайшим путям, априорной агрегацией слоев и отсутствием учета временной динамики.