Приложение задачи поиска минимального покрытия в графе для повышения надежности системы цифровой личности

В работе рассматриваются особенности построения систем цифровой личности для управления информационно-технологическими процессами предприятия, архитектура которых зависит от децентрализованных реестров данных – блокчейнов. В работе рассмотрены блокчейны как взвешенные графы и сформулирован ряд тезисов, говорящих об особенности функционирования таких распределенных сетей на реальных информационно-технологических предприятиях. Рассмотрены особенности различных топологий сетей и возможных архитектурных уязвимостей и недочетов, которые могут повлиять на работу всей сети – централизация майнинга, централизация стейкинга, различные атаки на функционирующую сеть (топологическая и атака 51 % процента). Рассмотрены блокчейны, использующие различные алгоритмы достижения консенсуса с учетом их особенностей. В работе рассматривается задача поиска минимального покрытия в графе и подчеркивается важность приложения этой задачи к описываемой системе цифровой личности для увеличения надежности компьютерной сети блокчейна за счет анализа ее топологии. Рассмотрены различные методы нахождения минимального покрытия в графе – точные и эвристические алгоритмы. В работе проанализировано приложение, реализующее алгоритм муравьиной колонии для решения поставленной задачи, приводятся численные характеристики работы алгоритма и его формальное описание.

1. Акутин А.С. Технология суверенной личности как новый подход в обработке персональных данных. В сборнике: Проблемы управления в социально-экономических и технических системах: материалы XIX Международной научно-практической конференции, 13–14 апреля 2023 года, Саратов, Россия. Саратов: ИЦ «Наука»; 2023. С. 128–134.

2. Акутин А.С., Денисова З.П. Технология цифровой личности в управлении технологическим предприятием. В сборнике: Проблемы управления в социально-экономических и технических системах: материалы XX Международной научно-практической конференции: сборник научных статей, 17–18 апреля 2024 года, Саратов, Россия. Саратов: ИЦ «Наука»; 2024. С. 154–156.

3. Vayadande K., Baviskar A., Avhad J., Bahadkar S., Bhalerao P., Chimkar A. A Comprehensive Review on Navigating the Web 3.0 Landscape. In: 2024 Second International Conference on Inventive Computing and Informatics (ICICI), 11–12 June 2024, Bangalore, India. IEEE; 2024. P. 456–463. https://doi.org/10.1109/ICICI62254.2024.00080

4. Nakamoto S. Bitcoin: A Peer-to-Peer Electronic Cash System. SSRN. URL: https://doi.org/10.2139/ssrn.3440802 [Accessed 4th February 2025].

5. Van Ditmarsch H., Gattinger M., Ramezanian R. Everyone Knows That Everyone Knows: Gossip Protocols for Super Experts. Studia Logica. 2023;111(3):453–499. https://doi.org/10.1007/s11225-022-10032-3

6. Song W., Zhang W., Wang J., Zhai L., Jiang P., Huang Sh. Blockchain Data Analysis from the Perspective of Complex Networks: Overview. Tsinghua Science and Technology. 2023;28(1):176–206. https://doi.org/10.26599/TST.2021.9010080

7. Gochhayat S.P., Shetty S., Mukkamala R., Foytik P., Kamhoua G.A., Njilla L. Measuring Decentrality in Blockchain Based Systems. IEEE Access. 2020;8:178372–178390. https://doi.org/10.1109/ACCESS.2020.3026577

8. Madine M., Salah Kh., Jayaraman R., Al-Hammadi Yo., Arshad J., Yaqoob I. appXchain: Application-Level Interoperability for Blockchain Networks. IEEE Access. 2021;9:87777–87791. https://doi.org/10.1109/ACCESS.2021.3089603

9. Акутин А.С., Бровко А.В. Децентрализованный реестр данных в технологии суверенной личности. Инженерный вестник Дона. 2023;(6):232–246.

10. Vega F. The Minimum Vertex Cover Problem. [Preprint]. ResearchGate. URL: https://www.researchgate.net/publication/388526292_The_Minimum_Vertex_Cover_Problem [Accessed 13th February 2025].

11. Jayabalasamy G., Pujol C., Latha Bhaskaran K. Application of Graph Theory for Blockchain Technologies. Mathematics. 2024;12(8). https://doi.org/10.3390/math12081133

12. Barabási A.-L., Albert R. Emergence of Scaling in Random Networks. Science. 1999;286(5439):509–512.

13. Xiao M., Nagamochi H. Exact Algorithms for Maximum Independent Set. Information and Computation. 2017;255:126–146. https://doi.org/10.1016/j.ic.2017.06.001

14. Åstrand M., Floréen P., Polishchuk V., Rybicki J., Suomela J., Uitto J. A Local 2-Approximation Algorithm for the Vertex Cover Problem. In: Distributed Computing: 23rd International Symposium, DISC 2009: Proceedings, 23–25 September 2009, Elche, Spain. Berlin, Heidelberg: Springer; 2009. P. 191–205. https://doi.org/10.1007/978-3-642-04355-0_21

15. Shyu Sh.J., Yin P.-Ye., Lin B.M.T. An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem. Annals of Operations Research. 2004;131:283–304. https://doi.org/10.1023/B:ANOR.0000039523.95673.33