Calculation of centrality in the analysis of congestion of city roads on the example of Petrozavodsk

Natalia N. Nikitina ; Evgeny E. Ivashko

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 3, pp. 41-63.

Résumé

Centrality is a numerical measure that characterizes the structural properties of a graph. In the presented work, centrality is used to analyze the load of the graph of urban roads in the city of Petrozavodsk. In the paper, we describe the method used to construct the road graph, present a modified centrality measure that takes into account the features of the transport network and the distribution of passenger traffic, and demonstrate the results of numerical simulations. For the transport graph, betweenness centralities were calculated with and without regard to the distribution of passenger traffic; a connectivity analysis was carried out to identify critical, overloaded and reserve roads, and the routes that make the greatest contribution to the centrality of the most loaded roads. The obtained results show that centrality can be used for the analysis of the structural features of the graph of urban roads, modeling sustainability and planning the development of the transport network.

Détail

Keywords: graph theory, centrality, transport graph, betweenness centrality.

Bibliographie

[1] Bredikhin S., Lyapunov V.M., Scherbakova N.G., Yurgenson A.N., “Parametry «tsentralnosti» uzlov seti tsitirovaniya nauchnykh statei”, Problemy informatiki, 2016, no. 1 (30), 39–57

[2] Bukashev A.A., Marchenko D.K., Evin I.A., Izuchenie strukturnoi slozhnosti dorozhnoi seti staroi i novoi Moskvy https://spkurdyumov.ru/networks/izuchenie-strukturnoj-slozhnosti-dorozhnoj-seti-staroj-i-novoj-moskvy/

[3] Nekraplennaya M.N., Namiot D.E., “Analiz matrits korrespondentsii metro”, International Journal of Open Information Technologies, 2019, no. 7, 68–80

[4] Nurminskii E.A., Shamrai N.B., “Modelirovanie transportnykh potokov g. Vladivostoka na osnove teorii ravnovesiya”, Sisteme de transport si logistica, materialele Conferintei Internationale (Chisinau, 2009), 334–348

[5] Batista R.D, Bazzan A.L., “Identification of central points in road networks using betweenness centrality combined with traffic demand”, Polibits, 2015, 85–91 | DOI

[6] Bavelas A., “A mathematical model for group structures”, Human organization, 7:3 (1948), 16–30 | DOI

[7] Bavelas A., “Communication patterns in task-oriented groups”, The journal of the acoustical society of America, 22:6 (1950), 725–30 | DOI

[8] Cardillo A., Scellato S., Latora V., Porta S., “Structural properties of planar graphs of urban street patterns”, Phys. Rev., 73 (2006), 066107

[9] Chan S.H., Donner R.V., Lammer S., “Urban road networks-spatial networks with universal geometric features? A case study on Germany's largest cities”, The European Physical Journal, 84 (2011), 563–77 | DOI

[10] Cheng Y.Y., Lee R.K., Lim E.P., Zhu F., “Measuring centralities for transportation networks beyond structures”, Applications of social media and social network analysis, 2015, 23–39 | DOI | Zbl

[11] Ermolin N.A., Khitraya V.A., Khitryi A.V., Mazalov V.V., Nikitina N.N., “Modeling of the City's Transport Network Using Game-Theoretic Methods on the Example of Petrozavodsk”, Contributions to Game Theory and Management, 15 (2022), 18–31 | DOI | MR

[12] Everett M.G., Borgatti S.P., “The centrality of groups and classes”, The Journal of mathematical sociology, 23:3 (1999) | DOI | MR | Zbl

[13] Freeman L.C., “A set of measures of centrality based on betweenness”, Sociometry, 1, 35–41

[14] Freeman L.C., “Centrality in social networks conceptual clarification”, Social networks, 1:3 (1978), 215–39 | DOI

[15] Fushimi T., Saito K., Ikeda T., Kazama K., “A new group centrality measure for maximizing the connectedness of network under uncertain connectivity”, International Conference on Complex Networks and their Applications, 2018, 3–14

[16] Giscard P.L., Wilson R.C., “Cycle-centrality in economic and biological networks”, International conference on complex networks and their applications, 2017, 14–28

[17] Giscard P.L., Wilson R.C., “A centrality measure for cycles and subgraphs II”, Applied Network Science, 3:1 (2018), 1–5 | DOI

[18] van der Grinten A., Angriman E., Meyerhenke H., “Scaling up network centrality computations – a brief overview”, it-Information Technology, 62:3–4 (2020), 189–204

[19] Hadas Y., Gnecco G., Sanguineti M., “An approach to transportation network analysis via transferable utility games”, Transportation Research Part B: Methodological, 105 (2017), 120–143 | DOI

