A comparative analysis of underground and bus transit networks through graph theory

Abstract

The aim of this paper is to study the topographical features of a transportation infrastructure through graph theory. First, we construct a planar, connected, and simple graph for each considered infrastructure; then, we compute some normalized indices associated to the graph, namely largest eigenvalue, gap, a Betti number, and codimension. The set of indices proposed in this paper is new for this application. These indices are computed from either the adjacency matrix or the edge ideal of the graph, and so they depend on the overall topology of the graph itself; furthermore, since the normalized indices are scale-free, they allow us a more effective comparison between different transportation infrastructures. Two scenarios are considered in order to understand advantages and limits of the proposed approach: the first scenario concerns a set of underground networks of certain large cities in the world, whereas the second one concerns a set of bus transit networks of several medium-sized cities in Italy. Indices calculated for both scenarios show two types of results. First, they show that the proposed indices are able to estimate the different topologies of the considered networks: networks with the same number of vertices and of edges but not with the same graph have different indices. Second, they show that the values of the indices in the two scenarios not only belong to the same curve separately but fit well also into the same curve: the transportation networks, no matter whether underground or bus transit, seem to be controlled by similar mechanisms.

Keywords

Transportation networks graph theory indices associated to graphs

Introduction

Nowadays, it is standard practice to represent transportation networks as graphs. In fact, such representation of networks allows researchers to highlight the wanted features of the network among the many ones. When graphs represent transportation networks, nodes and links of the network usually become vertices and edges of the associated graph. The degree of detail in this representation is somewhat subjective because it depends on the scope of investigation.

In addition, as in literature many different indices have been associated to a graph, researchers can get a better and more comprehensive understanding of the features of the transportation network from the analysis of values of some indices associated to the graph. When the chosen indices are normalized, even the comparison of different networks becomes easier. Hence, the representation of transportation infrastructures with graphs, and the following computation of some associated indices, should aim at understanding the different behaviors of networks. Besides, the comparison of a new designed network with working ones could help planners to get a network that fully satisfies transportation needs. In this sense, graph indices can integrate planning factors such as demand, demography, geography, demand assignment, and costs.

In the present paper, which is mainly applicative and not theoretic or algorithmic, we want to investigate properties of underground and bus (and sometimes tramway) transit transportation networks that depend on the way a line crosses all the other ones. Then, we transform networks into undirected, planar, simple graphs by coupling a node to either a terminal stop or a transfer one (for us, a stop is either an underground station or a bus stop). With transfer stop, we mean a stop connected to at least three other stops. This choice affects the analysis related to land and service accessibility but not to the functional properties of the network. In the “The underground and bus transit graphs” section, we motivate the reason why we consider only undirected, planar, and simple graphs, and some consequences of our choice. Then, for each graph, we compute four indices, namely the largest eigenvalue of the graph, the gap, difference between the largest and the second largest eigenvalues, the codimension (codim, for brief), and the Betti number $b_{21}$ . While the first two indices are computed from the adjacency matrix of the graph, the last two are computed from the edge ideal of the graph. Finally, we normalize them all with respect to suitable functions depending on the number of vertices and edges, so as to get scale-free indices.

The analysis of the four computed indices has two main purposes. The first objective is to understand to what extent the considered indices are suitable to analyze transportation networks. To understand this, we construct a new dataset consisting of 33 graphs associated to bus transit networks of medium-sized Italian cities and we compute the values the indices take. Then, we compare those values with the ones in the underground network dataset by Derrible and Kennedy, computed in Mussone and Notari (2017). For the sake of completeness, we report the values in both datasets. We stress that, while the underground dataset includes cities from five major world areas, the new dataset involves cities all lying in a geographically small area compared to the worldwide one. Moreover, the Italian cities date back to at least the Middle-Ages, and so their transportation networks, though redesigned in the last decades, had to be integrated with a settled urban network. Hence, there is no reason to believe a priori that the indices are equally suitable for both datasets.

Once we have clear evidence that the chosen scale-free indices are suitable to analyze transportation networks, our second objective is to merge the two datasets to get a more robust one, suitable for further investigation on transportation networks. To obtain this, we plot the indices on the same plane and we check that they complete each other, that is to say, the same curve fits both the datasets. We have to underline that those indices capture certain relationships between vertices and edges of a graph but probably not all the existing ones; to clarify that point, one has to push forward the present research.

At last, among the results of our research, we emphasize that no matter whether underground or bus transit, these networks present an increasing structure depending on similar principles, since we can think of the different sizes of the analyzed networks as the evolution over time of a city, according to Alexander (1965).

The paper has five other sections: The next section presents a brief literature review; the “The indices” section lists the indices proposed for the analysis; the “The underground and bus transit graphs” section describes the datasets used for the application; the “Results” section shows and discusses the results of the proposed indices and a comparison between underground transportation networks and bus transit ones. Finally, in the “Conclusions” section, we summarize the conclusions.

Literature review and paper aims

The study of transportation infrastructures via the computation of indices from the associated graphs began with the seminal papers by Garrison and Marble (1962, 1964). Those authors introduced three indices depending only on the number of vertices and edges of the graphs associated to networks: circuit α, degree of connectivity γ, and complexity β. Since then, such an approach has become very common, and many other indices have been proposed and discussed by applying them to various datasets.

