Clustering problem in self-organising communication networks on the example of smart vehicle transportation system

Marek Antosiewicz; Przemysław  Szufel; Bogumił Kamiński; Agata Skorupka; Paweł Prałat; Atefeh Mashatan

doi:https://doi.org/10.59139/ps.2025.04.1

Marek Antosiewicz SGH Warsaw School of Economics, Collegium of Economic Analysis, Al. Niepodległości 162, 02–554 Warszawa, Poland ORCID:https://orcid.org/0000-0003-3035-8591 , Przemysław Szufel SGH Warsaw School of Economics, Collegium of Economic Analysis, Al. Niepodległości 162, 02–554 Warszawa, Poland ORCID:https://orcid.org/0000-0001-9525-3497 , Bogumił Kamiński SGH Warsaw School of Economics, Collegium of Economic Analysis, Al. Niepodległości 162, 02–554 Warszawa, Poland ORCID:https://orcid.org/0000-0002-0678-282X , Agata Skorupka SGH Warsaw School of Economics, Collegium of Economic Analysis, Al. Niepodległości 162, 02–554 Warszawa, Poland ORCID:https://orcid.org/0000-0003-4487-8758 , Paweł Prałat Toronto Metropolitan University, Department of Mathematics, 350 Victoria St., Toronto, ON, M5B 2K3, Canada ORCID:https://orcid.org/0000-0001-8898-8778 , Atefeh Mashatan Toronto Metropolitan University, Department of Information Technology Management, 55 Dundas Street West, Toronto, ON, M5G 2C3, Canada ORCID:https://orcid.org/0000-0001-9448-9123 Przegląd Statystyczny. Statistical Review, vol. 72, 2025, 4, pages: 1-24 Published online: 23 March 2026 DOI https://doi.org/10.59139/ps.2025.04.1 Citation: Antosiewicz, M., Szufel, P., Kamiński, B., Skorupka, A. Prałat, P., & Mashatan, A. (2025). Clustering problem in self-organising communication networks on the example of smart vehicle transportation system. Przegląd Statystyczny. Statistical Review, 72(4), 1–24. https://doi.org/10.59139/ps.2025.04.1.

83 Views 12 Downloads

ARTICLE

(English) PDF

ABSTRACT

Efficient communication in many types of dynamic networks depends critically on how nodes are clustered into subnetworks. As such networks grow and evolve rapidly, there is a need for fast and robust clustering algorithms that account for communication cost structures induced by different node partitions. In this paper, we evaluate how classic community detection algorithms (CDAs), i.e. the Louvain and Ensemble Clustering for Graphs (ECG), adapted to incorporate a flexible family of cost functions, perform relative to standard heuristic and metaheuristic approaches. Using simulations on l-nearest neighbour graphs of varying sizes, we find that especially the Louvain algorithm consistently delivers high quality solutions at a substantially lower computational cost. In contrast, metaheuristic methods fail to scale effectively, and the ECG algorithm does not provide performance improvements in our setting, despite its reported stabilising effect in traditional community detection tasks. Overall, our results indicate that classic CDAs are well suited for real time clustering in dynamic communication networks and constitute a strong basis for developing scalable communication optimisation strategies.

KEYWORDS

transport networks, communication networks, network design, graph clustering

JEL

D85, C61, L90

REFERENCES

Badis, H., & Rachedi, A. (2015). Modeling tools to evaluate the performance of wireless multi-hop networks. In M. S. Obaidat, P. Nicopolitidis & F. Zarai (Eds.), Modeling and Simulation of Computer Networks and Systems. Methodologies and Applications (pp. 653–682). https://doi.org/10.1016/B978-0-12-800887-4.00023-7.

Balister, P., Bollobás, B., Sarkar, A., & Walters, M. (2005). Connectivity of random k-nearest-neighbour graphs. Advances in Applied Probability, 37(1), 1–24. https://doi.org/10.1239/aap/1113402397.

Bentley, J. L. (1980). Multidimensional Divide-and-Conquer. Communications of the ACM, 23(4), 214–229. https://doi.org/10.1145/358841.358850.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, (10), 1–12. https://doi.org/10.1088/1742-5468/2008/10/P10008.

Clarkson, K. L. (1983). Fast algorithms for the all nearest neighbors problem. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (pp. 226–232). IEEE Computer Society. https://doi.org/10.1109/SFCS.1983.16.

Coppola, R., & Morisio, M. (2016). Connected Car: technologies, issues, future trends. ACM Computing Surveys, 49(3), 1–36. https://doi.org/10.1145/2971482.

Creswick, N., Westbrook, J. I., & Braithwaite, J. (2009). Understanding communication networks in the emergency department. BMC Health Services Research, 9(1), 1–9. https://doi.org/10.1186/1472-6963-9-247.

Demirbas, M., Arora, A., Mittal, V., & Kulathumani, V. (2004). Design and analysis of a fast local clustering service for wireless sensor networks. In Proceedings. First International Conference on Broadband Networks (pp. 700–709). Institute of Electrolical and Electronics Engineers. https://doi.org/10.1109/BROADNETS.2004.30.

Esteves, R. P., Granville, L. Z., & Boutaba, R. (2013). On the management of virtual networks. IEEE Communications Magazine, 51(7), 80–88. https://doi.org/10.1109/MCOM.2013.6553682.

