Article citation information:

¯ochowska, R., Soczówka, P. Analysis of selected transportation network structures based on graph measures. Scientific Journal of Silesian University of Technology. Series Transport. 2018, 98, 223-233. ISSN: 0209-3324. DOI: https://doi.org/10.20858/sjsutst.2018.98.21.

 

 

Renata ¯OCHOWSKA[1], Piotr SOCZÓWKA[2]

 

 

 

ANALYSIS OF SELECTED TRANSPORTATION NETWORK STRUCTURES BASED ON GRAPH MEASURES

 

Summary. The structure of transportation networks has been the subject of analysis for many years, due to the important role that it plays in assessing the efficiency of transportation systems. One of the most common approaches to representing this structure is to use graph theory, in which elements of transportation infrastructure are depicted by a set of vertices and edges. An approach based on graph theory allows us to assess the structure of a transportation network in terms of connectivity, accessibility, density or complexity. In the paper, different transportation network structures are assessed and compared, based on graph measures.

Keywords: transportation network, graph theory, graph and topology measures

 

 

1. INTRODUCTION

 

A transportation network is usually understood as a set of transportation points, with connections between them, in the form of paths or routes, designed for travel by people, cargo shipments and the passage of vehicles [20]. The spatial structure of such a network corresponds to the connections that exist between the elements of transportation infrastructure in the geographical space. This means that elements of the transportation network are also elements of land use in the area in which they are located [5]. The volume of traffic flows, expressed by the number of travelling people, as well as moving vehicles, or by the mass of carried goods in a given unit of time, is one of the measures of transportation network performance.

The efficiency of the entire transportation system in the area under analysis is largely determined by the structure of its transportation network. The denser and more consistent the network, the greater the number of connections between two selected vertices. This has a significant impact on the possibility of reducing traffic congestion by moving traffic onto alternative roads, which in turn means shorter travel time. This explains why the analysis of transportation network structures has been the subject of intensive research for many decades [1,6-9,22,24].

The article analyses the assessment of selected structures of a transportation network based on graph measures. The network models correspond to real transportation systems. The analysis is carried out in terms of the possibility of using different types of graph measures when assessing the propagation of disturbances in the transportation network.

 

 

2. REPRESENTATION OF THE TRANSPORTATION NETWORK STRUCTURE 

 

The physical topology of a network, which is understood as the arrangement of nodes and links in the network, is based on point and linear transportation infrastructure objects. The aim of the study is to define the scope of the representation of the infrastructure’s elements and the connections between them. Therefore, the structure of the network may be both very simplified and particularly complex. Thus, depending on the adopted criteria for the classification of transportation systems, scales and aggregation level, a transportation node may be a single intersection, a bus stop, a railway station, a road junction, an airport, a logistics centre or even a whole city. In turn, the link may be a single traffic lane, a railway track, a communication route or a corridor connecting important transportation nodes. When designing a network model, the proper representation of location, direction and connections is of particular importance. It is also worth noting that the topology of a network model should be as close as possible to the structure of the real network it represents [18].

The structure of the transportation network can be mapped by using various mathematical tools. One of the most commonly and intuitive approaches is to represent the transportation system of the studied area using graph theory [12,25]. Graph methods has been used to map and study the spatial structure of transportation networks since the 1960s [10,13]. In Poland, they have been used, for example, to assess the topological accessibility of the railway network of the West Pomeranian Voivodeship [19], former Poznañ Province [15,16] and Silesia [21].

The main requirement of topological analysis is to represent an existing transportation network as an abstract set of points (nodes or vertices), connected by a set of lines (segments, edges or arcs). In the graph theory approach, attention is primarily centred on the arrangement of connections between nodes, which allows for the use of undirected graphs. Metric and capacity characteristics are also often ignored [2].

Two basic approaches to the representation of a transportation network structure using graph theory are found in the literature [23]:

-          Primal, in which the nodes of the network are represented in the form of vertices, and links in the form of arcs or edges

-          Dual, in which the sections of the network are represented in the form of vertices, and nodes in the form of arcs or edges

 

For the purpose of analysing the values of selected graph measures for various structures of a transportation network, a set of numbers relating to the types of structures has been determined as follows:

 

                                                          (1)

 

where is the number for structure type, and is the number for all structure types under analysis. Therefore, using the primal approach to mapping the structure of the transportation network, the -th structure of the network may be described in the form of a graph:

 

                                              (2)

where is the set of vertices of graph ,is the set of edges of graph . Both the vertices and the edges are sequentially numbered. Therefore, the set  contains subsequent numbers for the vertices of graph , i.e.:

 

                                             (3)

 

where  is the number of a vertex of graph , is the number of the last vertex (in the set of vertex numbers in ascending order) corresponding to the size of the set , and the set  contains subsequent numbers for the edges of graph , i.e.:

 

                                             (4)

 

