Мария Вячеславовна Денисова — магистрант, направление «Прикладная информатика», факультет информационных технологий и анализа больших данных, Финансовый университет при Правительстве Российской Федерации; BI-разработчик, ООО «Авито Тех»
Москва
Maria V. Denisova — Master’s student, program “Applied Informatics”, Department of Artificial Intelligence, Faculty of Information Technology and Big Data Analysis, Financial University under the Government of the Russian Federation; BI Developer, Avito Tech, LLC
Moscow
Расул Ахматович Кочкаров — кандидат экономических наук, доцент кафедры искусственного интеллекта факультета информационных технологий и анализа больших данных
Москва
Rasul A. Kochkarov — Cand. Sci (Econ.), Assoc. Prof. of the Department of Artificial Intelligence, Faculty of Information Technology and Big Data Analysis
Moscow
В статье предложен теоретически обоснованный и вычислительно эффективный алгоритм для выявления критически значимых («мостовых») ребер в многослойных социальных графах. суть подхода заключается в последовательном применении трех процедур: 1) cпектральное укрупнение каждого слоя графа — сжатие с сохранением ключевых спектральных свойств (в частности, лапласиана) и локальной резистивной структуры; 2) приближенная оценка реберной посреднической центральности — расчет значимости ребер с учетом весов слоев и кросс-слойных взаимодействий; 3) жадное покрытие кратчайших путей — итеративный отбор ребер, максимизирующих фрагментацию графа при минимальном числе удалений. определены ключевые свойства алгоритма: сохраняет надпороговую связность остаточного графа (через контроль второго собственного значения лапласиана); ограничивает рост эффективного диаметра после удаления ребер; обеспечивает (1–1/e) — аппроксимацию оптимального покрытия кратчайших путей; устойчив к шумовым возмущениям и вариациям весов слоев; имеет асимптотическую сложность O(Ln log n + km log n), что существенно ниже классических методов. Практическая значимость — в задачах мониторинга распространения информации, оценки структурной уязвимости сетей и прогнозирования каскадных сбоев в многослойных структурах (социальные платформы, транспортные и коммуникационные сети). ограничения связаны с предположением о распространении по кратчайшим путям, априорной агрегацией слоев и отсутствием учета временной динамики.
The paper proposes a theoretically grounded and computationally efficient algorithm for identifying critically important (“bridge”) edges in multilayer social graphs. The approach consists of three sequential procedures: 1) spectral coarsening of each graph layer — compression while preserving key spectral properties (in particular, the Laplacian) and the local resistive structure; 2) approximate estimation of edge betweenness centrality — computing edge importance with layer weights and cross-layer interactions taken into account; 3) greedy shortest-path coverage — iteratively selecting edges that maximize graph fragmentation while minimizing the number of removals. The key properties of the algorithm are established: it preserves above-threshold connectivity of the residual graph (via control of the second Laplacian eigenvalue); limits the growth of the effective diameter after edge removals; provides a (1–1 / е) approximation to the optimal shortest-path cover; is robust to noise perturbations and variations in layer weights; and has asymptotic complexity O(Ln log n + km log n), which is substantially lower than that of classical methods. The practical significance lies in monitoring information diffusion, assessing structural vulnerability, and predicting cascading failures in multilayer infrastructures (social platforms as well as transportation and communication networks). Limitations include the assumption of shortest-path propagation, a priori layer aggregation, and the lack of an explicit temporal dynamics model.
The authors declare that there are no conflicts of interest present.