Агрегация слабосвязанных компонент и мостов влияния многослойных социальных графов

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

1. Newman M.E.J., Girvan M. Finding and evaluating community structure in networks. Physical Review. 2004;E69:026113. DOI: 10.48550/arXiv.cond-mat/0308217

2. Granovetter M.S. The Strength of Weak Ties. American Journal of Sociology. 1973;78(6):1360–1380. URL: https://www.jstor.org/stable/2776392

3. Watts D.J., Strogatz S.H. Collective Dynamics of “Small-world” Networks. Nature. 1998;393:440–442. DOI: 10.1038/30918

4. Girvan M., Newman M.E.J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the USA. 2002;99(2):7821–7826. DOI: 10.1073/pnas.122653799

5. Newman M.E.J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the USA. 2006;103(23):8577–8582. DOI: 10.1073/pnas.0601602103

6. Kivelä M., Arenas A., Barthelemy M., Gleeson J.P., Moreno Y., Porter M.A. Multilayer networks. Journal of Complex Networks. 2014;2(3):203–271. DOI: 10.48550/arXiv.1309.7233; DOI: 10.1093/comnet/cnu016

7. Boccaletti S., Bianconi G., Criado R., del Genio C.I., Gómez-Gardeñes J., Romance M., Sendiña-Nadal I., Wang Z., Zanin M. The structure and dynamics of multilayer networks. Physics Reports. 2014;544(1):1–122. DOI: 10.1016/j.physrep.2014.07.001

8. Brandes U. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology. 2001;25(2):163– 177. DOI: 10.1080/0022250X.2001.9990249

9. Spielman D.A., Teng S.-H. Spectral sparsification of graphs. SIAM Journal on Computing. 2011;40(4):981–1025. DOI: 10.1137/08074489X

10. Riondato M., Upfal E. ABRA: Approximating betweenness centrality in static and dynamic graphs with Rademacher averages. Proceedings of the 22nd ACM SIGKDD Conference. 2016;1145-1154. DOI: 10.1145/2939672.2939770

11. Jin Y., Loukas A., JáJá J. Graph coarsening with preserved spectral properties. Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. 2020;4452-4462. URL: https://proceedings.mlr.press/v108/jin20a/jin20a.pdf

12. Watts D. J., Strogatz S.H. Collective dynamics of “small world” networks. Nature. 1998;393(6684):440-442. DOI: 10.1038/3091

13. Song C., Havlin S., Makse H.A. Self similarity of complex networks. Nature. 2005;433(7024):392–395. DOI: 10.1038/nature03248

14. Yassin A., Cherifi H., Seba H., Togni O. High and low similarity backbone extraction using similarity-based link prediction. Applied Network Science. 2025;10:22. DOI: 10.1007/s41109-025-00705-y

15. Burt R.S. Structural holes: The social structure of competition. — Cambridge, MA: Harvard Univ. Press; 1992. 313 p. URL: https://archive.org/details/structuralholess0000burt/page/4/mode/2up

16. Saito K., Kimura M., Motoda H. Discovering Influential Nodes for SIS Models in Social Networks. Discovery Science, Porto; 2009. DOI: 10.1007/978-3-642-04747-3_24

17. De Domenico M., Solé Ribalta A., Omodei E., Gómez S., Arenas A. Ranking in interconnected multilayer networks reveals versatile nodes. Nature Communications. 2015;6(1):6868. DOI: 10.1038/ncomms7868

18. Lotfi N., Requejo H.S., Rodrigues F.A., Mello M.A.R. A new centrality index designed for multilayer networks. Methods in Ecology and Evolution. 2023;15(1):204-213. DOI: 10.1111/2041-210X.14257

19. Leskovec J., Kleinberg J., Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data. 2007;1(1):2. DOI: 10.1145/1217299.1217301

20. Zhao Z., Zhang Y., Feng Z. Towards scalable spectral embedding and data visualization via spectral coarsening. ACM International Conference on Web Search and Data Mining. 2021. DOI: 10.1145/3437963.3441767

21. Chen P.Y., Hero A.O. Multilayer spectral graph clustering via convex layer aggregation. IEEE Transactions on Signal Processing. 2017. URL: https://ieeexplore.ieee.org/document/7990044

22. Dong X., Frossard P., Vandergheynst P. Clustering with multi-layer graphs: A spectral perspective. IEEE Transactions on Signal Processing. 2012. URL: https://ieeexplore.ieee.org/document/6265414/

23. Solé-Ribalta A., De Domenico M., Gómez S. Centrality rankings in multiplex networks. ACM Web Science Conference. 2014. DOI: 10.1145/2615569.2615687

24. Chakraborty T., Narayanam R. Cross-layer betweenness centrality in multiplex networks with applications. IEEE 32nd International Conference on Data Engineering (ICDE). 2016. DOI: 10.1109/ICDE.2016.7498257

25. Miller B.A., Shafi Z., Ruml W., Vorobeychik Y. Attacking shortest paths by cutting edges. Proceedings of the ACM WebConference. 2023. DOI: 10.48550/arXiv.2211.11141

26. Lu G., Xiong Y., Ding C., Wang Y. An optimal schedule for urban road network repair based on the greedy algorithm. PLoS ONE. 2016;11(10). DOI: 10.1371/journal.pone.0164780

27. Glantz R., Meyerhenke H., Schulz C. Tree-based coarsening and partitioning of complex networks. ACM Journal of Experimental Algorithmics. 2016. DOI: 10.1145/2851496

28. Bellingeri M., Cassi D. Robustness of weighted networks under node and link removal. Physica A Statistical Mechanics and its Applications 489. 2017;500:11–22. DOI: 10.1016/j.physa.2017.07.020

29. Loukas A., Vandergheynst P. Spectrally approximating large graphs with smaller graphs. ICML. 2018. URL: http://proceedings.mlr.press/v80/loukas18a.html

30. Nemhauser G., Wolsey L. Maximizing submodular set functions. Mathematical Programming. 1978;14(1):265– 294. URL: https://thibaut.horel.org/submodularity/papers/nemhauser1978.pdf

31. Panayiotou G., Magnani M., Pinaud B. Current challenges in multilayer network engineering. Applied Network Science. 2024;9(1). DOI: 10.1007/s41109-024-00686-4

32. Ghoniem M., Melançon G. The State of the Art in Multilayer Network Visualization. Computer Graphics Forum. 2019;38(16). DOI: 10.1111/cgf.13610