Among many others, we quote the papers by Derrible and Kennedy (2010a, 2010b, 2012), also because we re-analyzed their dataset, consisting of graphs associated to underground networks, in Mussone and Notari (2017). In their papers, Derrible and Kennedy consider 33 urban rapid rail transit networks of varying sizes, whether at grade, underground, or elevated, currently working in five major world areas (North and Latin America, Europe, Africa, and Asia). They transform the networks into graphs by coupling a node to each transfer station, where transfer station is understood to be either a station connected to at least three other stations, or a terminal one. We adopt the same procedure to construct a graph from a transportation network. The indices considered by Derrible and Kennedy are the number of vertices; the number of edges; the network diameter, i.e. the total number of edges linking the two furthest vertices using the shortest path; and the complexity β and the degree of connectivity γ, both by Garrison and Marble (1962). They also consider indicators depending on physical characteristics of the network, such as edge lengths. A further development of this work can be found in Wanga et al. (2017).

For completeness, we stress that, in Mussone and Notari (2017), more indices were considered: in addition to the four ones considered in this paper, we took into account the number of vertices, edges, the indices $α, β, γ$ by Garrison and Marble (1962), the degree of the graph associated to the edge ideal of the graph itself, and the further Betti number $b_{22}$ .

Gattuso and Miriello (2005) face the problem of a topological and geographical evaluation of metro networks through a set of indicators, at graph and geographical levels. At graph level they use, other than the ones by Garrison and Marble (1962):

the local degree, i.e. the number of concurrent links on the generic node;

the number of destinations directly connected by i nodes;

the number of nodes; generally it does not correspond to the number of network stations (two or three different line stations, placed at the same point, are represented by a unique network node);

the number of links (a link covered by several lines is counted only once);

the number of cycles.

A list of parameters at geographical level is also proposed. Actually, this study is notable for the development of two indicators at geographical level: node’s range of influence (to differentiate the attractiveness of a node) and network covering (circular surfaces defined by the node’s range of influence that can be placed one upon another).

Gastner and Newman (2006) find some clear patterns that imply a connection between network structure and geography by analyzing empirical data and overcoming past limitations on computer resources. Blumenfeld-Lieberthal (2009) analyzes the topology of transportation networks within different systems of cities using their characteristics as indicator of economic activity between them.

Xie and Levinson (2007) propose to calculate three parameters, namely heterogeneity, connection pattern, and continuity, to measure structural characteristics of road networks. Heterogeneity is derived from the probability p_k that a vertex is connected to other k vertices and it is proportional to $1 / k^{a}$ , where k is the degree of a vertex and $a$ is the coefficient to be calibrated. This probability distribution is called power law degree and networks with this property are called scale-free. Connection pattern uses Garrison and Marble’s (1962) definition but it mainly focuses on comparing the total length of roads belonging to a ring or circuit to the total length of roads. Continuity is based on a definition of edge hierarchy which again implies a certain quantification of a network property. On the same topic, it is particularly interesting the paper by Barabasi and Albert (1999) who study how networks can grow but without the constraint of planarity.

Ducruet and Lugo (2013) propose a discussion about structure and dynamics in transportation networks whose static dimension is analyzed with regard to topology, geometry, morphology, and spatial structure from a global and local point of view, according to the required application (e.g. looking for interconnectivity or vulnerability, respectively). Kurant and Thiran (2006) extract the topology of mass transportation networks from their timetables. Many other papers focus on dynamic features (mainly the growth) of transportation networks (see, e.g. Xie and Levinson, 2009a, 2009b), so many and so specialized that this topic could deserve a dissertation apart.

In Estrada (2012) and Estrada et al. (2012), the authors study how much information is contained in the communicability distance matrix $G$ and in the communicability distance index ϒ(G), first designed for chemical graph theory, when graphs come from other fields. The communicability distance matrix and index provide a way to measure the propagation of a perturbation at a node to other nodes on the graph (i.e. whether the perturbation remains local or does not), and so they are particularly useful in exploring the so-called locality or its absence in networks. Other papers to be included are those by Barthelemy (2011) and Roth et al. (2012) that mainly focused on characterizing and understanding the structure and the temporal evolution of spatial networks.

Finally, we quote Alexander (1965), as the conclusions in that paper have been recently recovered by Derrible (2016). In Alexander (1965), the author argues that when a city grows organically, its parts are highly interconnected. As we consider urban transportation networks, we expect the associated graphs to be so complex that they merit a detailed analysis.

The indices

In this section, we introduce the indices we use to analyze graphs. To allow for an easy comparison between indices computed for graphs with a different number of vertices or edges, we normalize indices with respect to some maximizing functions, empirically computed in the class of undirected, planar, connected, and simple graphs. As in Section 2 of Mussone and Notari (2017), we divide the indices into two classes, according to the techniques needed to compute them: linear algebraic and algebraic indices. The linear algebraic indices are computed from the adjacency matrix of graphs via linear algebra, whereas the algebraic indices are computed from the edge ideal of the graph via the algebra of polynomial rings. All indices, then, depend on the topology of the graph itself.

Let $G$ be an undirected, simple, planar, connected graph with $v$ vertices and $e$ edges. It may be worth noting that for such a graph the number of edges ranges within [ $v - 1, 3 v - 6]$ . Let $A (G)$ be the adjacency matrix of the graph. Since $G$ is undirected, the matrix $A (G)$ is symmetric and real-valued. So, its eigenvalues are real and they are $v$ if counted according to multiplicity. We increasingly order the eigenvalues as $λ_{1} \leq λ_{2} \leq \dots \leq λ_{v}$ . The eigenvalues do not change if we re-label the vertices of $G$ , and so they are associated to the graph, and not to its adjacency matrix. The indices are the largest eigenvalue $λ_{v}$ and the gap $g = λ_{v} - λ_{v - 1} .$ Frequently, eigenvalues and related functions are used to describe graphs, because it is easy to compute them. However, their meaning is not very clear from a graph-theoretical point of view.

