Graph analysis of underground transport networks

The methodic of city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics were calculated from subways indexes (number of lines, number of stations, length of lines in kilometers, ridership per year) and from...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автори:	Sarycheva, L., Sergieieva, K.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2014
Назва видання:	Искусственный интеллект
Теми:	Интеллектуальные системы планирования, управления, моделирования и принятия решений
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85293
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Graph analysis of underground transport networks / L. Sarycheva, K. Sergieieva // Искусственный интеллект. — 2014. — № 4. — С. 58–70. — Бібліогр.: 14 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85293
record_format	dspace
spelling	irk-123456789-852932015-07-25T03:01:31Z Graph analysis of underground transport networks Sarycheva, L. Sergieieva, K. Интеллектуальные системы планирования, управления, моделирования и принятия решений The methodic of city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics were calculated from subways indexes (number of lines, number of stations, length of lines in kilometers, ridership per year) and from indicators of cities urbanization (area and population). The interrelation between graph (road) structures and weights of their edges, and between π -index describing the shape of the graph and the number of passengers is demonstrated. It is shown on a practical example that the analysis of structure of proposed road network graphs can be useful in determining the sequence of new roads construction. Clustering of underground transport networks based on characteristics of network graph structure was performed for the first time. Запропоновано методику аналізу міських мереж метрополітенів на основі характеристик графів (центральність, зв'язність і форма). Значення характеристик розраховані на основі індексів метрополітенів (кількість ліній, кількість станцій, протяжність ліній в кілометрах, пасажиропотік на рік) і показників урбанізації міст (площа та чисельність населення). Продемонстровано взаємозв'язок між структурою графів транспортних мереж, вагою їх дуг і π -індексом для опису форми графа і кількості пасажирів. На практичному прикладі показано, що аналіз структури представлених графів транспортних мереж може використовуватися для визначення послідовності етапів будівництва нових ліній. Вперше виконано кластеризацію транспортних підземних мереж на основі характеристик структури графа мережі. Предложена методика анализа городских сетей метрополитенов на основе характеристик графов (центральность, связность и форма). Значения характеристик рассчитаны на основе индексов метрополитенов (количество линий, количество станций, протяженность линий в километрах, пассажиропоток в год) и показателей урбанизации городов (площадь и численности населения). Показана взаимосвязь между структурой графов транспортных сетей, весом их дуг и π -индексом для описания формы графа и количества пассажиров. На практическом примере показано, что анализ структуры представленных графов транспортных сетей может использоваться для определения последовательности этапов строительства новых линий. Впервые выполнена кластеризация транспортных подземных сетей на основе характеристик структуры графа сети. 2014 Article Graph analysis of underground transport networks / L. Sarycheva, K. Sergieieva // Искусственный интеллект. — 2014. — № 4. — С. 58–70. — Бібліогр.: 14 назв. — англ. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/85293 519.711:004.8 en Искусственный интеллект Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений
spellingShingle	Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений Sarycheva, L. Sergieieva, K. Graph analysis of underground transport networks Искусственный интеллект
description	The methodic of city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics were calculated from subways indexes (number of lines, number of stations, length of lines in kilometers, ridership per year) and from indicators of cities urbanization (area and population). The interrelation between graph (road) structures and weights of their edges, and between π -index describing the shape of the graph and the number of passengers is demonstrated. It is shown on a practical example that the analysis of structure of proposed road network graphs can be useful in determining the sequence of new roads construction. Clustering of underground transport networks based on characteristics of network graph structure was performed for the first time.
format	Article
author	Sarycheva, L. Sergieieva, K.
author_facet	Sarycheva, L. Sergieieva, K.
author_sort	Sarycheva, L.
title	Graph analysis of underground transport networks
title_short	Graph analysis of underground transport networks
title_full	Graph analysis of underground transport networks
title_fullStr	Graph analysis of underground transport networks
title_full_unstemmed	Graph analysis of underground transport networks
title_sort	graph analysis of underground transport networks
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2014
topic_facet	Интеллектуальные системы планирования, управления, моделирования и принятия решений
url	http://dspace.nbuv.gov.ua/handle/123456789/85293
citation_txt	Graph analysis of underground transport networks / L. Sarycheva, K. Sergieieva // Искусственный интеллект. — 2014. — № 4. — С. 58–70. — Бібліогр.: 14 назв. — англ.
series	Искусственный интеллект
work_keys_str_mv	AT sarycheval graphanalysisofundergroundtransportnetworks AT sergieievak graphanalysisofundergroundtransportnetworks
first_indexed	2025-07-06T12:30:12Z
last_indexed	2025-07-06T12:30:12Z
_version_	1836900693442560000
fulltext	ISSN 1561-5359 «Искусственный интеллект» 2014 № 4 58 3S УДК 519.711:004.8 L. Sarycheva, K. Sergieieva National Mining University Karl Marks ave., 19, 49005, Dnepropetrovsk, Ukraine Graph Analysis of Underground Transport Networks Л.В. Сарычева, Е.Л. Сергеева ГВУЗ «Национальный горный университет» пр. Карла Маркса, 19, 49005, Днепропетровск, Украина Анализ графов транспортных подземных сетей Л.В. Саричева, К.Л. Сергєєва ДВНЗ «Національний гірничий університет» пр. Карла Маркса, 19, 49005, Дніпропетровськ, Україна Аналіз графів транспортних підземних мереж The methodic of city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics were calculated from subways indexes (number of lines, number of stations, length of lines in kilometers, ridership per year) and from indicators of cities urbanization (area and population). The interrelation between graph (road) structures and weights of their edges, and between π -index describing the shape of the graph and the number of passengers is demonstrated. It is shown on a practical example that the analysis of structure of proposed road network graphs can be useful in determining the sequence of new roads construction. Clustering of underground transport networks based on characteristics of network graph structure was performed for the first time. Keywords: graph analysis, transport network, underground, GIS Предложена методика анализа городских сетей метрополитенов на основе характеристик графов (центральность, связность и форма). Значения характеристик рассчитаны на основе индексов метрополитенов (количество линий, количество станций, протяженность линий в километрах, пассажиропоток в год) и показателей урба- низации городов (площадь и численности населения). Показана взаимосвязь между структурой графов транспортных сетей, весом их дуг и π -индексом для описания формы графа и количества пассажиров. На практическом примере показано, что анализ структуры представленных графов транспортных сетей может использоваться для определения последовательности этапов строительства новых линий. Впервые выполнена кластеризация транспортных подземных сетей на основе характеристик структуры графа сети. Ключевые слова: анализ графов, транспортные сети, метрополитен, ГИС Запропоновано методику аналізу міських мереж метрополітенів на основі характеристик графів (центральність, зв'язність і форма). Значення характеристик розраховані на основі індексів метрополітенів (кількість ліній, кількість станцій, протяжність ліній в кілометрах, пасажиропотік на рік) і показників урбанізації міст (площа та чисельність населення). Продемонстровано взаємозв'язок між структурою графів транспортних мереж, вагою їх дуг і π -індексом для опису форми графа і кількості пасажирів. На практичному прикладі показано, що аналіз структури представлених графів транспортних мереж може використовуватися для визначення послідовності етапів будівництва нових ліній. Вперше виконано кластеризацію транспортних підземних мереж на основі характеристик структури графа мережі. Ключові слова: аналіз графів, транспортні мережі, метрополітен, ГІС Introduction Researches on applying graph theory to analyze transportation networks have been carrying out since the 1960-s till the present days. The most famous works were published by David Levinson, Mike Batty, Paul Longley etc. Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 59 3S Analysis of transport networks graphs involves solving problems: − forecasting and evaluating transport network growth [1, 2]; − studying the influence of transport network structure and topology on quantitative indicators of traffic flows [3]; − investigation of dependence of network structure from the size of cities ground transportation and urban structure [4]; − construction of dynamic models of urban systems using GIS technologies based on cellular automata, agent-based modeling and fractal analysis [5, 6, 7]; − investigation relationships between quantitative indicators of transport network structure and its performance, density and urban spatial pattern, and the trips distance for early solution of transport problems etc. The up-to-date researches don’t pay enough attention to network bandwidth analysis depending on the parameters of structure of the network graph. This aspect is investigated in the paper. Basic Definitions Graph ( )E,VG is a pair of two sets – non-empty set of nodes V and an assemblage E of unordered pairs of distinct elements of V set [8]: ( ), ; , 0, .G V E V E v E V V= ≠ ∈ × Pairs of the E assemblage are called as ribs. The number of nodes of a graph G is denoted as n and the number of edges – m ( ) ( )( ) ( ) ( ), : ,n n G m m G n G V m G E= = = = , where ,V E – ,V E cardinal number. Assume that 21 v,v – nodes, ( )21 v,ve = – edge between them. Maximum distance for a given graph G is called as diameter: )v,u(dmax)G(D Gv,u ∈ = . The set of nodes at the same distance g from the node v is called as tier: { }g)u,v(dVu)g,v(D =∈= . The distance matrix ( ) n,...,2,1j,i,d j,i = of the Ggraph is defined as: ( )jij,i v,vdd = . Characteristics of Graph Structure The principle characteristics of graph structure are its centrality, connectivity and shape. Centrality characterizes the positionality of graph nodes. Absolute index iS of the iv node accessibility is the sum of distances from this node to other nodes [9, 10]: ∑= j iji dS . The iv node is called a central if it possesses the smallest absolute value of reachability index i ni1 i SminS ≤≤ = . The König's number jK is also the absolute index of the node i v reachability: ij nj1 i dmaxK ≤≤ = . The central iv node possesses the least König's number: i ni1 j KminK ≤≤ = . L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 60 3S The degree of deviation of the i -th node from the central one: i i i S S =η . The index of hierarchy ( ) iii v,vdy = shows the topological distance from the central node. Nodes with the same values of index of hierarchy form a tier. Centrality is useful for analysis of centers location of local or regional entities, transportation nodes. A measure of centrality on the set of centralities { }iS of graph nodes is integration of: ∑∑ == i i j,i ij S 2 1 d 2 1 S . The * i S index of centrality of the center node defines the graph unipolarity: i ni1 i SminS * ≤≤ = . The variance on a set of central nodes describes the graph centralization: i i ii nSS2)SS(H −=−= ∑ . The territory of the city consists of finite sets of objects: the set of enterprises, buildings, roads, etc. The essence of the territorial community consists in existing mathematical relationships between these objects. The configuration of line-node structure of territory objects placement and relationship is modeled using graphs [11]. For example, structures simulated by graphs in Fig. 1 describe three stages of territory development: initial (a), medium (b), ripe (c) on a qualitative level. Figure 1 – Graphs model for three stages of the territory development: initial (a), medium (b) and ripe (c) Connected graph is modeling the structure of urban subway and road network. The graph is connected if there is a path from any node to any other. The graph connectivity parameters characterize it intenseness with ribs and degree of triangulation. The best known of them are three connectivity parameters – α ,β ,ϕ -indexes: 10; 5n2 knm <α< − +− =α ; (1) 30; n m ≤β≤=β ; (2) 10; )2n(3 m ≤ϕ≤ − =ϕ , (3) where m , n , k are the number of edges, nodes and graph connected components respectively. To calculate the graph shape parameters the matrix ( ) 1n,...,2,1j,n,...,2,1i,M ij −==µ= of ordinal vicinity can be used: { }ithe number of vicinal vertices of the j-th order for the node v ij µ = , а) b) c) Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 61 3S where vicinal nodes of the j -th order for node iv are nodes of the ( )j,ivD tier (neighbors of the 1-st order – adjacent nodes). For example, the sequence neighborhood matrixes for graphs from Fig. 1(a), Fig. 1(b), Fig. 1(c) are represented in Fig. 2.                 111111 011112 001122 000222 001122 011112 111111                 000222 001122 000123 000132 000033 000123 001221                 000133 000133 000133 000006 000133 000133 000133 a) b) c) Figure 2 – Sequence neighborhood matrix for graphs from Fig. 1 If two graphs possess same number of nodes the more compact of them is the one having more zero columns in the M matrix. The graph on Fig.1(c) is more compact than the graphs in Fig.1(a) and Fig.1(b) (2 times and 4/3 times, respectively). The ratio of the graph edges total length P to its diameter D determines the shape of the graph described by π -index: D/P=π . Table 1 present values of the observed parameters for 3 graph model shown in Fig. 1. Table 1 – Parameters of graphs structures shown in Fig. 1. Graph Centrality S1=S7=21 S2=S6=16 S3=S5=13 S4=12 i * =4 К1=К7=6 К2=К6=5 К3=К5=4 К4=3 η1=η7=1,8 η2=η6=1,3 η3=η5=1,0 η4=1 γ1=γ7=3 γ2= γ6=2 γ 3= γ5=1 γ 4=0 S=56 Si=12 H=28 S1=15 S2= S6=13 S3=9, S4=14 S5=10 S7=12 i=3 К1=К2=4 К4=К6=4 К5=К7=3 К2=2 η1=1,7 η2=η6=1,4 η3=1 η4=1,6 η5=1,1 η7=1,3 γ1=γ4=2 γ6=2 γ 2=γ5=1 γ7=1 γ4=0 S=43 Si=9 H=23 S1=S2=9 S3=S5=9 S6=S7=9 S4=6 i=4 К1=К2=2 К3=К5=2 К6=К7=2 К4=1 η1=η2=1,5 η3=η5=1,5 η6=η7=1,5 η4=1,6 γ1=γ2=1 γ3=γ5=1 γ6=γ7=1 γ4=0 S=30 Si=6 H=18 Connectivity (a) α = 0 β = 0,9 ϕ = 0,4 (b) α =0,2 β =1,1 ϕ = 0,5 (c) α =0,7 β =1,7 ϕ = 0,8 Shape (a) Q = 0 π = 1 (b) Q = 2 π = 2 (c) Q = 3 π = 6 For attributed graph with weighted edges the diameter of the graph and the length of its edges can be expressed not only topologically (as the number of edges), but also metrically (through the attributes of edges). (a) (b) (c) L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 62 3S The Examples of Analysis of Subway Graphs Network Characteristics Consider an example demonstrating the usefulness of analysis of the graph structure for spatially referenced objects [10]. Given network of roads is represented as graph in Fig. 3. Each edge of the graph is the road, each node – the station (point) or a node of roads intersection. External road (indicated by arrows) were not take into account because of their secondary importance. Assume that 7 new roads indicated by dashed lines in Fig. 3 were designed. Which of these roads will have the greatest impact on the availability of one point with respect to another within the territory? How will the appearance of each new road impact on the relative availability of individual points within the network? To answer these questions, the parameters of centrality of the original graph (with no new roads) and graphs (a) – (f) in Fig. 3 were calculated. The calculated parameters are presented in Table 2. It is evident from the table that each new road improves communication between settlements (reduces average path length in the network of roads), but their effectiveness varies. (a) (b) (c) (d) (e) (f) – – – - proposed roads Figure 3 – The impact of new roads in the network on the relative availability of settlements (dots highlights items that will benefit from the construction of these roads, the size of dots indicates the degree of winning) Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 63 3S Table 2 – The parameters of graphs modeling road networks Roads network graphs (according to Fig. 3) Paramerets Initial а b c d e f The average length of the path in the network 242 220 238 216 217 221 174 Si 190 178 190 168 156 164 122 S 4359 3961 4283 3895 3920 3982 3125 The place- preference (according to S) 9 4 6 2 3 5 1 H 1688 1336 1536 1574 2068 1896 1736 % of decrease of the average path length in the network 0 9,1 1,7 10,6 10,0 8,6 28,3 Nodes vi beneficial to the new road with the degree ∆i - ∆10=70 ∆11=58 ∆5=52 ∆4=46 ∆13=46 ∆36=33 ∆37=33 ∆35=10 ∆37=105 ∆12=104 ∆36=74 ∆13=69 ∆11=52 ∆21=80 ∆31=65 ∆20=43 ∆18=40 ∆19=40 ∆21=74 ∆20=36 ∆19=34 ∆18=34 ∆37=146 ∆12=141 ∆36=126 ∆21=122 ∆31=106 The most effective road is (f) as it reduces the average length of a path in the network on 10.6%, the least effective – (b). Simultaneous creation of new roads (a) - (f), shown by the graph in Fig. 3 (f), reduces the average path length of the network on 28.3%. The benefit taken for settlements from building the new roads is determined by changes in the average path length for each locality. For the (a) road construction the most interested are the 10-th, 11-th and 5-th settlements, in road (b) - the 36-th, 37-th, in road (c) – the 37-th, 12-th, 36-th, in road (d) – the 21-th, 31-th, 20-th, for the (e) road – the 21-th, 20-th settlements. The costs given by settlements for building of new roads can be distributed in proportion to the winning, defined by parameter i∆ ( igraph initialii S - node S=∆ ) in Table 2. Calculation of Subway Indexes In the other example the subway network graphs structure for some European cities is analyzed (Table 3). All subway schemes and cities subway statistics are available through [12, 13] (Table 4, 5, 6). The number of stations 4X includes transfer stations taken from [14]. The number of edges and nodes m , n of subway network graphs are calculated by the scheme taking into account the fact that several transfer stations (from various subway lines) create one node of the graph. Correlation coefficients for graph connectivity characteristics (α ,β ,π indexes – аlfa, beta, iP , PID) and input indexes 621 X,...,X,X is the highest for the π -indexes and the lowest for ϕ -indexes – fi. This means that the π - indices are informative characteristic for analysis of subways networks graphs (Table 7). The Paris, Moscow, Prague, Kiev and Saint Petersburg are characterized by the largest values of passenger-to-kilometers (kilometers) ratio, which is especially evident from fig.4(b) in auxiliary scale. Only Prague and Kiev have in common the largest values of passenger / population ratio (this fact may be caused by the large number of tourists) (fig.4(a)). L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 64 3S Table 3 – Subway schemes of European cities Paris Madrid Moscow London Berlin Athens Budapest Prague Kiev Kharkov Minsk Saint Petersburg Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 65 3S Table 4 – Input data for subways Length P, km Population (million) Ridership per year (million) Number of stations Urban area, km 2 Number of lines № City (subway location) X1 X2 X3 X4 X5 X6 1 Athens 78,3 3,50 407 64 583 3 2 Berlin 146,11 3,95 507 196 1347 9 3 Budapest 32,3 1,73 171 42 894 3 4 Warsaw 21,7 1,71 139 21 544 1 5 Hamburg 112,9 1,79 209 108 712 4 6 Dnepropetrovsk 7,1 1,00 8 6 324 1 7 Kiev 65,9 2,81 527 51 544 3 8 London 470 9,40 1171 381 1623 11 9 Madrid 224,5 5,90 602 288 1321 13 10 Minsk 35,4 1,85 281 28 324 2 11 Moscow 313,1 15,50 2464 188 4403 12 12 Paris 217,3 10,36 1524 383 2845 16 13 Prague 59,4 1,27 589 57 285 3 14 Saint Petersburg 113 4,84 784 67 1191 5 15 Kharkov 39,3 1,45 239 29 466 3 Table 5 – Subway characteristics Edges weights Node weights Frequency of travels Areal weights Areal density of lines Linear density of stations Areal density of stations № City (subway location) Х3/Х1 Х3/Х4 Х3/Х2 Х3/Х5*10 3 Х5/Х1 Х1/Х4 Х5/Х4 1 Athens 5,2 6,4 116,3 698,1 7,4 1,2 9,1 2 Berlin 3,5 2,6 128,4 376,6 9,2 0,7 6,9 3 Budapest 5,3 4,1 98,6 190,7 27,7 0,8 21,3 4 Warsaw 6,4 6,6 81,4 255,9 25,1 1,0 25,9 5 Hamburg 1,9 1,9 116,8 293,5 6,3 1,0 6,6 6 Dnepropetrovsk 1,1 1,4 8,1 25,0 45,6 1,2 54,0 7 Kiev 8,0 10,3 187,8 968,2 8,3 1,3 10,7 8 London 2,5 3,1 124,6 721,5 3,5 1,2 4,3 9 Madrid 2,7 2,1 101,9 455,3 5,9 0,8 4,6 10 Minsk 7,9 10,0 152,3 868,2 9,2 1,3 11,6 11 Moscow 7,9 13,1 159,0 559,6 14,1 1,7 23,4 12 Paris 7,0 4,0 147,2 535,7 13,1 0,6 7,4 13 Prague 9,9 10,3 465,8 2067,4 4,8 1,0 5,0 14 Saint Petersburg 6,9 11,7 162,0 658,2 10,5 1,7 17,8 15 Kharkov 6,1 8,3 165,0 513,5 11,9 1,4 16,1 L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 66 3S Table 6 – Subway graphs characteristics № City (subway location) m n P D DM (D, km) alfa beta fi Pi (P/D) PID (X1/DM) 1 Athens 61 60 61 23 35,0 0,02 1,02 0,35 2,65 2,24 2 Berlin 187 177 187 39 31,8 0,03 1,06 0,36 4,79 4,60 3 Budapest 39 40 39 19 17,3 0,00 0,98 0,34 2,05 1,87 4 Warsaw 20 21 20 20 21,7 0,00 0,95 0,35 1,00 1,00 5 Hamburg 104 97 104 45 55,8 0,04 1,07 0,36 2,31 2,02 6 Dnepropetrovsk 5 6 5 5 7,1 0,00 0,83 0,42 1,00 1,00 7 Kiev 48 48 48 17 23,9 0,01 1,00 0,35 2,82 2,76 8 London 370 316 370 59 74,0 0,09 1,17 0,39 6,27 6,35 9 Madrid 276 237 276 32 40,6 0,09 1,16 0,39 8,63 5,53 10 Minsk 26 27 26 13 18,1 0,00 0,96 0,35 2,00 1,96 11 Moscow 176 152 176 24 45,1 0,08 1,16 0,39 7,33 6,94 12 Paris 367 307 367 37 24,3 0,10 1,20 0,40 9,92 8,94 13 Prague 54 54 54 23 25,6 0,01 1,00 0,35 2,35 2,32 14 Saint Petersburg 62 59 62 18 30,1 0,04 1,05 0,36 3,44 3,75 15 Kharkov 26 26 26 12 17,3 0,02 1,00 0,36 2,17 2,27 Table 7 – Correlation coefficients for subway graphs characteristics X1 X2 X3 X4 X5 X6 alfa beta fi Pi PID X1 1 X2 0,8 1 X3 0,7 1,0 1 X4 0,8 0,8 0,6 1 X5 0,7 1,0 0,9 0,7 1 X6 0,8 0,8 0,8 1,0 0,8 1 alfa 0,9 0,8 0,8 0,9 0,8 0,9 1 beta 0,8 0,8 0,7 0,9 0,7 0,9 0,9 1 fi 0,5 0,5 0,4 0,6 0,5 0,6 0,6 0,3 1 Pi 0,8 0,8 0,8 1,0 0,8 1,0 0,9 0,9 0,6 1 PID 0,8 0,9 0,8 0,9 0,8 1,0 0,9 0,9 0,5 1,0 1 Does the ridership per year depend on parameters of the graph? According to Fig. 5, the iP parameter of the Paris and Madrid subway network graphs allows to suggest about the possibility to increase ridership in these cities in comparison with the observed situation. Ridership per year in Moscow, Saint Petersburg and Prague are optimal with respect to iP parameter. At the same time the difference (Fig. 6) of D P Pi = (calculated from the graph) and DM X PID 1 = (calculated from the length of subway lines in km) parameters is the largest for Madrid and Paris. Paris and Madrid subway networks may have the largest passenger traffic (larger than in Moscow). If we compare the subway networks to indicate how the total length of subway lines ( 1 X ) matches to π -index (Fig. 7), we will conclude that the London network is the longest and possesses the lower π -index value than the Paris network (whose length is two times shorter). Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 67 3S 0 500 1000 1500 2000 2500 3000 M o s c o w P a r i s Lo n don S a i n t P e ter s b u r g M a dr id P r ag u e K i e v B e r l i n A t h e n s M i n s k K h a r k o v H a m b u rg B ud a pes t W a rs aw D ne pro pet r ovs k R id e rs h ip p e r y e a r (m il li o n ), Х 3 0 2 4 6 8 10 12 14 16 18 P o p u la ti o n ( m il li o n ), Х 2 X3 X2 a) 0 500 1000 1500 2000 2500 3000 M o s c o w P a r i s Lo n d o n S a i n t P e t e rs bu rg M a d r i d P r ag ue K i e v B e r lin A th e n s M ins k K ha rk o v H a mb u r g B u d a p e s t W ar s a w D n e p r op e t r o v s k R id e rs h ip p e r y e a r (m il li o n ), Х 3 0 50 100 150 200 250 300 350 400 450 500 L e n g th ( k m ), X 1 X3 X1 b) Figure 4 – Plots for subway characteristics of European cities: a) ridership per year (millions) and population (millions); b) ridership per year (millions) and length (km) 0 500 1000 1500 2000 2500 3000 M o s co w P a r i s Lo nd o n S a i n t P e t e r s b u r g M ad rid P r ag ue K i e v B e r l i n A t h en s M in s k K ha rko v H am bu r g B u d a p e s t W ars aw D nep r op e tro vsk R id e rs h ip p e r y e a r (m il li o n ), X 3 0 2 4 6 8 10 12 P i X3 Pi Figure 5 – Plots of ridership and π -index values L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 68 3S -1 0 1 1 2 2 3 3 M o s c o w P a r i s L o n d o n Sa in t P ete rs b u r g M a d r i d P r a g u e Ki e v Be rli n A t h e n s M in s k K h a r k o v H a mb ur g B u d a p e s t W a rs a w D n e p r o p e t ro v s k P i - P ID Figure 6 – Differences of iP and PID indexes 0 50 100 150 200 250 300 350 400 450 500 L o n d o n M o s c o w M ad ri d P a r i s B er lin S a i n t P e t e r s b u r g H a m b u r g A th ens K ie v P r ag ue K h a r k o v M in s k B u d a p e s t W ar s a w D n epr op e t r o v s k L e n g th P , k m , X 1 0 2 4 6 8 10 12 P i X1 Pi Figure 7 – Plots of Length P (km) and π -index values Clustering of examined networks based on graph characteristics (α ,β ,π – indexes) into K clusters ( 4,3,2K = ) using the k -means method highlights the next clusters (Table 8). Table 8 – Clustering of subway networks based on graph characteristics Clustering on the basis of α, β, π – indexes Clustering on the basis of Х1, Х2, Х3, Х4, Х5 characteristics City (subway location) K=2 K=3 K=4 K=2 K=3 K=4 Athens 2 2 2 2 3 2 Berlin 2 2 4 2 3 3 Budapest 2 2 2 2 2 2 Warsaw 2 3 3 2 2 2 Hamburg 2 2 2 2 2 2 Dnepropetrovsk 2 3 3 2 2 2 Kiev 2 2 2 2 2 2 London 1 1 1 1 1 1 Madrid 1 1 1 2 3 3 Minsk 2 2 2 2 2 2 Moscow 1 1 1 1 1 4 Paris 1 1 1 1 1 1 Prague 2 2 2 2 2 2 Saint Petersburg 2 2 4 2 3 2 Kharkov 2 2 2 2 2 2 Graph Analysis of Underground Transport Networks «Штучний інтелект» 2014 № 4 69 3S The peculiarities of obtained clusters: − (London, Madrid, Moscow, Paris) are characterized by the highest values of the α ,β ,π parameters; − for (Berlin, Saint Petersburg) the values of parameters are above average; − for (Athens, Budapest, Hamburg, Kiev, Minsk, Prague, Kharkov) the values of α ,β ,π parameters are close to average; − (Warsaw, Dnepropetrovsk) are characterized by the lowest values of α ,β ,π parameters. Cities clustering on the basis of input characteristics ( 5421 X,X,X,X ) does not include Madrid, Moscow or Warsaw, Dnepropetrovsk into the same cluster. So the structure of cluster of subway network graphs based on α ,β ,π indexes is not the same as the structure of clusters based on input data 54321 X,X,X,X,X . Conclusions The methodic for city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics are calculated from values of subways indexes (number of lines, number of stations, length in kilometers, ridership per year) and from indicators of cities urbanization (area and population). A relationship between graphs (roads) structure and weights of their edges, between π -index describing the shape of the graph and the number of passengers is demonstrated. It is shown on a practical example that the analysis of structure of proposed road network graphs can be useful in determining the sequence of new roads construction. Clustering of underground transport networks based on characteristics of network graph structure was performed for the first time. References 1. Levinson D.M. Planning for Place and Plexus: Metropolitan Land Use and Transport / D.M. Levinson, K.J. Krizek // Routledge, ISBN-13: 978-0415774918. – 2008. – 334 p. 2. Levinson D. Forecasting and Evaluating Network Growth / D. Levinson, X. Feng, M.O. Norah // Networks and Spatial Economics. – 12(2). – 2012. – p. 239-262. 3. Pavithra P. Network Structure and Spatial Separation / P. Pavithra, H. Hochmair, D. Levinson // Environment and Planning: Planning and Design. – 39(1). – 2012. – P. 137-154. 4. Levinson D. Network Structure and City Size / D. Levinson // 2012 http://nexus.umn.edu/Papers/NetworkStructureAndCitySize.pdf 5. Batty M. Modeling urban dynamics through GIS-based cellular automata /M. Batty, Y. Xie, Z. Sun // Computers, Environment and Urban Systems. – 23. – 1999. – p. 205-233. 6. Batty M. Cities and Complexity: Understanding Cities with Cellular Automata, Agent-Based Models, and Fractals / M. Batty // The MIT Press, ISBN: 978-0-262-02583-6. – 2007. – 565 p. 7. Jin Y. Applied Urban Modeling: New Types of Spatial Data Provide a Catalyst for New Models / Y. Jin, M. Batty // Transactions in GIS. – 17(5). – 2013. – p. 641-644. 8. Берж К. Теория графов и ее применения / К. Берж. – M.: Госиноиздат, 1962. – 319 с. 9. Оре О. Теория графов / О. Оре. – M.: Наука, 1980. – 336 с. 10. Хаггет П. География: синтез современных знаний / П. ХаггетZinatne. – M.: Прогресс, 1979. – 684 с. 11. Сарычева Л.В. Компьютерный эколого-социально-экономический мониторинг регионов. Математическое обеспечение.НГУ / Л.В. Сарычева. – Днепропетровск: НГУ, 2003. – 222 с. 12. Metro systems by annual passenger rides. Wikipedia, the free encyclopedia, 2013 http://en.wikipedia.org/wiki/Metro_systems_by_annual_passenger_rides 13. Demographia World Urban Areas (World Agglomerations): 9th Annual Edition (March 2013). http://www.demographia.com/db-worldua.pdf 14. Europe. UrbanRail.net, 2013. http://www.urbanrail.net/eu/euromet.htm L. Sarycheva, K. Sergieieva «Искусственный интеллект» 2014 № 4 70 3S RESUME L. Sarycheva, K. Sergieieva Graph Analysis of Underground Transport Networks Background: Researches on applying graph theory to analyze transportation networks have been carrying out since the 1960-s till the present days. The most famous works were published by David Levinson, Mike Batty, Paul Longley etc. Analysis of transport networks graphs involves solving problems: forecasting and evaluating transport network growth; studying the influence of transport network structure and topology on quantitative indicators of traffic flows; investigation of dependence of network structure from the size of cities ground transportation and urban structure; construction of dynamic models of urban systems using GIS technologies based on cellular automata, agent-based modeling and fractal analysis; investigation relationships between quantitative indicators of transport network structure and its performance, density and urban spatial pattern, and the trips distance for early solution of transport problems etc. The up-to-date researches don’t pay enough attention to network bandwidth analysis depending on the parameters of structure of the network graph. This aspect is investigated in the paper. Materials and methods: The subway network graphs structure for some European cities is analyzed using the methods of graph theory and clustering. The number of edges and nodes of subway network graphs were calculated by the scheme taking into account the fact that several transfer stations (from various subway lines) create one node of the graph. All subway schemes and cities subway statistics are available through Internet. Results: It is observer that the ridership per year depends on parameters of the graph. In Paris and Madrid subway network graphs structure indexes allow to suggest about the possibility to increase ridership in these cities in comparison with the observed situation. Ridership per year in Moscow, Saint Petersburg and Prague are optimal. At the same time Paris and Madrid subway networks may have the largest passenger traffic (larger than in Moscow). Clustering of examined networks based on graph characteristics) into clusters highlights the next clusters: London, Madrid, Moscow, Paris are characterized by the highest values of the graph connectivity parameters; for Berlin, Saint Petersburg the values of parameters are above average; for Athens, Budapest, Hamburg, Kiev, Minsk, Prague, Kharkov the values of graph connectivity parameters are close to average; Warsaw, Dnepropetrovsk are characterized by the lowest values of parameters. The structure of cluster of subway network graphs based on indexes is not the same as the structure of clusters based on input data. Conclusion: The methodic for city subway networks analysis on the basis of graph characteristics (centrality, connectivity and shape) is proposed. The subways characteristics are calculated from values of subways indexes (number of lines, number of stations, length in kilometers, ridership per year) and from indicators of cities urbanization (area and population). The relationship between graphs (roads) structure and weights of their edges, between π -index describing the shape of the graph and the number of passengers is demonstrated. It is shown on a practical example that the analysis of structure of proposed road network graphs can be useful in determining the sequence of new roads construction. Clustering of underground transport networks based on characteristics of network graph structure was performed for the first time. The article entered release 16.04.2014.

Graph analysis of underground transport networks

Репозитарії

Схожі ресурси