Link Prediction and Maximum Flow in Transportation Network

Abstract

This study conducted link prediction analysis and maximum flow analysis, which provide critical insights into alternative route inferences and traffic flow, based on real transportation network data. The dataset used in the analysis was specifically generated for this purpose. Data collection involved Bluetooth vehicle counting devices installed at 54 intersection points in the city center of Malatya, Turkey. The methodology leveraged approximately 50 million vehicle transition records to weight the transportation network graph. The Ford-Fulkerson method was utilized for the maximum flow analysis, while the Jaccard similarity metric was employed for the link prediction analysis. The graph construction and all analysis processes were carried out using the R programming language and the igraph graph library. The results of the analyses provided significant insights into alternative route corridors within the transportation network and the maximum traffic capacity of the roads. Consequently, the findings enabled the identification of critical points and potential congestion areas. The outcomes are expected to make a substantial contribution to enhancing the efficiency of the transportation network and improving traffic management strategies.

Keywords

• Transportation Networks
• Maximum flow
• Link predection.

Ulaşım Ağında Bağlantı Tahmini ve Maksimum Akış

Abstract

Bu çalışmada gerçek bir ulaşım ağı verisi üzerinde alternatif yol çıkarımları için kullanılan link prediction ve trafiği akışı hakkında önemli bilgiler sunan maximum flow analizi gerçekleştirilmiştir. Analiz için kullanılan veri seti bu analiz için özgün olarak üretilmiştir. Veri seti için Malatya ili kent merkezinde 54 kavşak noktasında kurulu bluetooth araç sayım cihazları kullanılmıştır. Analiz için yaklaşım 50 milyon araç geçisi verisi ile ulaşım ağı çizgesinin ağırlıklandırılmasında kullanılmıştır. Maximum flow analizi için Ford-Fulkerson yöntemi, link prediction analizi için jaccard similarity metriği kullanılmıştır. Çizgenin oluşturulması ve tüm analiz süreçlerinde R dili ve igraph çizge kütüphanesi kullanılmıştır. Elde edilen analiz sonuçları neticesinde ulaşım ağında alternatif yol güzergahları ve yolların taşıyabileceği maksimum trafik hakkında önemli bilgilere ulaşılmıştır. Bu sayede kritik noktaların ve potansiyel tıkanıklıkların belirlenmesinede olanak tanınmıştır. Elde edilen sonuçların, ulaşım ağının verimliliğini artırmak ve trafik yönetim stratejilerini geliştirmek için önemli bir katkı sunması beklenmektedir.

Keywords

• Ulaşım ağları
• Bağlantı tahmini
• Maksimum akış

References

1. [1] F. Öztemiz, “AMFC: A New Approach Efficient Junctions Detect via Maximum Flow Approach”, Bitlis Eren Üniversitesi Fen Bilimleri Dergisi, vol. 12, no. 4, pp. 1054–1068, 2023, doi: 10.17798/bitlisfen.1325877.
2. [2] Ivchenko, G. I., & Honov, S. A. (1998). On the jaccard similarity test. Journal of Mathematical Sciences, 88, 789-794.
3. [3] Mahmoud Owais, Ahmed E. Matouk, "A factorization scheme for observability analysis in transportation networks," Expert Systems with Applications, vol. 174, 2021, p. 114727, ISSN: 0957-4174. DOI: 10.1016/j.eswa.2021.114727.
4. [4] Hark, Cengiz. (2024) The power of graphs in medicine: Introducing BioGraphSum for effective text summarization, Heliyon, Volume 10, Issue 11,
5. [5] Ekanayake, E. M. U. S. B., Daundasekara, W. B., & Perera, S. P. C. (2022). New Approach to Obtain the Maximum Flow in a Network and Optimal Solution for the Transportation Problems. Modern Applied Science, 16(1), 30.
6. [6] Schrijver, A. (2002). On the history of the transportation and maximum flow problems. Mathematical programming, 91, 437-445.
7. [7] Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., & Sachdeva, S. (2022, October). Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 612-623). IEEE.
8. [8] Du, M., Jiang, X., & Chen, A. (2022). Identifying critical links using network capacity-based indicator in multi-modal transportation networks. Transportmetrica B: Transport Dynamics, 10(1), 1126-1150.

9. [9] Akgün, İ., Tansel, B. Ç., & Wood, R. K. (2011). The multi-terminal maximum-flow network-interdiction problem. European Journal of Operational Research, 211(2), 241-251.
10. [10] Mukherjee, T., Sangal, I., Sarkar, B., & Alkadash, T. M. (2022). Mathematical estimation for maximum flow of goods within a cross-dock to reduce inventory. Math. Biosci. Eng, 19(12), 13710-13731.
11. [11] Mahlous, A. R., Fretwell, R. J., & Chaourar, B. (2008, September). MFMP: max flow multipath routing algorithm. In 2008 Second UKSIM European Symposium on Computer Modeling and Simulation (pp. 482-487). IEEE.
12. [12] Gu, S., Li, K., Liang, Y., & Yan, D. (2021). A transportation network evolution model based on link prediction. International Journal of Modern Physics B, 35(31), 2150316.
13. [13] R. Rai and J. Grover, "Comparative Analysis of Cosine and Jaccard Similarity-Based Classification for Detecting CAN Bus Attacks," 2024 IEEE Region 10 Symposium (TENSYMP), New Delhi, India, 2024, pp. 1-6, doi: 10.1109/TENSYMP61132.2024.10752180.
14. [14] Srinivas, V., Mitra, P., Srinivas, V., & Mitra, P. (2016). Applications of link prediction. Link Prediction in Social Networks: Role of Power Law Distribution, 57-61.
15. [15] Ma, Y., Liang, X., Huang, J., & Cheng, G. (2017, November). Intercity transportation construction based on link prediction. In 2017 IEEE 29th international conference on tools with artificial intelligence (ICTAI) (pp. 1135-1138). IEEE.
16. [16] Li, X., & Li, P. (2021, May). Rejection sampling for weighted jaccard similarity revisited. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 5, pp. 4197-4205).
17. [17] Wang, G., Wang, Y., Li, J., & Liu, K. (2021). A multidimensional network link prediction algorithm and its application for predicting social relationships. Journal of Computational Science, 53, 101358.
18. [18] Cai, L., Li, J., Wang, J., & Ji, S. (2021). Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9), 5103-5113.
19. [19] Lü, L., & Zhou, T. (2011). Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6), 1150-1170.
20. [20] Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020). Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applications, 553, 124289.
21. [21] Bag, S., Kumar, S. K., & Tiwari, M. K. (2019). An efficient recommendation generation using relevant Jaccard similarity. Information Sciences, 483, 53-64.
22. [22] Costa, L. D. F. (2021). Further generalizations of the Jaccard index. arXiv preprint arXiv:2110.09619.
23. [23] Vorontsov, I. E., Kulakovskiy, I. V., & Makeev, V. J. (2013). Jaccard index based similarity measure to compare transcription factor binding site models. Algorithms for Molecular Biology, 8, 1-11.
24. [24] Topaloğlu, F., & Bozbay Korkmaz, E. (2024). Desıgnıng AHP Based Decısıon Support System: E-Commerce Sıte Selectıon. NATURENGS, 5(1), 31-40. https://doi.org/10.46572/naturengs.1478408.