Модифікований алгоритм процесу обтинання для виділення k-серцевин складних мереж

Дмитро Поліщук; Олександр Поліщук

doi:10.15407/fmmit2025.40.005

Дмитро Поліщук
Олександр Поліщук

DOI: https://doi.org/10.15407/fmmit2025.40.005

Ключові слова: складна мережа, k-серцевина, процес обтинання, сусідство, уразливість, цілеспрямована атака, оцінювання наслідків.

Анотація

Проаналізовано найбільш вживаний для виділення k-серцевин складних мереж (СМ) алгоритм процесу обтинання. Визначений основний недолік цього алгоритму, який полягає у можливості виродження k-серцевини у порожню множину навіть якщо ця мережа містить достатньо велику кількість вузлів зі ступенем не меншим ніж k. Для усунення цього недоліку запропоновано модифікований алгоритм процесу обтинання та показано його дієздатність для виділення k- серцевин на прикладах низки модельних та реальних складних мереж. k-серцевини обрані у якості груп найважливіших елементів СМ, які можуть стати метою одночасної цілеспрямованої атаки на мережу та розроблено сценарій такої атаки, який враховує потенційні спроможності нападника. Запропоновано спосіб оцінювання наслідків успішної атаки на k-серцевину, який базується на поняття області її сусідства.

Посилання

Dorogovtsev S.N., Goltsev A.V., Mendes J.F.F., K-core organization of complex networks. Physical review letters, Vol. 96, No. 4, 2006, 040601. doi: 10.1103/PhysRevLett.96.040601.

Burleson-Lesser K., A Network Theoretical Approach to Real-World Problems: Application of the K-Core Algorithm to Various Systems. Dissertation of PhD Doctor of Philosophy, New York, USA: The City University of New York, 2018.

Tavares F., Illuminating the Gas Between Galaxies with Supercomputing. Available: https://www. nasa.gov/centers-and-facilities/ames/illuminating-the-gas-between-galaxies-with-supercomputing, Nov 20, 2019.

Svitlyk Y., Human Brain Project: Attempt to imitate the human brain. Available: https://root-nation.com/en/ articles-en/tech-en/en-human-brain-project , Nov 5, 2023.

Kong X. et al, k-core: Theories and applications. Physics Reports, Vol. 832, 2019, 1-32. doi: 10.1016/j.physrep.2019.10.004.

Mimar S., Learning Dynamical Processes from Structure in Complex Networks. Rochester: University of Rochester, 2022.

Hossain J., Soundarajan S., Sarıyüce A. E., Quantifying node-based core resilience. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2023, 259-276.https://doi.org/10.1007/978-3-031-43418-1_16

Li J., et al, Large-Scale Social Network Privacy Protection Method for Protecting K-Core. International Journal of Network Security, Vol. 23, 2021, 612-622. doi: 10.1109/ACCESS.2019. 2933151.

Bellingerio M., Cassi D., Vincenzi S., Efficiency of attack strategies on complex model and real-world networks. Physica A: Statistical Mechanics and its Applications, Vol. 414, 2014, 174-180. doi: 10.1016/j.physa.2014.06.079.

Batagelj V., Zaversnik M., An O (m) algorithm for cores decomposition of networks. arXiv: cs/0310049, 2003.

Boccaletti S., et al, Complex networks: Structure and dynamics. Physics reports, Vol. 424, No. 4, 2006, 175-308. doi: 10.1016/j.physrep.2005.10.009.

Wan Z., et al, A survey on centrality metrics and their network resilience analysis. IEEE Access, Vol. 9, 2021, 104773-104819. doi: 10.1109/ACCESS.2021.3094196.

Ugurlu O., Comparative analysis of centrality measures for identifying critical nodes in complex networks. Journal of Computational Science, Vol. 62, 2022, 101738. doi: 0.1016/j.jocs.2022. 101738.

Polishchuk O., Vulnerability of Complex Network Structures and Systems. Cybernetics and Systems Analysis, Vol. 56, No. 2, 2020, 312 - 321. doi: 10.1007/s10559-020-00247-4.

Polishchuk D., Polishchuk O., Yadzhak M., Complex evaluation of hierarchically-network systems Automatic Control and Information Sciences, Vol. 2, No. 2, 2014, 32-44.

Tokhirov R., Rahmonov N., Technologies of using local networks efficiently. Asian Journal Of Multidimensional Research, Vol. 10, No. 6, 2021, 250-254. doi: 10.5958/2278-4853.2021.00535.8.

Zhou B., et al, Attacking the core structure of complex network. IEEE Transactions on Computational Social Systems, Vol. 10, No. 4, 2022, 1428-1442. doi: 10.1109/TCSS.2022.3188522.

Ahuja R. K., et al, Faster algorithms for the shortest path problem. Journal of the ACM, Vol. 37, No. 2, 1990, 213-223. doi: 10.1145/77600.77615.

Nguyen Q., et al, Conditional attack strategy for real-world complex networks. Physica A: Statistical Mechanics and its Applications, Vol. 530, 2019, 12156. doi: 10.1016/j.physa.2019.121561.

Noldus R., Van Mieghem P., Assortativity in complex networks. Journal of Complex Networks, Vol. 3, No. 4, 2015, 507-542. doi: 10.1093/comnet/cnv005.