Статья: АГРЕГАЦИЯ СЛАБОСВЯЗАННЫХ КОМПОНЕНТ И МОСТОВ ВЛИЯНИЯ МНОГОСЛОЙНЫХ СОЦИАЛЬНЫХ ГРАФОВ (2026)

Читать онлайн

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

Ключевые фразы: многослойный (мультиплексный) социальный граф, посредническая центральность ребра, спектральное укрупнение (coarsening), критические мостовые ребра ("мосты влияния"), сублинейная сложность вычислений, межкластерные ребра, жадное покрытие путей, лапласиан графа
Автор (ы): Кочкаров Расул Ахматович (Kochkarov R. A.), Денисова Мария Вячеславовна (Denisova M. V.)
Журнал: ЦИФРОВЫЕ РЕШЕНИЯ И ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Предпросмотр статьи

Идентификаторы и классификаторы

SCI
Информатика
УДК
001.6. Научные знания
Для цитирования:
КОЧКАРОВ Р. А., ДЕНИСОВА М. В. АГРЕГАЦИЯ СЛАБОСВЯЗАННЫХ КОМПОНЕНТ И МОСТОВ ВЛИЯНИЯ МНОГОСЛОЙНЫХ СОЦИАЛЬНЫХ ГРАФОВ // ЦИФРОВЫЕ РЕШЕНИЯ И ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА. 2026. Т. 2 № 1
Текстовый фрагмент статьи
Будьте первым, кто начнет обсуждение

Если у вас возникли вопросы или появились предложения по содержанию статьи, пожалуйста, направляйте их в рамках данной темы.