АНАЛІЗ ТА ЕКСПЕРИМЕНТАЛЬНІ ДОСЛІДЖЕННЯ МЕТОДІВ І ЗАСОБІВ ДЛЯ ВІЗУАЛІЗАЦІЇ ГРАФІВ У ДИНАМІЧНИХ СИСТЕМАХ

https://doi.org/10.23939/ujit2025.01.131
Надіслано: Березень 31, 2025
Переглянуто: Квітень 14, 2025
Прийнято: Травень 01, 2025
1
Національний університет "Львівська політехніка", м. Львів, Україна
2
Національний університет "Львівська політехніка", м. Львів, Україна

Візуалізація графів є важливим інструментом для інтерпретації складних даних у системах із динамічними зв’язками, таких як транспортні, комп’ютерні чи соціальні мережі, де структура даних постійно змінюється. У таких умовах особливо актуальне завдання створення адаптивних методів, здатних забезпечити чітке, зрозуміле й своєчасне відображення змін у структурі графа. У роботі проаналізовано силові методи візуалізації графів, які моделюють сили притягування та відштовхування для пошуку позицій вершин графа у двовимірному просторі, що мінімізує сумарну енергетичну функцію системи. Розроблено програмний застосунок із використанням мови програмування Java, фреймворку Spring, бібліотеки GraphStream та засобів JavaFX для інтеграції, реалізації, налаштування та порівняння алгоритмів Ідса, Фрюхтермана – Рейнгольда та Камада – Каваї. Виконано експериментальне дослідження, у межах якого протестовано поведінку кожного алгоритму на різних типах графів із відкритих наборів даних, зокрема Rome-Lib і Scotch Graph Collection. Виявлено, що алгоритм Фрюхтермана – Рейнгольда забезпечує плавні й поступові зміни макета, високу адаптивність до змін і належну масштабованість, тому він ефективний для динамічної візуалізації, зокрема у системах моніторингу транспорту. Алгоритм Камада – Каваї забезпечує стабільність макета, однак має високу обчислювальну складність і менш наочний у разі інтерактивної візуалізації змін конфігурації графа через різкі переміщення окремих вершин. Алгоритм Ідса придатний для роботи з розрідженими графами або деревоподібними структурами, але поступається за якістю під час роботи зі щільними графами. Розроблена система підтримує автоматичне реагування на зміну структури графа та повторний запуск алгоритму, що дає змогу відображати актуальний стан макета в режимі реального часу. Запропоновано напрям подальших досліджень, пов’язаний із використанням нейронних мереж для автоматичної оцінки якості макетів, класифікації типу графа та вибору оптимального алгоритму й параметрів його роботи. Очікується, що це підвищить ефективність, точність і зручність візуалізації графів у динамічних системах, забезпечивши нові можливості для моніторингу, аналізу та прийняття рішень на основі графових моделей.

[1] Birch, K., Cochrane, D. T., & Ward, C. (2021). Data as asset? The measurement, governance, and valuation of digital personal data by Big Tech. Big Data & Society, 8(1), 115. https://doi.org/10.1177/20539517211017308

[2] Gupta, S., Justy, T., Kamboj, S., Kumar, A., & Kristo- ffersen, E. (2021). Big data and firm marketing performance: Findings from knowledge-based view. Technological Forecasting and Social Change, 171, Article 120986. https://doi.org/ 10.1016/ j.techfore.2021.120986

[3] Boeing, G. (2025). Modeling and analyzing urban networks and amenities with OSMnx (Working paper). University of Southern California. Retrieved from: https://geoffboeing. com/share/osmnx-paper.pdf

[4] Rathore, M. M., Shah, S. A., Awad, A., Shukla, D., Vimal, S., & Paul, A. (2021). A cyber-physical system and graph-based approach for transportation management in smart cities. Sustainability, 13(14), Article 7606. https://doi.org/ 10.3390/ su13147606

[5] Anisa, R., Prihandini, R. M., Alvina, D. A. R. J., Makhfud- loh, I. I., Agatha, A. B., & Wulandari, Y. N. (2024). Application of graph theory in computer network optimization. Retrieved from: https://www.researchgate.net/ publication/ 381490742_Application_of_Graph_Theory_in_ Computer_Network_Optimization

[6] Logan, A. P., LaCasse, P. M., & Lunday, B. J. (2023). Social network analysis of Twitter interactions: A directed multilayer network approach. Social Network Analysis and Mining, 13(65). https://doi.org/10.1007/s13278-023-01063-2

[7] Aksoy, S. G., Purvine, E., Cotilla-Sanchez, E., & Halappa- navar, M. (2018). A generative graph model for electrical infrastructure networks. Journal of Complex Networks, 7(1), 128–162. https://doi.org/10.1093/comnet/cny016

[8] Bi, S., & Zhang, Y. J. A. (2016). Graph-based cyber security analysis of state estimation in smart power grid. IEEE Communications Magazine, arXiv preprint arXiv:1612. 05878. https://arxiv.org/abs/1612.05878

[9] Graph Layout Benchmark Datasets. Retrieved March 26, 2025, from: https://visdunneright.github.io/gd_ benchmark_sets/

[10] Beck, F., Burch, M., Diehl, S., & Weiskopf, D. (2014). The state of the art in visualizing dynamic graphs. In R. Borgo, R. Maciejewski, & I. Viola (Eds.), Eurographics Conference on Visualization (EuroVis) – STARs. The Eurographics Association. https://doi.org/10.2312/eurovisstar.20141174

[11] Cheong, S.-H., Si, Y.-W., & Wong, R. K. (2021). Online force-directed algorithms for visualization of dynamic graphs. Information Sciences, 556, 223–255. https://doi.org/ 10.1016/ j.ins.2020.12.068

[12] Kobourov, S. G. (2013). Force-directed algorithms for schematic drawings and placement: A survey. In Handbook of Graph Drawing and Visualization (pp. 383–408). CRC Press. https://doi.org/10.1016/j.ins.2020.12.069

[13] Cheong, S.-H., & Si, Y.-W. (2020). Force-directed algorithms for schematic drawings and placement: A survey. Information Visualization, 19(1), 6591. https://doi.org/ 10.1177/ 1473871618821740

[14] Eades, P. (1984). A heuristic for graph drawing. Congressus Numerantium, 42, 149–160. Retrieved from https://www. cs.ubc.ca/~will/536E/papers/Eades1984.pdf

[15] Fruchterman, T. M. J., & Reingold, E. M. (1991). Graph drawing by force-directed placement. Software: Practice and Experience, 21(11), 1129–1164. https://doi.org/10.1002/spe. 4380211102

[16] Kamada, T., & Kawai, S. (1989). An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1), 715. https://doi.org/10.1016/0020-0190(89)90102-6

[17] Danych, I., & Shpak, Z. (2024). Practical and educational application for interaction with graphs. In Proceedings of the 1st International Scientific and Practical Conference “Computational Intelligence and Smart Systems” (CISS- 2024) (pp. 37–39). Lviv: ATB Publishing.