Optimization of data transfer in urban information systems based on graph theory methods

D.A. Rybakov

---

Abstract: The Moscow Urban Information Systems managed by the DIT represent a complex distributed ecosystem generating and processing huge volumes of heterogeneous data. Efficient transmission of this data, especially for critical services with strict requirements for latency and reliability, is a key factor in the functioning of the “smart city” and the quality of public services. Optimization of data transmission in the Moscow GIS based on graph theory is critical to improve QoS, reliability and efficiency.
Aim. The research objective is to develop and verify methods for optimizing data transmission in urban information systems based on graph theory. The objectives include reducing delays, improving reliability, and enhancing the efficiency of network resources for critical services.
Methods. The study was based on detailed modeling of the Moscow DIT infrastructure as a weighted graph, where vertices represent data processing/storage nodes, and edges represent communication channels with attributes of throughput, latency and reliability. Data flows for key services were specified with QoS requirements.
Results. For optimization, specialized graph algorithms are used: modified A* with geographic heuristics for QoS routing, load balancing algorithms based on searching for the maximum flow/minimum cost, and methods for ensuring fault tolerance through searching for k-disjoint paths (k = 2). Using the A* algorithm allow us to reduce the average delay in video stream transmission for the Safe City system by 22–35 % compared to the basic approaches, while guaranteeing SLA compliance (<150 ms). The load balancing algorithms reduce the 95th percentile of transaction delays for making an appointment with a doctor from 65 ms to 42 ms by preventing overloads of key nodes. Using two disjoint backup paths reduce the recovery time for critical services after a channel failure from 500 ms to 50 ms.
Conclusions. The obtained results convincingly prove the high practical value of applying graph theory to optimizing data transmission in large-scale urban systems. Taking into account the geographical specificity and hierarchical structure of the Moscow network proved to be a critical factor in success

Keywords: graph theory, urban information systems, data transmission optimization, QoS

For citation. Rybakov D.A., Optimization of data transfer in urban information systems based on graph theory methods. News of the Kabardino-Balkarian Scientific Center of RAS. 2025. Vol. 27. No. 5. Pp. 168–179. DOI: 10.35330/1991-6639-2025-27-5-168-179

References

1. Karunuzhali D., Meenakshi B., Keerthi L. A QoS-aware routing approach for Internet of Things-enabled wireless sensor networks in smart cities. Multimedia Tools and Applications. Vol. 84. Pp. 17951–17977. DOI: 10.1007/s11042-024-18125-y
2. Debajit S. Applications of graphs in smart cities. In book: Handbook of Research on Data-Driven Mathematical Modelling in Smart Cities. 2023. Pp. 40–54. DOI: 10.4018/978-1-6684-6408-3.ch003
3. Wester C.H. Schoonenberg, Inas S. Khayal, Amro M. Farid. A Hetero-functional graph theory for modeling interdependent smart city infrastructure: book. Springer. 196 p. DOI:
   10.1007/978-3-319-99301-0
4. Jing Q., Yuhan Ch., Zhihong T. et al. Automatic concept extraction based on semantic graphs from big data in smart city. IEEE Transactions on Computational Social Systems. 2019. Pp. 1–9. DOI: 10.1109/TCSS.2019.2946181
5. Dhanasekaran S., Dhanalakshmi G., Logeshwaran J. et al. Multi-model traffic forecasting in smart cities using graph neural networks and transformer-based multi-source visual fusion for intelligent transportation management. International Journal of Intelligent Transportation Systems Research. 2024. Vol. 22. Pp. 1–22. DOI: 10.1007/s13177-024-00413-4
6. Itskov A.G. Elements of discrete mathematics. Set theory, combinatorics, graph theory: Izhevsk: Izhevsk Institute of Computer Research, 2023. Pp. 77–94. (In Russian)
7. Grishko N.V. Spectral theory of finite regular graphs as a mean of modeling data transmission processes in computer networks. Proceedings of the conference “Donetsk Readings 2022: Education, Science, Innovation, Culture and Challenges of Our Time”. 2022. Pp. 143–145. (In Russian)
8. Rogalevich P.I., Zhikharev A.P. Smart City System. Organization of data transmission. Modern Means of Communication. 2022. Vol. 1. No. 1. Pp. 344–345. EDN: GVASPT. (In Russian)

Information about the author

Daniil A. Rybakov, Postgraduate Student of the Department of Computer Science, Plekhanov Russian University of Economics;
36 Stremyannyy lane, Moscow, 115054, Russia;
Data Engineer, Data Analysis and Processing Department, Department of Information Technology, City of Moscow;
12с1, Yakovoapostolsky lane, Moscow, 107078, Russia;
rybakov.daniel99@gmail.com, ORCID: https://orcid.org/0009-0005-8959-4427, SPIN-code: 7155-6461