Gerla, M., & Kleinrock, L. (1977). On the Topological Design of Distributed Computer Networks. IEEE Transactions on Communications, 25(1), 48–60. https://doi.org/10.1109/TCOM.1977.1093709.

Hallac, D., Leskovec, J., & Boyd, S. (2015). Network Lasso: Clustering and Optimization in Large Graphs. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 387–396). https://doi.org/10.48550/arXiv.1507.00280.

Hbaieb, A., Ayed, S., & Fourati, L. (2021). Internet of Vehicles and Connected Smart Vehicles Communication System Towards Autonomous Driving. https://doi.org/10.21203/rs.3.rs-493419/v1.

Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. https://doi.org/10.1109/HICSS.2000.926982.

Hussain, K., Mohd Salleh, M. N., Cheng, S., & Shi, Y. (2019). Metaheuristic research: A comprehensive survey. Artificial Intelligence Review, 52, 2191–2233. https://doi.org/10.1007/s10462-017-9605-z.

Kaiwartya, O., Abdullah, A. H., Cao, Y., Altameem, A., Prasad, M., Lin, C.-T., & Liu, X. (2016). Internet of Vehicles: Motivation, Layered Architecture, Network Model, Challenges, and Future Aspects. IEEE Access, 4, 5356–5373. https://doi.org/10.1109/ACCESS.2016.2603219.

Kamiński, B., Prałat, P., & Théberge, F. (2021). Mining Complex Networks. CRC Press.

Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: A comparative analysis. Physical Review E, 80(5), 1–12. https://doi.org/10.1103/PhysRevE.80.056117.

Lu, N., Cheng, N., Zhang, N., Shen, X., & Mark, J. W. (2014). Connected Vehicles: Solutions and Challenges. IEEE Internet of Things Journal, 1(4), 289–299. https://doi.org/10.1109/JIOT.2014.2327587.

Mothe, J., Mkhitaryan, K., & Haroutunian, M. (2017). Community detection: Comparison of state of the art algorithms. In S. Shoukourian (Ed.), Computer Science and Information Technologies (pp. 125–129). Institute of Electrolical and Electronics Engineers. https://doi.org/10.1109/CSITechnol.2017.8312155.

Mukhtaruzzaman, M., & Atiquzzaman, M. (2020). Clustering in VANET: Algorithms and challenges. https://arxiv.org/pdf/2009.01964.

O’Malley, S. W., & Peterson, L. L. (1992). A dynamic network architecture. ACM Transactions on Computer Systems, 10(2), 110–143. https://doi.org/10.1145/128899.128901.

Paul, A., Chilamkurti, N., Daniel, A., & Rho, S. (2017). Intelligent Vehicular Networks and Communications. Fundamentals, Architectures and Solutions. Elsevier. https://doi.org/10.1016/C2015-0-04087-4.

Poulin, V., & Théberge, F. (2018). Ensemble clustering for graphs. In L. M. Aiello, C. Cherifi, H. Cherifi, R. Lambiotte, P. Lió & L. M. Rocha (Eds.), Complex Networks and Their Applications: VII: vol. 1. Proceedings The 7th International Conference of Complex Networks and Their Applications. Complex Networks 2018 (pp. 231–243). Springer. https://doi.org/10.1007/978-3-030-05411-3_19.

Poulin, V., & Théberge, F. (2019). Ensemble clustering for graphs: Comparisons and applications. Applied Network Science, 4(1), 1–13. https://doi.org/10.1007/s41109-019-0162-z.

Qureshi, K. N., & Abdullah, A. H. (2013). A Survey on Intelligent Transportation Systems. Middle-East Journal of Scientific Research, 15(5), 629–642. https://doi.org/10.5829/idosi.mejsr.2013.15.5.11215.

Shahraki, A., Taherkordi, A., Haugen, O., & Eliassen, F. (2020). Clustering objectives in wireless sensor networks: A survey and research direction analysis. Computer Networks, 180, 1–18. https://doi.org/10.1016/j.comnet.2020.107376.

Soares, V., & Rodrigues, J. (2021). Vehicular delay-tolerant networks. In J. J. P. C. Rodrigues (Ed.), Advances in Delay-Tolerant Networks (DTNs). Architecture and Enhanced Performance (2nd edition; pp. 59–78). Woodhead Publishing. https://doi.org/10.1016/B978-0-08-102793-6.00004-7.

Sun, Z., Liu, Y., Wang, J., Anil, C., & Cao, D. (2020). Game theoretic approaches in vehicular networks: A survey. https://doi.org/10.48550/arXiv.2006.00992.

Tai, C.-F., Chiang, T.-C., & Hou, T.-W. (2011). A virtual subnet scheme on clustering algorithms for mobile ad hoc networks. Expert Systems with Applications, 38(3), 2099–2109. https://doi.org/10.1016/j.eswa.2010.07.148.

Vaidya, P. M. (1989). An O(n log n) Algorithm for the All-Nearest-Neighbors Problem. Discrete & Computational Geometry, 4(2), 101–115. https://doi.org/10.1007/BF02187718.

Younis, O., & Fahmy, S. (2004). Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy-Efficient Approach. In IEEE INFOCOM 2004. The Conference on Computer Communications (Vol. 1; pp. 1–12). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/INFCOM.2004.1354534.