Modified pruning process algorithm for k-cores decomposition in a complex networks
DOI:
https://doi.org/10.15407/fmmit2025.40.005Keywords:
складна мережа, k-серцевина, процес обтинання, сусідство, уразливість, цілеспрямована атака, оцінювання наслідків.Abstract
The most commonly used algorithm for extracting k-cores of complex networks (CNs) is analyzed. The main drawback of this algorithm is identified, which is the possibility of degenerating the k-core into an empty set even if this network contains a sufficiently large number of nodes with a degree not less than k. To eliminate this drawback, a modified pruning process algorithm is proposed and its effectiveness for extracting k-cores is shown on the examples of a number of model and real-world complex networks. k-cores are formed as groups of the most important CN elements, which can become the target of simultaneous targeted attack on the network, and a scenario of such attack is formed, which takes into account the potential capabilities of intruder. A method for evaluation the consequences of successful attack on k-core is proposed, which is based on the concept of its neighborhood domain.
References
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.