Now, we describe the algebraic indices. An edge is a couple of vertices, the endpoints of the edge. We say that the endpoints of the edge meet the edge itself. The codimension of a graph is the least number of vertices needed to meet all the edges. Of course, if we take all the vertices, they meet all the edges. However, in general, a proper subset of vertices is enough to meet all the edges, and so the codimension is smaller than $v$ . We stress that in a graph $G$ there can be distinct subsets containing exactly $codim (G)$ vertices that meet all the edges. The degree 1 algebraic Betti number is related to the degrees of the vertices and to the number of independent triangles contained in the graph. A triangle is a complete graph with three vertices, and so it has three edges, too, each couple of vertices being an edge. Three triangles are independent if their union is not a graph with four vertices and six edges, that is to say, a complete graph with four vertices.

The whole set of indices is the following (“Linear algebraic indexes” section).

Linear algebraic indexes

λ_v

$λ_{v}$ .It is the largest eigenvalue of $G$ .

Gap g

g = λ_{v} - λ_{v - 1}

(1)

It is the difference between the largest eigenvalue and the second largest one of $G$ , and is called gap.

Normalized largest eigenvalue

\frac{λ_{v}}{Λ (v, e)}

(2)

It is the normalized largest eigenvalue of $G$ , where $Λ (v, e)$ is the largest eigenvalue of the graph $L (v, e) .$ The graph $L (v, e)$ over the vertices $1, 2, \dots, v$ is constructed as follows. There is an edge from 1 to every other vertex, and from 3 to 3. Then, there is an edge from 2 to 4, and from 3 to 4. We go on by connecting first 2 to 5, and then 4 to 5, and so on, until we get a graph with $e$ edges. The largest eigenvalue $Λ (v, e)$ of $L (v, e)$ is the maximum among the largest eigenvalues of undirected, planar, and connected graphs with $v$ vertices and $e$ edges. As we do not have a closed formula for $Λ (v, e),$ we give the adjacency matrix of $L (v, e)$ and compute its eigenvalues from that. The adjacency matrix is the following.

Let $v, e$ be integers such that $v - 1 \leq e \leq 3 v - 6.$ Let $M$ be the $v \times v$ matrix whose elements are