where is the number for an edge of graph , and is the number for the last edge (in the set of edges numbers in ascending order) corresponding to the size of the set .

The mathematical model of the transportation network should be constructed in such a way as to enable the identification of its elements, the description of its spatial structure and the assignment of specific characteristics to its individual elements [26].

 

 

3. MEASURES OF A TRANSPORTATION NETWORK STRUCTURE 

 

There are many measures that can be used to assess the structure of the transportation network and analyse its efficiency. Some of them take into account spatial features (distance, surface), as well as the level of activity (traffic), while others solely rest on the topological dimension of the network. They may be applied to [18]:

-          The expression of the relationship between values and the network structures they represent

-          The comparison of different transportation networks at a specific point in time

-          The comparison of the evolution of a transportation network at different points in time

 

The representation of the structure of the transportation network in the form of graph enables a set of functions to be assigned, which correspond to the properties (characteristics) of the elements of this structure in relation to each vertex and/or edge of the graph. These characteristics are also used to assess the structure of the transportation network. In order to conduct comparative analyses of the topology of entire networks or their parts, the measures at the network level are particularly important. Among the groups of indices for assessing the structure of a transportation network are graph measures, which are particularly important because of the representation of the network in the form of a graph.

One of the most important characteristics of a transportation network is its level of connectivity, which may be described as the degree of connections in a particular area or a measure of how many components of the transportation network are connected to each other [3,17]. The more connected networks there are, the shorter the travel times and costs. Moreover, connectivity plays an important role in the social and economic development of regions [17]. Three measures, based on graph theory, were initially developed by Kansky [10,11] and can be used to assess the connectivity of a transportation network [4,11,18]: alpha, beta and gamma measures. It is worth noting that all of them are ratios, that is, they represent a relation between distinguishable elements of a network [11,18]. 

The alpha measure  compares the number of cycles in the network represented by the graph  with maximum number of cycles [11,18]. This measure can range from 0 to 1. Values close to 1 indicate a well-connected network; however,  does not usually equal 1. For simple and less connected networks (for example, tree networks), values of  are close to 0.

The alpha measure may be calculated based on the following formula:

 

                          (5)

where is the number of edges in a graph , wherein ; is the number of vertices in a graph , wherein ; and  is the number of isolated subgraphs in a graph . The alpha measure is often expressed as a percentage value, which denotes the percentage of maximum connectivity.

 

The second graph measure, the beta measure , expresses the relation between a certain number of edges and the number of vertices in a graph  [4,18]. It is one of the simplest measures used to evaluate the connectivity of transportation networks [11]. It may be calculated based on the following formula:

 

                                (6)

 

where  is the number of edges in a graph , wherein ; and is the number of vertices in a graph , wherein .

 

Similar to the alpha measure, higher values of the beta index characterize well-connected networks [4,11]. For planar graphs, the maximum value of the beta index is 3, whereas, for non-planar graphs, its values are infinite. All disconnected graphs have values of the beta measure smaller than 1, while a perfect grid network may have values of the beta measure around 2.5. For network planning purposes, values of about 1.4 for the beta measure are acceptable [3].

The third graph measure developed by Kansky, the gamma measure , expresses the relation between an observed number of edges in the network and the maximum possible number of edges [12,19]. Similar to the alpha measure, it ranges from 0 to 1, with 1 denoting a completely connected network and 0 denoting a poor level of connectivity [11]. It is determined as follows:

 

                        (7)

 

where  is the number of edges in a graph , wherein ; and is the number of vertices in a graph , wherein . It is worth noticing that Formula (7) is applicable to planar graphs [11]. Usually, the gamma measure is expressed as percentage values.

 

Different graph-based measures take into consideration the network as a whole. Example of such measures may be the eta measure , which is an average length of a link in a transportation network [4,11]. It may be calculated based on the following formula:

 

                              (8)

 

where is the total length of the graph , i.e., the sum of the length of all edges from the set ; and  is the number of edges in a graph , wherein . The total length  of the graph  is a very important characteristic of the transportation network structure from the point of view of its efficiency. According to [4], the longer the edges in the network, the better it is to ensure the maximum speed of a given link. The total length  is also taken into account in the calculation of the pi measure , which expresses the relationship between the total mileage of a transportation network and its diameter [11,18]. It may be determined based on the following formula:

                                (9)

where  is the total length of the graph , and is the length of a diameter of a graph , i.e., the length of the shortest path between the two most distanced vertices from the set .

 

The pi measure equals 1 for less complicated networks. Greater values are ascribed to more complex transportation networks [11].

Another important measure based on graph theory is the graph density , which is understood as the ratio of the number of its edges to the largest possible number of edges that may be stretched on the vertices of the graph