Aggregation of Weakly Connected Components and Influence Bridges in Multilayer Social Graphs

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.

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