[20] Henry E., Bonnetain L., Furno A., El Faouzi N.E., Zimeo E., “Spatio-temporal correlations of betweenness centrality and traffic metrics”, 2019 6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), 2019, 1–10

[21] Kazerani A., Winter S., Can betweenness centrality explain traffic flow?, 12th AGILE international conference on geographic information science, 2009, 1–9

[22] Kolaczyk E.D., Chua D.B., Barthélemy M., “Group betweenness and co-betweenness: Inter-related notions of coalition centrality”, Social Networks, 31:3 (2009), 190–203 | DOI

[23] Liu W., Li X., Liu T. and Liu B., “Approximating betweenness centrality to identify key nodes in a weighted urban complex transportation network”, Journal of Advanced Transportation, 2019, 9024745, 1–8

[24] Lujak M., Giordani S., “Centrality measures for evacuation: Finding agile evacuation routes”, Future Generation Computer Systems, 83 (2018), 401–412 | DOI

[25] Luo D., Cats O., van Lint H., Can passenger flow distribution be estimated solely based on network properties in public transport systems?, Transportation, 47 (2020), 2757–2776 | DOI

[26] Mishra S., Welch T.F., Jha M.K., “Performance indicators for public transit connectivity in multi-modal transportation networks”, Transportation Research Part A: Policy and Practice, 46:7 (2012), 1066–1085 | DOI

[27] Nikitina N., Mazalov V., “Network Centralities Based on Non-additive Measures”, Mathematical Optimization. Theory and Operations Research: Recent Trends, MOTOR 2022, CCIS, 1661, eds. Y. Kochetov et al., 2022, 1–12 | MR

[28] Planet dump retrieved from https://planet.osm.org, , OpenStreetMap contributors, 2022 https://www.openstreetmap.org

[29] Puzis R., Altshuler Y., Elovici Y., Bekhor S., Shiftan Y., Pentland A., “Augmented betweenness centrality for environmentally aware traffic monitoring in transportation networks”, Journal of Intelligent Transportation Systems, 17:1 (2013), 91–105 | DOI

[30] Puzis R., Elovici Y., Dolev S., “Fast algorithm for successive computation of group betweenness centrality”, Physical Review, 76:5 (2007), 056709 | MR

[31] Roohi L., Rubinstein B.I., Teague V., “Differentially-private two-party egocentric betweenness centrality”, IEEE INFOCOM 2019 – IEEE Conference on Computer Communications, 2019, 2233–2241

[32] Sarker S., Veremyev A., Boginski V., Singh A., “Critical nodes in river networks”, Scientific reports, 9:1 (2019), 1–11 | DOI | MR

[33] Skibski O., Michalak T.P., Rahwan T., “Axiomatic characterization of game-theoretic centrality”, Journal of Artificial Intelligence Research, 62 (2018), 33–68 | DOI | MR | Zbl

[34] Strano E., Nicosia V., Latora V., Porta S., Barthélemy M., “Elementary processes governing the evolution of road networks”, Scientific reports, 1:2(1) (2012), 1–8 | MR

[35] Tarkowski M.K., Szczepański P.L., Michalak T.P., Harrenstein P., Wooldridge M., “Efficient computation of semivalues for game-theoretic network centrality”, Journal of Artificial Intelligence Research, 63 (2018), 145–189 | DOI | MR | Zbl

[36] Torra V., Narukawa Y., “On network analysis using non-additive integrals: extending the game-theoretic network centrality”, Soft Computing, 23:7 (2019), 2321–2329 | DOI | Zbl

[37] Williams M.J., Musolesi M., “Spatio-temporal networks: reachability, centrality and robustness”, Royal Society open science, 3:6 (2016), 160196 | DOI | MR

[38] Wu F., Yang W., Sun M., Ren J., Lyu F., “Multi-path selection and congestion control for NDN: An online learning approach”, IEEE Transactions on Network and Service Management, 18:2 (2020), 1977–1989 | MR

[39] Wu X., Cao W., Wang J., Zhang Y., Yang W., Liu Y., “A spatial interaction incorporated betweenness centrality measure”, Plos one, 17:5 (2022), e0268203 | DOI

[40] Ye P., Wu B., Fan W., “Modified betweenness-based measure for traffic flow prediction of urban roads”, Transport Research Record, 2563:1 (2016), 144–150 | DOI

[41] Zhou L., Zeng Y., He Y., Jiang Z., Ma J., “Multi-hop based centrality of a path in complex network”, 2017 13th International Conference on Computational Intelligence and Security (CIS), 2017, 292–296

[42] Zhou Y., Kundu T., Goh M. and Sheu J.B., “Multimodal transportation network centrality analysis for Belt and Road Initiative”, Transportation Research Part E: Logistics and Transportation Review, 149 (2021), 102292 | DOI