M_{ij} = {\begin{array}{l} 1 & if (i, j) \in B_{ve} \\ 0 & otherwise \end{array}

(3)

where

if $e = v - 1,$ then

B_{ve} = {(1, j) | j = 2, \dots, v}; B_{ve} = {(1, j) | j = 2, \dots, v} if e = v + 2 q, q \geq 0, then

B_{ve} = {(1, i), (2, j), (2 + h, 3 + h) | i = 2, \dots, v; j = 3, \dots, 3 + q; h = 0, \dots, q}

e = v - 1 + 2 q, q \geq 1,

then

B_{ve} = {(1, i), (2, j), (1 + h, 2 + h) | i = 2, \dots, v; j = 3, \dots, 3 + q; h = 1, \dots, q}

The adjacency matrix of $L (v, e)$ is defined as $A (L (v, e)) = M + M^{T} .$

Normalized gap of G

\frac{g}{Γ (v, e)}

(4)

It is the normalized gap of $G$ , where $Γ (v, e)$ is the gap of the graph $M (v, e),$ whose vertices are $1, 2, \dots, v,$ that is constructed as follows. There is an edge from 1 to every other vertex, with two exceptions if $e = 2 v - 4$ or $e = 3 v - 6$ . Then, we connect 2 to $j \neq v$ , and finally we construct a path containing the vertices 3, 4, and so on. If $e = 2 v - 4,$ there is no edge between 1 and 2. Finally, if $e = 3 v - 6,$ there is no edge between 1 and 2, but $3, 4, \dots, v$ are a cycle. The gap $Γ (v, e)$ of $M (v, e)$ is the maximum among undirected, planar, and connected graphs with $v$ vertices and $e$ edges. As we have no closed formula for $Γ (v, e),$ we give the adjacency matrix of $M (v, e)$ to compute it. The adjacency matrix for $v \geq 6$ is as follows.

Let $v, e$ be integers with $v \geq 6$ and $v - 1 \leq e \leq 3 v - 6.$ Let $M$ be a $v \times v$ matrix whose elements are

M_{ij} = {\begin{array}{l} 1 & if (i, j) \in B_{ve} \\ 0 & otherwise \end{array}

(5)

where

if $e = v - 1,$ then $B_{ve} = {(1, 2), \dots, (1, v)};$ $B_{ve} = {(1, 2), \dots, (1, v)};$ if $v \leq e \leq 2 v - 5,$ then $B_{ve} = {(1, 2), \dots, (1, v), (2, 3), \dots, (2, e - v + 3)};$ $B_{ve} = {(1, 2), \dots, (1, v), (2, 3), \dots, (2, e - v + 3)};$ if $e = 2 v - 4,$ then $B_{ve} = {(i, 3), \dots, (i, v) | i = 1, 2};$ $B_{ve} = {(i, 3), \dots, (i, v) | i = 1, 2};$ if $e = 2 v - 3,$ then $B_{ve} = {(1, 2), \dots, (1, v), (2, 3), \dots, (2, v)};$

if $2 v - 2 \leq e \leq 3 v - 8,$ then

B_{ve} = {(1, 2), \dots, (1, v), (2, 3), \dots, (2, v - 1), (3, 4), (4, 5), \dots, (e - 2 v + 6, e - 2 v + 7)}

if $e = 3 v - 7,$ then

B_{ve} = {(1, 2), \dots, (1, v), (2, 3), \dots, (2, v), (3, 4), (4, 5), \dots, (v - 2, v - 1)}

if $e = 3 v - 6,$ then

B_{ve} = {(1, 3), \dots, (1, v), (2, 3), \dots, (2, v), (3, 4), (4, 5), \dots, (v - 1, v), (3, v)}

The adjacency matrix of $M (v, e)$ is defined as $A (M (v, e)) = M + M^{T} .$

Algebraic indices

Codim(G)

It is the codimension of the graph $G$ and is computed in the following way. An edge is a couple of vertices, usually called the endpoints of the edge. As previously said, a vertex meets an edge if that vertex is one of the endpoints of the edge. The codimension $codim (G)$ is the minimum number of vertices needed to meet all the edges of $G$ .

b₂₁(G)

It is an algebraic Betti number of $G$ and is equal to

b_{21} (G) = \sum_{i = 1}^{v} \frac{d_{i} (d_{i} - 1)}{2} - t (G)

(6)

where

d_{i}

is the degree of the ith vertex and

t (G)

is the number of independent triangles on the graph.

Normalized codimension of $G$

codim (G) / {codim}_{\max} (v, e)

(7)

It is the normalized codimension of $G$ . The denominator is defined differently according to the parity of the number of vertices $v$ and it is the codimension of graphs with a special layout with respect to codimension. As we have a function for computing the maximum codimension, the description of the graph is not needed. If the number of vertices is even, i.e. $v = 2 m,$ the denominator is

{codim}_{max} (v = 2 m, e) = {\begin{array}{l} m if e = v - 1, v \\ m + k + 1 if \begin{array}{l} v + 1 \leq e \leq 3 v - 11 \\ e - v - 1 = 4 k + r with 0 \leq r \leq 3 \end{array} \\ v - 2 if e > 3 v - 11 \end{array}

(8)

If the number of vertices is odd, i.e. $v = 2 m + 1,$ the denominator is

{codim}_{max} (v = 2 m + 1, e) = {\begin{matrix} \begin{array}{l} m if e = v - 1 \\ m + 1 if e = v, v + 1, v + 2 \\ m + k + 2 if \begin{matrix} v + 3 \leq e \leq 3 v - 11 \\ e - v - 3 = 4 k + r \\ with 0 \leq r \leq 3 \end{matrix} \\ v - 2 if e > 3 v - 11 \end{array} \end{matrix}

(9)

Normalized $b_{21} (G)$

b_{21} (G) / b_{21} (v, e)

(10)

It is the normalization of $b_{21} (G)$ , where the denominator is equal to

b_{21} (v, e) = {\begin{array}{l} (\begin{matrix} v - 1 \\ 2 \end{matrix}) + (\begin{matrix} e - v + 2 \\ 2 \end{matrix}) & if v - 1 \leq e \leq 2 v - 3 \\ v^{2} - 9 v + 10 + 3 e & if 2 v - 2 \leq e \leq 3 v - 6 \end{array}

(11)

As in the previous cases, $b_{21} (v, e)$ is the Betti number of a graph with a special planar layout with respect to this index. Also in this case, as we have a function for computing the maximum value, the description of the graph is not needed.

Our study focuses on the values of the above described four normalized indices.

In Table 1, we report the values of the indices for the graphs in Figure 1, and the maximum values of the indices for $v = 6, e = 5.$

Figure 1.

Three graphs with $v = 6, e = 5$ used to illustrate the codimension of graphs. White circles point out the vertices that contribute to the codimension. The graph drawn in (c) is $L (6, 5) = M (6, 5) .$

Table 1.

Values of indices for the graphs in Figure 1.

Index	Graph a	Graph b	Graph c	Max value
codim	2	3	1	3
$b_{21}$	6	5	10	10
gap	1	0.92	2.24	2.24
Largest eigenvalue, λ_v	2	1.92	2.24	2.24

The underground and bus transit graphs

Before describing in detail the two datasets taken into consideration, we debate on the statistical significance of the datasets. While it is evident how many networks belong to each dataset, it is hard to estimate the total number of transportation networks (i.e. the universe) that we have to consider. Hence, we do not know what percentage of the universe corresponds to our datasets. Now, we list some reasons to explain why it is hard to estimate the universe. A first fact is that many cities, but not all, have a transportation network in the sense we are considering. Second, there are networks that serve areas containing several cities, usually a large one with a few small satellites. Finally, there are networks connecting different and very crowded areas. All of them are transportation networks but they work on different scales. We are interested in local transportation networks, and so we ought to count the networks of the first type but also some networks of the second type, if not too big. Again, it is optional to include or exclude some of them. Moreover, it is reasonable that some of them are essentially the same network even if on a different scale or in different world areas, and so they have to be counted only once. In conclusion, it is not possible to estimate how big the universe is. A complete different approach could be the following one. As networks are represented by graphs, we can consider all the possible graphs. However, real networks are represented by a relatively small number of graphs if compared to the set of all graphs that can be constructed with the same number of vertices and edges. This remains true even if we change the number of details we consider when passing from networks to graphs. Then, if one considers all possible graphs, information on real networks is limited. A refined strategy could consist in selecting the graphs that do represent transportation networks. To implement such a strategy, however, we need to characterize such graphs. Unfortunately, up to now, in literature, no one has proposed such a characterization. Finally but not least, real networks dynamically change very rapidly, and so a graph represents a real network only for the time the considered network does not change. In conclusion, we are not able to evaluate the statistical significance of our datasets. However, we are sure we can consider the actual transportation networks as expressions of similar processes, reducing dramatically our universe, and so the proposed datasets are suitable at least for inferring information about the universe.

A further remark concerns the restriction on graphs we associate to networks. In fact, we only consider undirected, planar, connected, and simple graphs. While every transportation network is connected, the planarity requirement could not be achieved for all networks, even if it generally does for the ones we took into account. In general, we assume there is a node every time two or more lines cross. The choice of considering undirected and simple graphs limits the network properties we can deal with. For example, we cannot consider physical network characteristics, such as the performance of a link (length, travel time, fare, or other costs), as well as interaction with demand. In fact, to capture such properties, one needs weighted, directed, and non-planar graphs. The definition of the proposed indices for such extended graphs deserves much further theoretical consideration and we are dealing with them for a following study. Finally, we remark that, as a byproduct of the procedure we use to construct a graph from a network, degree 2 vertices are very rare. The choice of not considering degree 2 vertices is justified by the fact that they do not modify the topology of the graph, but, of course, it is an information that can be taken into consideration when studying weighted graphs.

Now, we describe the two datasets in detail.

The first set consists of 41 graphs representing underground networks, from the largest cities worldwide (Table 2). The second set contains 33 graphs representing bus transit local transport networks for 38% of Italian cities with a population in the range of 90,000–200,000 inhabitants (Table 3). Though both samples can be considered statistically significant with respect to the represented universe, they were limited only by the availability of transportation network maps.

Table 2.

Number of vertices, edges, and some results for the graphs of the first scenario – Underground graphs of some worldwide cities (norm. stands for normalized).

No.	Network	Vertices	Edges	norm. codim	norm. b21	norm. gap	norm. $λ_{v}$
1	Rome	5	4	0.500	1.000	2.000	1.000
2	Cairo	6	5	0.667	0.600	2.236	0.894
3	Marseille	6	5	0.667	0.600	2.236	0.894
4	Cairo_modified	7	7	0.500	0.750	2.039	0.955
5	Marseille_modified	7	7	0.500	0.750	2.039	0.955
6	Delhi	8	7	0.500	0.571	2.646	0.869
7	Athens	9	9	0.600	0.483	2.268	0.860
8	Brussels	9	9	0.800	0.483	2.268	0.863
9	Prague	9	9	0.600	0.586	2.268	0.910
10	Toronto	10	9	0.800	0.306	3.000	0.717
11	Lyon	10	10	0.800	0.486	2.389	0.825
12	Montreal	10	10	0.800	0.486	2.389	0.825
13	Toronto_modified	10	10	0.800	0.432	2.389	0.835
14	Lisbon	11	11	0.667	0.457	2.510	0.810
15	Athens_modified	11	12	0.667	0.479	2.504	0.843
16	Bucharest	11	12	0.833	0.438	2.504	0.800
17	Montreal_modified	11	12	0.667	0.521	2.504	0.843
18	Buenos Aires	12	13	0.571	0.534	2.588	0.881
19	Singapore	12	13	0.714	0.397	2.588	0.794
20	Milan	14	15	0.750	0.346	2.766	0.799
21	St Petersburg	14	16	0.625	0.405	2.806	0.790
22	Hong Kong	17	18	0.889	0.244	3.046	0.658
23	Washington D.C.	17	18	0.667	0.268	3.046	0.713
24	Stockholm	20	19	0.800	0.164	4.359	0.557
25	Stockholm_modified	20	20	0.700	0.198	3.535	0.639
26	Boston	21	22	0.727	0.212	3.420	0.644
27	Boston_modified	22	24	0.750	0.204	3.409	0.620
28	Shanghai	22	28	0.692	0.290	3.590	0.715
29	Chicago	24	28	0.769	0.228	3.526	0.639
30	Chicago_modified	25	30	0.714	0.226	3.621	0.634
31	Barcelona	29	42	0.778	0.226	4.641	0.661
32	Berlin	32	43	0.737	0.192	4.371	0.563
33	Mexico City	35	52	0.727	0.183	5.168	0.547
34	Osaka	36	51	0.773	0.174	4.880	0.553
35	Moscow	43	66	0.786	0.156	5.885	0.525
36	Madrid	73	124	0.760	0.094	8.711	0.444
37	Seoul	78	124	0.784	0.079	7.951	0.398
38	New York	86	136	0.768	0.072	8.214	0.383
39	London	87	121	0.788	0.067	6.854	0.400
40	Paris	104	165	0.735	0.065	8.964	0.380
41	Tokyo	131	233	0.736	0.055	12.302	0.377

Table 3.

Number of vertices, edges, and some results for the graphs of the second scenario – Bus transit local transport graphs of some Italian cities (norm. stands for normalized).

No.	Network	Vertices	Edges	norm. codim	norm. b₂₁	norm. gap	norm. $λ_{v}$
1	Busto Arsizio	19	28	0.833	0.293	0.103	0.622
2	Lucca	20	24	0.727	0.274	0.204	0.675
3	Ravenna	24	28	0.769	0.201	0.090	0.607
4	Pesaro	25	30	0.714	0.219	0.179	0.658
5	Cagliari	26	31	0.733	0.187	0.101	0.583
6	Alessandria	26	34	0.800	0.217	0.098	0.585
7	Asti	27	35	0.750	0.216	0.139	0.615
8	Rimini	27	35	0.750	0.243	0.178	0.664
9	Cesena	29	39	0.765	0.203	0.154	0.635
10	Novara	31	43	0.737	0.205	0.131	0.586
11	Cremona	32	44	0.789	0.173	0.114	0.558
12	Pisa	34	46	0.750	0.165	0.093	0.547
13	Prato	35	49	0.810	0.197	0.137	0.619
14	Monza	36	49	0.727	0.174	0.051	0.560
15	Treviso	38	47	0.773	0.150	0.161	0.582
16	Brescia	41	54	0.667	0.166	0.096	0.584
17	Pavia	41	57	0.840	0.133	0.103	0.513
18	Vicenza	42	47	0.609	0.106	0.037	0.452
19	Lecce	43	52	0.708	0.123	0.050	0.472
20	Bolzano	43	69	0.857	0.136	0.055	0.491
21	Arezzo	44	55	0.800	0.119	0.036	0.462
22	Forli	45	64	0.821	0.114	0.061	0.476
23	Como	47	61	0.815	0.118	0.034	0.468
24	Bergamo	50	62	0.821	0.103	0.093	0.507
25	Parma	50	65	0.724	0.127	0.154	0.554
26	Reggio Emilia	50	65	0.724	0.117	0.072	0.478
27	Foggia	53	79	0.848	0.104	0.027	0.435
28	Piacenza	56	81	0.857	0.098	0.048	0.436
29	Massa	58	79	0.771	0.099	0.055	0.455
30	Ferrara	62	77	0.800	0.079	0.028	0.393
31	Udine	63	82	0.757	0.084	0.045	0.425
32	Modena	70	99	0.721	0.089	0.063	0.437
33	Aquila	79	100	0.800	0.069	0.088	0.410

In the first scenario, there are 41 graphs (Table 2). Thirty-three of these graphs were built up by Derrible and Kennedy (2010a) to represent functionally the underground networks of certain large cities worldwide. Variants of eight graphs from the above ones are also taken into consideration (indicated with the label “modified”) and added to the list. In the paper by Roth et al. (2012), 14 networks are used, and in that above-mentioned by Derrible and Kennedy (2010a) they are 33.

For the second scenario, we built up 33 graphs to represent functionally the bus transit local transportation networks for some medium-sized Italian cities (Table 3). For some of those cities, the available data were the list of the main stops of each bus line. In those cases, we superimposed the list to the city map and we considered as nodes the junctions with at least three entering/exiting connections, or terminal stops, as in the first scenario.

As indicated in the “Introduction” section, this new dataset consists of transit networks of cities all lying in a geographically small area if compared to the other dataset. Moreover, the considered cities date back to at least the Middle-Ages, and so their transportation networks, although designed in the last decades, had to be integrated with a settled urban network.

The graphs representing underground networks have mostly a number of vertices less than 26, and the others are scattered in the range 30–131. Moreover, graphs with the number $v$ of vertices less than 21 have a number of edges at most one more than that number (we remind that the maximum number of edges for a planar graph is 3v−6). The graphs representing bus transit networks, on the contrary, have a number of vertices in the range 19–79, with an almost uniform distribution. For such graphs, the number of edges is higher in percentage.

Considering both datasets together, however, the number of edges is in the range $v - 1 \leq e \leq 2 v - 4$ , i.e. in the first half of the theoretical range for planar connected graphs. In both datasets, there are different graphs with the same number of vertices and/or edges, which we can use to compare the performance of the indices.

The considered cities in the first scenario are much more populated than those in the second scenario. Nevertheless, the associated networks have a comparable number of nodes and links, due to the cost of building, managing, and maintaining a complex underground network with respect to a bus transit one.

We computed the indices proposed in the “The indices” section for both the datasets. The computation of the linear algebraic indices was performed by using MatLab^©, while the algebraic indices were computed by using Singular (Decker et al., 2015). In Tables 2 and 3, for the sake of brevity, we report only the normalized indices. In fact, the normalized indices are more suitable for comparing graphs that have different numbers of vertices and edges.

Results

Tables 2 and 3 show that the values of the indices, when considered all together, vary significantly between graphs of the same set. The only exception is Lyon and Montreal, but their graphs are the same, once the vertices are re-labeled. Hence, the considered indices are suitable for detecting the different topologies of the analyzed graphs. The indices show more or less a monotonic trend with respect to the number of vertices. In fact, the largest eigenvalue, the gap, and the degree 1 algebraic Betti number are clearly decreasing, while codim is increasing in the first scenario and constant in the second one.

Now, we begin to analyze the data of Tables 2 and 3. We observed in the “The underground and bus transit graphs” section that the number of vertices of the graphs in the first scenario is not homogeneous. In order to understand how much this affects results, we cluster the graphs having the number of vertices in [19, 19 + p − 1], in [19 + p, 19 + 2p − 1], in [19 + 2p, 19 + 3p−1], and so on until it reaches 79, the largest number of vertices for graphs in the second dataset, with p = 2, 5, 10. We perform an analogous clustering also on the first dataset. For each subset, we compute the averages of the indices. By comparing those numbers, it is easy to see that clustering acts only as a low-pass filter and trends present in data do not change. As expected, we get a smooth interpolating curve when p grows.

To confirm that the proposed indices are suitable for detecting different topologies, we perform a further analysis. We compare three graphs of the second scenario (the cities of Bergamo, Parma, and Reggio Emilia), with 50 vertices each, but with different numbers of edges: 62, 65, and 65, respectively. The comparison confirms that the proposed indicators are capable of pointing out differences between the topologies of these graphs as shown in Table 4, where values are re-normalized according to their maximum column values for easy comparison. Although the three considered cities have graphs with the same number of vertices and two of them also have the same number of edges, the indices are different. The Parma graph emerges as the most complex one. By analyzing the distribution of node degrees (Figure 2(a)), we can observe that the Parma graph has the highest number of degree 6 vertices (i.e. with node degree equal to 6) which indicates a more complex local structure. By analyzing also the minimum spanning trees of these graphs, we observe some differences, particularly Parma spanning tree differs from the other two for its number of levels which is lower (9 versus 11). That denotes the presence of higher degree vertices. Also its diameter is lower. However, we note that the node degree or distance, considered alone, is not enough to render the complexity of a graph, because it is easy to construct trees (i.e. the simplest graphs) with many vertices of very large degree.

Figure 2.

Distribution of vertex degree for the three graphs with 50 vertices of the second scenario (a) and for the three graphs with 43 vertices from both scenarios (b); the number in brackets below city name represents the number of edges.

Table 4.

Normalized indices for the three graphs with 50 vertices of the second scenario, and for the three graphs with 43 vertices from both scenarios, re-normalized by their maximum relative values (norm. stands for normalized).

	Vertices	Edges	norm. codim	norm. b₂₁	norm. gap	norm. lambda
Bergamo	50	62	1.00	0.78	0.58	0.87
Parma	50	65	0.92	1.00	1.00	1.00
Reggio Emilia	50	65	0.92	0.93	0.47	0.86
Lecce	43	52	0.62	0.62	0.39	0.71
Bolzano	43	69	1.00	0.91	0.57	0.98
Moscow_MN	43	66	0.88	1.00	1.00	1.00

We perform another analysis of the same type on three other graphs, one from the first scenario and two from the second one, namely the cities of Moscow, Bolzano, and Lecce, with 43 vertices each, and with a different number of edges: 66, 69, and 52, respectively. As shown in Table 4, also in this case the indices show some differences. The Moscow graph turns out to be the most complex. The node degree distribution of Moscow has the highest number of degree 5 vertices, while the number of degree 6 vertices is the same for Moscow and Bolzano (see Figure 2(b)). It holds also for this triplet of graphs that the minimum spanning tree of Moscow has the lowest number of levels and also its diameter is the lowest.

It must be pointed out that these two last analyses have to be considered only as indicative because of the limited number of cases they include, and the many spanning trees a graph has. Despite this statistical weakness, however, sensitiveness to all the indices cannot be denied. In conclusion, we have clear evidence that the four scale-free proposed indices are suitable for analyzing networks.

To compare the values of the indices for the two scenarios, we plotted them together, getting a diagram for each normalized index versus the number of vertices (Figure 3). The four pictures highlight the different distribution of vertices for graphs of the two datasets. In fact, as remarked in the “The underground and bus transit graphs” section, the second scenario (the bus transit one) has the most number of graphs concentrated in the central range of the considered number of vertices, whereas the first scenario (the underground one) is more scattered over the whole range. Nevertheless, the two sets of data actually complete each other, as Figure 3 shows, by arranging data for each index around a hypothetic fitting curve. Repeating the above procedure versus the number of edges, we get very similar results. Hence, we can merge the two datasets, no matter what type of network they represent, and we get a more robust database. This might be useful for investigating whether or not a graph represents a transportation network: if the values of the indices of the graph are comparable to the ones of the dataset then the graph can be associated to a transportation network.

Figure 3.

Relationships between the number of vertices and normalized codim (a)_, b₂₁ (b), gap (c), and λ_v (d) for graphs of underground and transit networks.

In order to investigate the best regression curve for each of the four normalized indices, we compute the fitting curve first on separated datasets and then on the joint dataset. The null hypothesis of both computations is that data in datasets belong to different population. We used curves belonging to different families: exponential, rational, and polynomial curves. The best performance (based on R² value) is obtained by using a double exponential curve

index . value = {ae}^{- bx} + {ce}^{- dx}

(12)

for the four indices. The codim curve has the highest dispersion (and worst performance, R² = 0.367) but this can be regarded as a merit factor, since it shows how strongly codim is affected by the topology of graphs. On the other hand, the other three indices exhibit a high correlation (norm b₂₁ R²=0.932, norm gap R²=0.814, norm

λ_{v}

R²=0.947).

This result suggests two considerations. First, the way a transit network changes when a new vertex or a new edge is added is quite well defined. In fact, it is enough to use the fitting curve to predict the values of the indices for a new configuration. What is still difficult to assess is how the new vertex is connected even if (or even though) the range of possibilities is likely to be very wide. Second, the two sets of transit networks behave similarly with respect to the number of vertices and edges of the associated graphs. Probably, this is due to the fact that the proposed analysis on topology is essentially scale-free and so it points out only some aspects of the transportation networks.

Conclusions

The present paper can be included in the vast literature aimed at studying transportation networks via the computation of indices of the associated graphs. We propose a set of scale-free indices to measure the differences in topology of graphs associated to transportation networks. We compute the values of the indices for graphs belonging to two different technological scenarios: the graphs of the first set represent underground networks, while the graphs of the second set represent bus transit networks. The underground set refers to underground systems of some relevant cities in the world, whereas the bus transit set contains the transit lines of some medium-sized Italian cities (mainly served by buses but also by tramways).

Particular care is employed to normalize indices by using the maximum value we can get from undirected, planar, connected, and simple graphs with exactly the same number of vertices and edges.

The analysis of the values of the indices for both scenarios shows that they vary even if the graphs have the same number of vertices and/or edges. Hence, we can use them to evaluate the differences, whereby edges connect vertices.

We also observe a relationship between node degrees and the values of indices in the sense that a graph with the highest node degree, among graphs with the same number of vertices and edges, has also the highest values of indices and vice versa. Moreover, the normalized values of the indices are well fitted by double exponential curves for both datasets and their union. The R² fitting index is greater than 0.80 for all indices except for codim which has a higher dispersion of values and a R² not greater than 0.37. This deserves further investigation but it can be considered a prospective merit since data dispersion is mainly due to differences reported by the index for different topologies.

Finally, we can conclude that the two datasets can be merged together in order to build a more robust/significant one, suitable for deciding whether a generic graph can be considered a possible representation of a transportation network.

From the topological point of view, our results prove that the two types of networks are built, more or less, by using the same underlying criteria. In fact, the list of an increasing number of vertices and edges could be thought of as a time modification of a transportation network, no matter what type it is. In particular, this result shows that the structure of transportation graphs tends to be restricted to a few basic topologies and not to the most complex ones involving an equal number of vertices and edges. We could consider the sets of considered graphs, from the smallest to the largest one, like a possible way a network evolves in time, though in our application we have not taken into account temporal dynamics.

This result seems very close to the one published by Roth et al. (2012). However, the limitation to a few “dominant mechanisms governing the evolution of these structures” emerges quite clearly from the fact that index values lie around the same curve.

Our last comment concerns a possible definition of a transportation graph, that is to say, a graph that could represent a transportation network from an abstract point of view. From the cases under investigation, such a graph is undirected, connected, planar, and simple, with a number of edges in the range $[v - 1, 2 v - 4],$ and indices not too far from the fitting curves we computed.

The extension of this approach to direct and/or weighted graphs needs further development and research. Direct or weighted graphs will allow us to take into account other crucial features associated to transportation graphs, such as e.g. length, travel time, costs, number of stops, speed, frequency, potential and satisfied demand, real estate values of buildings close to lines, and so on. On the other hand, the adjacency matrix of a direct graph is no longer symmetric, and so its eigenvalues may be not real. The algebraic indices, too, need to be redefined if they are to be used in this new setting.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Lorenzo Mussone is Associate Professor in Transportation engineering at Politecnico di Milano. His main scientific activities concern traffic modeling by means of different techniques: partial derivative macroscopic equations, microscopic simulation, neural networks, and swarm intelligence; graph theory. Main fields of research are road accident data analysis; vehicular flow control in urban road networks and motorways; capacity calculation of complex railway systems; driver behavior and performance analysis; roundabouts, application of AI tools to transportation analysis and modeling, ITS applications and performance analysis. He wrote more than 170 papers on national and international journals. He is in the panel of reviewers of many transportation journals.

Roberto Notari is Associate Professor in Geometry at Department of Mathematics of Politecnico di Milano since 2015. His research interests range from Algebraic Geometry and Commutative Algebra to their applications. In particular, his latest researches have focused on the geometric properties of the parameter spaces of some classes of algebras, on the study of the deterministic and statistical models associated to the localization problem, on the computation of indices suitable to describe transportation graphs, and on the description of critical loci in Computer Vision.

References

Alexander

(1965) A city is not a tree. Architectural Forum 122(1): 58–62.

Barabasi

A-L

Albert

(1999) Emergence of scaling in random networks. Science 286(5439): 509–512.

Barthelemy

(2011) Spatial networks. Physics Reports 499: 1–101.

Blumenfeld-Lieberthal

(2009) The topology of transportation networks: A comparison between different economies. Networks and Spatial Economics 9: 427–458.

Decker

Greuel

G-M

Pfister

, et al. (2015) Singular 4-0-2 – a computer algebra system for polynomial computations. Available at: http://www.singular.uni-kl.de (accessed 19 September 2019).

Derrible

(2016) Urban infrastructure is not a tree: Integrating and decentralizing urban infrastructure systems. Environment and Planning B: Urban Analytics and City Science 44(3): 553–569.

Derrible

Kennedy

(2010a) Characterizing metro networks: State, form, and structure. Transportation 37: 275–297.

Derrible

Kennedy

(2010b) The complexity and robustness of metro networks. Physica A 389(2010): 3678–3691.

Derrible

Kennedy

(2012) A network analysis of subway systems in the world using updated graph theory. Transportation Research Record 2112(1): 17–25.

10.

Ducruet

Lugo

(2013) Structure and dynamics of transportation networks: Models, concepts, and applications. In: Rodrigue

Notteboom

Shaw

(eds) The SAGE Handbook of Transport Studies. Thousand Oaks, CA: SAGE Publications, pp.347–364.

11.

Estrada

(2012) The communicability distance in graphs. Linear Algebra and Its Applications 436(2012): 4317–4328.

12.

Estrada

Hatano

Benzi

(2012) The physics of communicability in complex networks. Physics Reports 514(2012): 89–119.

13.

Garrison

Marble

(1962) The Structure of Transportation Networks. Evanston, IL: Transportation Center Northwestern University.

14.

Garrison

Marble

(1964) Factor-analytic study of the connectivity of a transportation network. Papers of the Regional Science Association 12(1): 231–238.

15.

Gastner

Newman

MEJ

(2006) The spatial structure of networks. The European Physical Journal B 49: 247–252.

16.

Gattuso

Miriello

(2005) Compared analysis of metro networks supported by graph theory. Networks and Spatial Economics 5(4): 395–414.

17.

Kurant

Thiran

(2006) Extraction and analysis of traffic and topologies of transportation networks. Physical Review E 74: 036114, 1–10.

18.

Mussone

Notari

(2017) Structure indicators for transportation graph analysis I: Planar connected simple graphs. Networks and Spatial Economics 17: 69–2.

19.

Roth

Kang

Batty

, et al. (2012) A long-time limit for world subway networks. Journal of the Royal Society Interface 9: 2540–2550.

20.

Wanga

Koç

Derrible

, et al. (2017) Multi-criteria robustness analysis of metro networks. Physica A 474(2017): 19–31.

21.

Xie

Levinson

(2007) Measuring the structure of road networks. Geographical Analysis 39: 336–356.

22.

Xie

Levinson

(2009a) Modeling the growth of transportation networks: A comprehensive review. Networks and Spatial Economics 9: 291–307.

23.

Xie

Levinson

(2009b) Jurisdictional control and network growth. Networks and Spatial Economics 9: 459–483.

A comparative analysis of underground and bus transit networks through graph theory

Abstract

Keywords

Introduction

Literature review and paper aims

The indices

Linear algebraic indexes

λv

Gap g

Normalized largest eigenvalue

Normalized gap of G

Algebraic indices

Codim(G)

b21(G)

Normalized codimension of G

Normalized b 21 ( G )

The underground and bus transit graphs

Results

Conclusions

Footnotes

Declaration of conflicting interests

Funding

References

λ_v

b₂₁(G)

Normalized codimension of $G$

Normalized $b_{21} (G)$