{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:20:20Z","timestamp":1777645220927,"version":"3.51.4"},"reference-count":38,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Agence Universitaire de la Francophonie with the National Council for Scientific Research in Lebanon","award":["ARCUS E2D2"],"award-info":[{"award-number":["ARCUS E2D2"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Road traffic congestion has became a major problem in most countries because it affects sustainable mobility. Partitioning a transport network into homogeneous areas can be very useful for monitoring traffic as congestion is spatially correlated in adjacent roads, and it propagates at different speeds as a function of time. Spectral clustering has been successfully applied for the partitioning of transportation networks based on the spatial characteristics of congestion at a specific time. However, this type of classification is not suitable for data that change over time. Evolutionary spectral clustering represents a state-of-the-art algorithm for grouping objects evolving over time. However, the disadvantages of this algorithm are the cubic time complexity and the high memory demand, which make it insufficient to handle a large number of data sets. In this paper, we propose an efficient evolutionary spectral clustering algorithm that solves the drawbacks of evolutionary spectral clustering by reducing the size of the eigenvalue problem. This algorithm is applied in a dynamic environment to partition a transportation network into connected homogeneous regions that evolve with time. The number of clusters is selected automatically by using a density peak algorithm adopted for the classification of traffic congestion based on the sparse snake similarity matrix. Experiments on the real network of Amsterdam city demonstrate the superiority of the proposed algorithm in robustness and effectiveness.<\/jats:p>","DOI":"10.3390\/a15030076","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T21:11:07Z","timestamp":1645737067000},"page":"76","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Partitioning of Transportation Networks by Efficient Evolutionary Clustering and Density Peaks"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2907-3399","authenticated-orcid":false,"given":"Pamela","family":"Al Alam","sequence":"first","affiliation":[{"name":"LISIC, University of Littoral C\u00f4te d\u2019Opale (ULCO), Calais, BP 719, CEDEX, 62228 Calais, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7911-1218","authenticated-orcid":false,"given":"Joseph","family":"Constantin","sequence":"additional","affiliation":[{"name":"LaRRIS, Faculty of Sciences, Lebanese University, Fanar, Jdeidet BP 90656, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4252-0819","authenticated-orcid":false,"given":"Ibtissam","family":"Constantin","sequence":"additional","affiliation":[{"name":"LaRRIS, Faculty of Sciences, Lebanese University, Fanar, Jdeidet BP 90656, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7674-3519","authenticated-orcid":false,"given":"Clelia","family":"Lopez","sequence":"additional","affiliation":[{"name":"ERIC, Universit\u00e9 de Lyon, Universit\u00e9 de Lyon 2, ERIC UR 3083 5  Avenue Pierre Mend\u00e8s France, CEDEX, F69676 Bron, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"7784","DOI":"10.3390\/su7067784","article-title":"Sustainable Urban Transport in the Developing World: Beyond Megacities","volume":"7","author":"Pojani","year":"2015","journal-title":"Sustainability"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.trpro.2015.09.054","article-title":"A Semi-decentralized Control Strategy for Urban Traffic","volume":"10","author":"Farhi","year":"2015","journal-title":"Transp. Res. Procedia"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1016\/j.proeng.2015.08.216","article-title":"Planning of the Traffic System in Urban Environments","volume":"117","author":"Zafirovski","year":"2015","journal-title":"Procedia Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1537","DOI":"10.1109\/TITS.2011.2161469","article-title":"On the Effectiveness of an Opportunistic Traffic Management System for Vehicular Networks","volume":"12","author":"Leontiadis","year":"2011","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Yuan, J., Zheng, Y., Xie, X., and Sun, G. (2011, January 21\u201324). Driving with knowledge from the physical world. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/2020408.2020462"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.trb.2017.08.021","article-title":"Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks","volume":"105","author":"Saeedmanesh","year":"2017","journal-title":"Transp. Res. Part B"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1016\/j.trb.2012.08.005","article-title":"On the spatial partitioning of urban transportation networks","volume":"46","author":"Ji","year":"2012","journal-title":"Transp. Res. Part B"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/j.trb.2016.05.008","article-title":"Clustering of heterogeneous networks with directional flows based on \u201cSnake\u201d similarities","volume":"91","author":"Saeedmanesh","year":"2016","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s10844-006-9953-7","article-title":"Time-focused clustering of trajectories of moving objects","volume":"27","author":"Nanni","year":"2006","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Jeung, H., Shen, H.T., and Zhou, X. (2008, January 7\u201312). Convoy queries in spatio-temporal databases. Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, Cancun, Mexico.","DOI":"10.1109\/ICDE.2008.4497588"},{"key":"ref_11","unstructured":"El Mahrsi, M.K., and Rossi, F. (2012). Modularity-based clustering for network-constrained trajectories. arXiv."},{"key":"ref_12","unstructured":"El Mahrsi, M.K., and Rossi, F. (2022, January 19). Graph-Based Approaches to Clustering Network-Constrained Trajectory Data, Available online: http:\/\/xxx.lanl.gov\/abs\/1210.0762."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.trb.2016.10.011","article-title":"Enhancing model-based feedback perimeter control with data-driven online adaptive optimization","volume":"96","author":"Kouvelas","year":"2017","journal-title":"Transp. Res. Part B"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.comnet.2018.04.008","article-title":"Autonomuous data driven surveillance and rectification system using in vehicle sensors for intelligence transportation system (ITS)","volume":"139","author":"Khalid","year":"2018","journal-title":"Comput. Netw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jpdc.2017.08.014","article-title":"A rear end collision prediction scheme based on deep learning in the internet of vehicles","volume":"117","author":"Chen","year":"2018","journal-title":"Parallel Distrib. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Tuffery, S. (2011). Data Mining and Statistics for Decision Making, John Wiley and Sons, Ltd.. [2nd ed.].","DOI":"10.1002\/9780470979174"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"98","DOI":"10.3141\/2623-11","article-title":"Spatio-temporal partitioning of transportation network using travel time data","volume":"2623","author":"Lopez","year":"2017","journal-title":"Transp. Res. Rec. J. Trasp. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B.L. (2007, January 12\u201315). Evolutionary Spectral Clustering by Incorporating Temporal Smoothness. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA.","DOI":"10.1145\/1281192.1281212"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Al Alam, P., Hamad, D., Constantin, J., Constantin, I., and Zaatar, Y. (2020, January 25\u201326). Dynamic Partitioning of Transportation Network Using Evolutionary Spectral Clustering. Proceedings of the Smart Applications and Data Analysis, Third International Conference, Marrakesh, Morocco.","DOI":"10.1007\/978-3-030-45183-7_13"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Dinh, D.T., Fujinami, T., and Huynh, V.N. (2019). Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient. International Symposium on Knowledge and Systems Sciences, Springer.","DOI":"10.1007\/978-981-15-1209-4_1"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Astolfi, D., and Pandit, R. (2022). Multivariate Wind Turbine Power Curve Model Based on Data Clustering and Polynomial LASSO Regression. Appl. Sci., 12.","DOI":"10.3390\/app12010072"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1111\/1467-9868.00293","article-title":"Estimating the number of clusters in a data set via the gap statistic","volume":"63","author":"Tibshirani","year":"2001","journal-title":"J. R. Stat. B"},{"key":"ref_23","unstructured":"Salvador, S., and Chan, P. (2004, January 15\u201317). Determining the number of clusters\/segments in hierarchical clustering\/segmentation algorithms. Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, FL, USA."},{"key":"ref_24","unstructured":"Lopez, C. (2017). Mod\u00e9lisation Dynamique du Trafic et Transport de Marchandises en Ville: Vers une Approche Combin\u00e9e. [Ph.D. Thesis, Universit\u00e9 de Lyon]."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.patrec.2016.08.012","article-title":"Efficient evolutionary spectral clustering","volume":"84","author":"Langone","year":"2016","journal-title":"Pattern Recognit. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.cam.2012.07.019","article-title":"Sparse spectral clustering method based on the incomplete Cholesky decomposition","volume":"237","author":"Frederix","year":"2013","journal-title":"J. Comput. Appl. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.jmva.2006.11.013","article-title":"Comparing clusterings\u2014An information based distance","volume":"98","author":"Meila","year":"2007","journal-title":"J. Multivar. Anal."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.eswa.2017.11.020","article-title":"Comparative density peaks clustering","volume":"95","author":"Li","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Zhang, H., Kiranyaz, S., and Gabbouj, M. (2018, January 4\u20136). Data Clustering Based on Community Structure in Mutual k-Nearest Neighbor Graph. Proceedings of the 41st International Conference on Telecommunications and Signal Processing (TSP), Athens, Greece.","DOI":"10.1109\/TSP.2018.8441226"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Yan, H., Lu, Y., and Ma, H. (2018, January 16\u201318). Density-based Clustering using Automatic Density Peak Detection. Proceedings of the International Conference on Pattern Recognition Applications and Methods, Madeira, Portugal.","DOI":"10.5220\/0006572300950102"},{"key":"ref_33","unstructured":"Wang, S., Wang, D., Li, C., and Li, Y. (2022, January 19). Comment on \u201cClustering by Fast Search and Find of Density Peaks\u201d, Available online: http:\/\/xxx.lanl.gov\/abs\/1501.04267."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Yu, L., and Ding, C. (2010, January 24\u201325). Network community discovery: Solving modularity clustering via normalized cut. Proceedings of the Eighth Workshop on Mining and Learning with Graphs, Washington, DC, USA.","DOI":"10.1145\/1830252.1830257"},{"key":"ref_35","unstructured":"Scott, W., and Padhraic, S. (2005, January 21\u201323). A Spectral Clustering Approach To Finding Communities in Graphs. Proceedings of the 2005 SIAM International Conference on Data Mining, Newport Beach, CA, USA."},{"key":"ref_36","unstructured":"Ng, A.Y., Jordan, M.I., and Weiss, Y. (2001, January 3\u20138). On spectral clustering: Analysis and an algorithm. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/s10618-012-0302-x","article-title":"Adaptive evolutionary clustering","volume":"28","author":"Xu","year":"2014","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_38","unstructured":"Hong, C., Jingjing, Z., Chunfeng, C., and Qinyu, C. (2016, January 9\u201310). Solving large-scale assignment problems by Kuhn-Munkres algorithm. Proceedings of the 2nd International Conference on Advances in Mechanical Engineering and Industrial Informatics, Hangzhou, China."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/76\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:26:54Z","timestamp":1760135214000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":38,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030076"],"URL":"https:\/\/doi.org\/10.3390\/a15030076","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,24]]}}}