# Analysis of Public Bus Transportation of a Brazilian City Based on the Theory of Complex Networks Using the P-Space

Authors: A. A. De Bona; K. V. O. Fonseca; M. O. Rosa; R. Lüders; M. R. B. S. Delgado
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The city of Curitiba, located at Southern Brazil, is recognized by its urban planning structured on three pillars: land use, collective transportation, and traffic. With 3.8 million people in its metropolitan area, the public transport system deals with approximately 2.5 million passengers daily. The structure and properties of such a transportation system have substantial implications for the urban planning and public politics for sustainable development of Curitiba. Therefore, this paper analyzes the structure of the public transportation system of Curitiba through the theory of complex networks in a static approach of network topology and presents a comparative analysis of the results from Curitiba, three cities from China (Shanghai, Beijing, and Guangzhou), and three cities from Poland (GOP, Warszawa, and Łódź). The transportation network was modeled as a complex network with exact geographical coordinates of its bus stops. In all bus lines, the method used was the P-Space. The results show that this bus network has characteristics of both small-world and scale-free networks.


---

## Body

## 1. Introduction

The theory of complex networks had its origins in graph theory with concepts from statistical mechanics, physics, and systems considered as complex [1]. These networks can be classified into social, technological, biological, information categories. As networks, their vertices and edges can describe their properties. For example, in a complex network, people can be represented by the nodes and the various relations between them by edges (connections between nodes).Complex networks may have various topologies and characteristics according to the studied domain and can be analyzed, characterized, and modeled using some metrics [2]. Networks can also be static or dynamic: static when the number of nodes and vertices is time-independent and dynamic when it is possible to model their growth by an analysis of its structure variation throughout time.Since the publication of the first article about small-world networks [3], research on complex networks has been a topic studied in the academia. Thereafter various concepts and models were introduced aiming at observing various physical processes, such as network dynamics, and how a network structure affects its dynamic behavior [4]. Public transportation systems (PTS) have been empirically analyzed under complex network framework. Complex network models of PTS (for bus and metropolitan train networks) can have a significant role in relieving congestion of increasingly heavy traffic in large cities due to urban expansion and population growing. The objective of many studies in the past two decades has been understanding and seeking to solve the existing urban mobility problem in all major cities in the world. Many studies have focused on some complex network static properties like degree distribution, average distance of the shortest path, clustering coefficient, closeness, and betweenness centrality that had some meaning to the studied PTS. One of the first studies [5] investigated the USA Boston subway network and highlighted the small-world properties and the so-called local and global efficiency of the PTS. Indian railway network was also studied [6] and indicated that it had small-world properties, like small average distances, and exponential degree distribution. Also urban train networks of Vienna (Austria) and Boston (USA) were analyzed by extending the use of random bipartite graph models from social networks to technological ones [7].Public bus networks of 22 polish cities were modeled as complex networks using 2 different representations (P-Space and L-Space) [8] and obtained power-law and exponential degree distributions followed, respectively. Similar analysis conducted over 3 bus transportation networks of Chinese cities [9] revealed that these networks had small-world behavior. Similar results from PTS of some major Chinese cities [10] confirmed such a behavior. A study of public transportation of 14 cities in the world [11] showed that their complex network models had power-law degree distribution with different exponents; a result also is shown in [8]. Later, those authors [12] proposed an evolutionary model of mapping PTS growth in order to conduct a more comprehensive analysis. Scale-free network behavior was identified in several analyses performed over 33 metro-based PTS [13]. It happened due to the presence of large transfer hubs (or station) in 3 metro lines. It has also revealed that 19 of these systems had close relationship between the number of passengers and the network layout. It was identified from studies of topological and functional properties of complex networks [14] that Shanghai’s subway network was robust against random attacks but weak for targeted attacks and that the disconnection of the subway stops with the highest betweenness values could cause serious damage into this network. Although dynamic properties of transport networks have been studied, their common characteristics have not been identified [15]. All previous studies addressed statistical behavior of complex networks generated from PTS data (bus stops and bus lines). However the usefulness of complex network framework for the city planner was barely discussed. City planners have to answer population expectations like fast way to reach all PTS stops in the city, increase in vehicle frequency of transportation lines, reduction in the number of connections to reach a destination, and so forth. Nowadays Curitiba (a city in Sothern Brazil well-known by its bus-based transportation system) and its planners have addressed these expectations purely based on their experimental knowledge of years of PTS management. This paper analyzes the static topology of Curitiba PTS using complex network theory based on P-Space representation. Its characteristics were objectively measured by complex network metrics as degree, degree distribution, the shortest averaged path, clustering coefficient, community structure metric, and centrality metrics (betweenness and closeness ones). Using these metrics, comparisons with results from other cities of comparable size were performed. The second purpose was to relate this complex network analysis to geographic information (spatial location of the bus stops) in order to provide useful information for city planners by answering questions like the following. Which Curitiba’s neighbors were well and ill served by the PTS layout? Are the central bus stops (closeness) well spread along the city? Are the most important bus stops (betweenness) close to each other in order to easily allow lines detours in case of a localized strike, for example? Are the bus stops capable of sustaining the amount of lines served by it? These are questions that city’s planners are interested in and this paper will address them. This paper is organized as follows: first the concepts of complex networks and Curitiba’s public transportation system (CPTS) are shown. Then a topological analysis is performed, and a comparison to recent researches (based on similar conditions) is made in order to find better understanding of the topological properties of CPTS.


## 2. Complex Network

A complex network is a graph with nontrivial topological characteristics that are found in transport networks, computer networks, telecommunications networks, social networks, and biological networks [20]. Basic concepts of graph theory can be applied directly to any real-world network: vertices (nodes), edges (links or connections), degree of a vertex, loops, directed or undirected graphs, and paths. For example, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice [21]. Such networks may be static when the number of vertices and edges or even the configuration of the connections does not vary with time or dynamic. The later allows modeling the network growth by analysis of the variation in time of their structure. Although real-world networks are dynamic, they may still be analyzed as static ones if time-based variations are nonexistent or less important [2]. The understanding of the complex network topology primarily allows the development of mathematical models used for simulation of events and processes that may occur on the network. The following sections describe the application of these concepts for characterization of complex networks.


### 2.1. Random Networks

The most basic model of complex networks consists of generating random graphs withN vertices and m edges. Initially proposed by Erdős and Rényi [16] as random graph or random network, this was the first model with capability of coherently describing networks of diverse sizes. For example, it can represent a bus transportation system if the majority of bus stops (nodes) have approximately the same number of connections and only a few vertices (connections between bus stops according to their bus lines) differ on a larger scale of the global average degree. The random network null-hypothesis thus makes a specific prediction: degree distributions are bell-shaped normal distribution [22].


### 2.2. Small-World Networks

The small-world network, proposed by Watts and Strogatz [3], is the most popular model of random networks [2, 23] because of its treatments for high transitivity and clustering coefficient (a complex network property that defines how the vertices are connected). A small-world network with N vertices [3], as shown in Figure 1, consists of a regular network with N vertices connecting the k nearest neighbor vertices in each direction totaling 2
m initial connections/edges, N
>
m
>
log
⁡
N
>
1. Then, all the possible edges are randomly reconnected with a fixed probability p (a concept from random network). If p
=
0, the network will have a large number of loops and long paths. If p
=
1, it becomes a totally random network with few loops and short paths. Another way to build a small-world network is to start with a regular network and then just randomly add some new connections/edges [23].Figure 1
Relocation procedure edges in small-world model, proposed by Watts and Strogatz [3].In Figure1 shows how p changes the network randomness: for p
=
0, vertices are connected in pairs and they determine a regular network; as p increases, the number of connections grows and therefore defines a small-world network; p
=
1 represents a random network. A small-world network is a common representation of many domains and presents a large number of connections between three vertices.


### 2.3. Scale-Free Networks

The models proposed by Erdős and Rényi (random networks) and Watts and Strogatz (small-world networks) [3] show a random pattern in edges and a characteristic degree in the majority of the vertices. The model proposed by Albert and Barabási [24] showed that several real systems are characterized by an unequal distribution of connections or a pattern of preferred connections called rich-get-richer (proposed by Albert and Barabási [23]) what in fact can be explained as a competitive advantage. This fact results in some highly connected vertices and others with low number of edges and the absence of a characteristic degree on the vertices [2]. The resulting model is known as scale-free network which shows an irregular distribution of edges. The set of edges to a same vertex indicates the appearance of central vertices called hubs, which are vertices that concentrate edges to many other vertices, as shown in Figure 2.Figure 2
Example of scale-free networks [3].


## 2.1. Random Networks

The most basic model of complex networks consists of generating random graphs withN vertices and m edges. Initially proposed by Erdős and Rényi [16] as random graph or random network, this was the first model with capability of coherently describing networks of diverse sizes. For example, it can represent a bus transportation system if the majority of bus stops (nodes) have approximately the same number of connections and only a few vertices (connections between bus stops according to their bus lines) differ on a larger scale of the global average degree. The random network null-hypothesis thus makes a specific prediction: degree distributions are bell-shaped normal distribution [22].


## 2.2. Small-World Networks

The small-world network, proposed by Watts and Strogatz [3], is the most popular model of random networks [2, 23] because of its treatments for high transitivity and clustering coefficient (a complex network property that defines how the vertices are connected). A small-world network with N vertices [3], as shown in Figure 1, consists of a regular network with N vertices connecting the k nearest neighbor vertices in each direction totaling 2
m initial connections/edges, N
>
m
>
log
⁡
N
>
1. Then, all the possible edges are randomly reconnected with a fixed probability p (a concept from random network). If p
=
0, the network will have a large number of loops and long paths. If p
=
1, it becomes a totally random network with few loops and short paths. Another way to build a small-world network is to start with a regular network and then just randomly add some new connections/edges [23].Figure 1
Relocation procedure edges in small-world model, proposed by Watts and Strogatz [3].In Figure1 shows how p changes the network randomness: for p
=
0, vertices are connected in pairs and they determine a regular network; as p increases, the number of connections grows and therefore defines a small-world network; p
=
1 represents a random network. A small-world network is a common representation of many domains and presents a large number of connections between three vertices.


## 2.3. Scale-Free Networks

The models proposed by Erdős and Rényi (random networks) and Watts and Strogatz (small-world networks) [3] show a random pattern in edges and a characteristic degree in the majority of the vertices. The model proposed by Albert and Barabási [24] showed that several real systems are characterized by an unequal distribution of connections or a pattern of preferred connections called rich-get-richer (proposed by Albert and Barabási [23]) what in fact can be explained as a competitive advantage. This fact results in some highly connected vertices and others with low number of edges and the absence of a characteristic degree on the vertices [2]. The resulting model is known as scale-free network which shows an irregular distribution of edges. The set of edges to a same vertex indicates the appearance of central vertices called hubs, which are vertices that concentrate edges to many other vertices, as shown in Figure 2.Figure 2
Example of scale-free networks [3].


## 3. Curitiba’s Public Transportation System

Curitiba’s public transportation system (CPTS) is founded on the integrated use of buses in order to allow users to change among several bus lines and pay only one fare ticket with comfort and fast access to their destinations. Structurally it is based on north-south and east-west lines where the so-called express buses travel in exclusive roads. Adjacent to these roads there are slow-speed parallel ways for private cars. These pathways (fast bus and slow cars ways) establish a ternary system that structures all Curitiba’s urban planning as a whole, moving people from and to downtown [25]. Also there are bus lines connecting distinct Curitiba’s city neighbors directly and connecting Curitiba downtown to specific city neighbors not as fast as express bus does. All those lines form the so-called Integrated Transport Network (because of the complexity and number of lines, a vision of the Curitiba public transport based only on transport using buses is shown in Figure 3 in simplified form, because there is no metro stations in the city of Curitiba). The integration process (one fare-multiple bus uses) occurs in places called integration terminals. Thus, the user can choose their own path to scroll through several neighborhoods of Curitiba and its metropolitan region.Figure 3
Simplified distribution of bus lines in Curitiba [19].Altogether there are 14 cities interconnected by this network of bus lines which provides wide mobility to approximately 2.5 million people daily. Table1 summarizes the CPTS operation [25]. It is important to mention that Curitiba does not have a train or metro system.Table 1
Operational summary-CPTS [16].
Operational data
Urban
Metropolitan integrated
Total
Number of buses
1,362
583
1,945
Number of buses (1)
1,500
645
2,145
Passengers transported (2)
1,811.000
459.000
2,270.000
Equivalent paying passengers (2)
828,500.00
201.500
1,030.000
Equivalent paying passengers (3)
19,950.000
5,050.000
25,000.000
Lines
509
106
615
Integration terminals
21
9
30
Tube station
345
12
357
Bus stops
6,516
2,550
9,066
Kilometers traveled (2)
330,000
150,000
480,000
1: including reserves, 2: business day, and 3: average, month, year.A bus line in CPTS is defined by its bus stops (origin, destination, and intermediate stops) that must be followed sequentially (a fixed path) according to a day-based timetable schedule, all predefined. A bus line usually has a reverse line associated: given a line with A and B as origin and destination bus stops, its reverse line will be B and A.CPTS also has different kinds of bus stops. They can be classified according to their infrastructure and capacity to attend passengers and how they are charged for tickets. These are the three kinds of bus stops in Curitiba:(1)
Regular bus stop is characterized by a simple infrastructure which attends few passengers and does not have accessibility devices. The fare is charged once inside the bus.
(2)
Integration terminal is characterized by large infrastructure to support lots of passengers and buses. It also has accessibility devices and passengers are charged at terminal entrance.
(3)
Tube station has intermediate infrastructure to support not too many passengers and buses. It is an intermediate infrastructure which also confines commuters inside it like an integration terminal but in a small scale. They have accessibility devices and passengers are charged at tube entrance. Inside terminals and tube stations, Curitiba’s passengers are allowed to change between buses without being charged. It is expected the CPTS commuting the largest number of users with comfort to/from the largest amount of destinations. By promoting a better public commuting service, a reduction on private car circulating is expected in the city. This is an important goal of Curitiba’s planners for the sustainable urban development of the city [26].


## 4. P-Space and L-Space

The definition of the complex network elements of a public transport network and how this network shall be modeled requires a lot of attention to establish a simple model where the extraction of results can be performed in a limited time [27]. The most widely used topologies are the P-Space and L-Space [8–10, 19, 27–30]; sometimes P-Space was called space-of-changes [5, 6]. L-Space is shown in Figure 4(a). In this network for transportation modeling, a node corresponds to a bus stop and an edge represents a connection/link between two adjacent bus stops on the same route [19, 29, 30]. The aim of using L-Space networks is to find out if there are isolated lines or evaluate the possibility of accessing a certain city region by taking buses from any lines. A measurement as network degree allows comparison between two lines in terms of their node degree. P-Space is also shown in Figure 4 and is considered a transfer network, where a node is also a bus stop. The edges are formed by the links between all pairs of bus stops in the same bus line. So based on a P-Space topology shown in Figure 4(b), it is possible to observe that bus stop 3 has a degree of 8, so 8 bus stops can be reached from bus stop 3 without transfer, and the length between bus stop 4 and bus stop 7 is 2, so the passenger has to make one transfer to reach bus stop 4 from bus stop 7. Clearly the order of bus stops in a line has no effect in P-Space representation because all the bus stops in a bus line are considered first-order neighbors of an analyzed bus stop in that bus line. Therefore P-Space modeling of a network enables us to compute the amount of transshipment bus stops (they connect bus stops belonging to more than one bus line) and therefore estimate the average amount of bus transfer to reach a destination bus stop from any other bus stop, for example. P-Space can better describe the accessibility and convenience of transportation network. Furthermore, it has a strong generalization due to ignoring the sequential order of the stops in a route [30].Figure 4
(a) L-Space and (b) P-Space topological representations of two hypothetical bus lines: Line A is formed by bus stops 6, 7, 8, 4, and 9, and Line B is formed by bus stops 1, 2, 3, 4, and 5.
(a)
(b)These P-Space characteristics can be used to support real planning of an integrated transport system as shown in [10, 19], with the advantage of modeling a connection between any two bus stops in the same route in random order. The L-Space generates less edges than P-Space, and L-Space preserves the geographical information more than P-Space.


## 5. Methodology Used to CPTS

The chosen method of topological construction and modeling of CPTS is as follows. As discussed in [10], L-Space method does not directly evaluate characteristics like transferring between bus lines, something useful to compare different public transportation systems. Data used here were obtained from Curitiba’s public transportation authority through an agreement signed with the UTFPR (Federal University of Technology of Paraná, Brazil). It involved (N
=
9699) bus stops and 615 bus lines which needed to be filtered out before their use. Here duplicated records (duplicated bus lines) were eliminated. After filtering such data out, a complex network was built using P-Space method with 558,810 edges with the following characteristics and restrictions:(1)
Only static properties of CPTS were considered.
(2)
The bus transport network was described as an undirected graph where the node (bus stop) and the edges represented connections between bus stops according to their bus lines [31].
(3)
All the bus stops (nodes in the built complex network) had unique identifiers and were associated with their geographical location.
(4)
The timetable schedules that each bus should follow to transverse its line were not considered here.
(5)
A bus line was represented by a set of bus stops identifiers that were ordered according to the sequence of bus stops that should be transverse by the bus attending such a line.
(6)
The connections (edges in the complex network) between bus stops could be set for one or more bus lines.
(7)
All the bus lines had unique identifiers.
(8)
At least one bus line was associated with a bus stop.
(9)
All intersections occurred at bus stops that were shared by more than one bus lines.


## 6. Analysis of Properties Based on P-Space Modeling

CPTS was represented as a graphG
=
(
V
,
A
), where V is the set of nodes and A is the set of edges. Mathematically G is a
i
j, an adjacent matrix, which graphically represents a complex network (formed by nodes and edges), which can be seen in Figure 5. It was verified that CPTS is a totally connected complex network, which means that there are no isolated bus lines.Figure 5
Topological structure using complex networks based on P-Space of CPTS.Figure6 shows in detail some bus stops (node) represented by their unique identifier: bus stop (node) NGNP8020 is connected to bus stops (node) NGNP4816 and NGNP4815 by a lines (edges), with degree 2.Figure 6
Magnified view of topological structure of CPTS as a P-Space complex network. Boxes represent CPTS bus stops (nodes) with their associated unique identifiers. The edges are allowed connections between nodes following P-Space method.After modeling CPTS as a complex network, some metrics were calculated in order to characterize it in terms of scale-free or small-world networks.


### 6.1. Degree Distribution (k and k
i)

An edge between two nodes means that there is a direct bus that links them. So the degree of an analyzed bus stop (k
i) represents the number of its reachable bus stops without transferring between bus lines and is described mathematically by (1). The degree of the ith bus stop in P-Space is proportional to the number of lines served by this bus stop [9]:(1)
k
i
=
∑
j
N
a
i
j
.In Figure7, the lowest, the highest, and the average degree (k) of k
i were2,2969,and65.72, respectively. The later result means that approximately65bus stops can be reached from any CPTS bus stop without transferring from the current bus line to the other one.Figure 7
Degree distribution of all CPTS bus stops (nodes). The solid line is a power-law distribution curve best fitted to degree data.It is important to mention that nodes withk
i
=
2 were obtained because there were records of special bus lines in Curitiba’s transportation which are intended to stop only at a single bus stop during late night or whose disembarking does not occur at existing bus stops. The main characteristic of special lines is that they are composed of two interconnected nodes, that is, a graph of two points.The degree distribution in Figure7 also shows that there are around 10 bus stops from which a passenger can reach more than 1000 bus stops without bus transferring. It also shows the high average degree of Curitiba’s bus stops. In terms of type of bus stop, Table 2 shows that two of the ten bus stops with the highest degree are regular bus stops, while others ones are integration terminals. In terms of connectivity these bus stops may have remarkable importance for the CPTS.Table 2
Top 10 bus stops in CPTS with the highest degree.
Tag
Degree (k)
Type of bus stop
Bus stop name
A
2969
Integration terminal
Pinheirinho
B
2945
Integration terminal
Capão Raso
C
2178
Integration terminal
Hauer
D
2075
Integration terminal
Cabral
E
1618
Integration terminal
Campina do Sequeira
F
1603
Integration terminal
Capão da Imbuia
G
1440
Integration terminal
CIC
H
1439
Regular
St. SandroCarlos Sarda, 371-Jardim Amelia
I
1405
Integration terminal
Portão
J
1384
Regular
St. Campos Sales; 842-Juvevê
The tag is used to geographically locate the bus stops in Figure8.Figure8 shows that 50 percent of top 10 bus stops with the highest degree are concentrated in southwestern neighbors in Curitiba. This fact will be discussed later.Figure 8
Map of CPTS bus stops with the highest degree distribution.


### 6.2. Cumulative Degree DistributionP
k
i

In order to reduce large fluctuations, the cumulative distributionP
k
i [1] was also used to describe the degree distribution in P-Space. On the downside, the resulting plot does not give a direct visualization of the degree distribution itself. The cumulative distribution (2) in the P-Space is presented in Figure 9: (2)
P
k
i
=
∑
k
′
=
k
i
∞
p
k
′
.Figure 9
Cumulative degree distribution of the bus stops (node) CPTS under double-logarithmic coordinate scale.Based on Figure9, it is possible to say that the degree of CPTS network does not follow a Poisson distribution (a characteristic of small-world networks) but has a power-law distribution behavior in the log-log plot, growing with a preferential attachment.Many empirical studies have shown that the degree distribution is mostly between a power-law and an exponential decay [32]. The degree distributions of these networks have been described as “having a power-law tail,” “truncated power-law,” “truncated exponential,” “double power-law,” and so forth. These distributions are better described using stretched exponential distribution (SED) as was proposed by Laherrère and Sornette in 1998 [33]. The latter form indicates a linear relation between ln
⁡
ln
⁡
P
k and ln
⁡
k. Obviously, SED degenerates to an exponential distribution when k is close to 1 and to a power-law when k is close to 0. When k is between 0 and 1, the degree distribution is between a power-law and an exponential function. The center region of an empirical distribution in a log-log plot may appear to have a linear part (scale-free region). However, there are typically curvatures in the head and tail parts. The closer the value of k to 0, the wider the scale-free region.Node degree in scale-free networks presents power-law distribution. Such distribution has no peak, most of its nodes have only few connections, and few of its nodes have large amount of connections. Based on analysis of cumulative degree distribution, which showed an approximately straight-line shape on doubly logarithmic scale, CPTS degree distribution resembles a power-law distribution. Therefore Curitiba’s transportation system showed scale-free network behavior.


### 6.3. Average Shortest Path Lengthl

It is calculated from the shortest length between two network nodes since generally there are more than one way to connect them. The average shortest path has the property to reflect the network information efficiency. Mathematically (3) is the average shortest number of steps between all pairs of nodes, where l
i
j is the shortest path between the ith and the jth nodes and V is the number of vertices. In Figure 10, this metric was approximately equal to3.37. It means that any bus stop in the CPTS can be reached from any other bus stop by changing bus 3.37
-
1
=
2.37 times on average:(3)
l
=
2
∗
∑
i
<
j
l
i
j
V
∗
V
-
1
.Figure 10
Average shortest path length distribution of the CPTS.


### 6.4. Cluster Coefficientc

It refers to the number of connections between the closest neighbors of theith node. It has the property of characterizing the local cohesiveness of the ith node or how the network nodes are clustered [2]. This metric reflects how easily passengers can move between the ith bus stop and its neighbor ones possibly transferring between bus lines. It is calculated from (4) where k
i is degree of the ith node and g
i is the number of connections between its neighbors. The average clustering coefficient of the entire network is described as (5). The resulting average for PTS was0.809:(4)
c
i
=
2
g
i
k
i
k
i
-
1
,
(5)
c
=
1
N
∑
i
=
1
N
c
i
.It has been shown [8] that the clustering coefficient in the P-Space decays linearly with the logarithm of degree for large k
i and is almost constant and close to unity for small k
i. Here, Figure 11 shows this dependency which can be described by a power-law distribution. It is mentioned [10] that all bus stops belonging to a complete subgraph of a single bus line have c
i
=
1 while c
i generally decreases if the ith bus stop belongs to more than one bus line. This indicates that the clustering coefficient of a node is strongly correlated with the node degree in public transport network. As k
i grows, the relationship between c
k
i, the average clustering coefficient of nodes with degree k
i, and k
i approximates to a power-law distribution; that is,(6)
c
k
i
~
k
i
-
α
.In CPTS’s case, α
=
0.74.Figure 11
Distribution of average clustering coefficient of nodes with degreek
i
-
c
k
i, clustering-degree correlations, of CPTS network in P-Space. The solid line is a power-law distribution curve best fitted to degree data.


### 6.5. Community StructureQ

It is possible to find communities inV-edges complex networks with few edges between the communities themselves [34]. The metric aims to detect the summation of the weights of intercommunity and intracommunity edges. In CPTS187communities were found. For the sake of comparison, the amount of Curitiba city neighborhoods was only75[17]. In many complex networks, communities can be defined hierarchically. When there are communities inside other communities, the concept of modularity is used to obtain the quality of such a hierarchical division in the community structure: higher modularity means stronger interconnections in the community structure. Newman and Girvan [35] proposed the measure of modularity Q described by (7). For a division with g groups, it defines a matrix E
g
×
g, where e
i
j is the fraction of edges in the original network that connect vertices in the ith group to those in the jth group. So for Q
=
0 a network is formed of disconnected modules and for higher Q the network presents modular structures. Values of Q close to1 (maximum possible value) indicate strong community structure. Typically Q varies from0.3to0.7while higher values are rare [35].Due to the large number of detected communities, CPTS modularity wasQ
=
0.676, which indicates a strong community structure:(7)
Q
=
∑
i
e
i
i
-
∑
i
j
k
e
i
j
e
k
i
.According to [35], the property that seems to be common to many networks is community structure (dense intergroup and sparse intragroup node connections).Based on the result, the CPTS has the same characteristic of different complex systems that can overlap and interfere with each other in real-life, forming a network of networks. So in CPTS it is possible to say that individual network is one component within a much larger complex network of networks. As technology has advanced, coupling between networks has become increasingly strong. Node failures in one network will cause the failure of dependent nodes in other networks and vice versa based on the strong community structure noticed from the CPTS data. This recursive process can lead to a cascade of failures throughout the network of networks system.Such is also the case in network theory, where the study of isolated single networks brings extremely limited results; real-world noninteracting systems are extremely rare in both classical physics and network study. Most real-world network systems continuously interact with other networks, especially since modern technology has accelerated network interdependency.To adequately model most real-world systems, understanding the interdependence of networks and effect of this interdependence on the structural and functional behavior of the coupled system is crucial. Introducing coupling between networks is analogous to the introduction of interactions between particles in statistical physics, which allowed physicists to understand the cooperative behavior of such rich phenomena as phase transitions. Surprisingly, recent results on mathematical models [36] show that analyzing complex systems as a network of coupled networks may alter the basic assumptions that network theory has relied on for single networks.


### 6.6. Closeness Centrality (c
c)

It measures how close a node is from the other ones in a network. It is the inverse of the sum of the shortest distances between each node and all other nodes as described in(8)
c
c
i
=
∑
j
d
i
j
-
1
=
1
∑
j
d
i
j
,where i is the central node, j is another node (i
≠
j), and d
i
j is the shortest distance between both nodes. The nodes with high closeness centrality are central in the network because they are close to most other nodes, while nodes with low closeness centrality are remote in the network [35]. According to Table 3 and Figures 12 and 13, 10 main bus stops of CPTS presented the shortest distance to any other bus stops since they presented the highest closeness centrality.Table 3
Top 10 bus stops and their respective bus lines based on the highest closeness centrality.
Alias
Value
Type of bus stop
Bus stop name
A
0.4410788
Integration terminal
Cabral
B
0.43344954
Integration terminal
Capão Raso
C
0.41930044
Integration terminal
Pinheirinho
D
0.41579488
Integration terminal
Fazendinha
E
0.41356078
Integration terminal
Santa Cândida
F
0.41196212
Integration terminal
Portão
G
0.40734208
Integration terminal
Hauer
H
0.4061649
Integration terminal
CIC
I
0.4061649
Integration terminal
Maracanã
J
0.40094262
Integration terminal
Bairro Alto
The alias identifier is used to geographically locate the bus stops in Figure13.Figure 12
Closeness centrality of CPTS.Figure 13
Map of CPTS bus stops with the highest closeness centrality or how close a bus stop is from the other ones.It is important to mention that all of the bus stops shown in Table3 are an integration terminal. Notably the largest bus flows were concentrated in integration terminals. Figure 12 shows that 60 percent of top 10 bus stops with the highest closeness centrality are concentrated in Southwestern Curitiba, the same behavior previously exhibited by the top 10 bus stops with the highest degree.


### 6.7. Betweenness Centrality (c
b)

This centrality measurement is a very interesting quantity which characterizes the importance of a node in the network. The more central the node, the larger the number of shortest paths going through this node [37]. The metric can also be used to identify the nodes with high congestion [38, 39]. It can be defined for the ith node by the sum of the fraction of all pairs of shortest paths which passes through the ith node as shown in (9). Figures 14 and 15 and Table 4 show the obtained results for CPTS:(9)
c
b
i
=
∑
j
≠
k
σ
j
k
i
σ
j
k
,where σ
j
k
i means the number of shortest paths from the jth bus stop to the kth bus stop and σ
j
k is the number of those that pass through the ith bus stop.Table 4
Bus stops and their respective bus lines based on the betweenness centrality.
Alias
Value
Type of bus stop
Bus stop name
A
1.1264549E7
Integration terminal
Pinheirinho
B
8512526.0
Integration terminal
Capão raso
C
7870579.0
Integration terminal
Cabral
D
6025762.0
Integration terminal
Campo Comprido
E
5832170.5
Integration terminal
Pinhais
F
5832170.5
Integration terminal
Santa Felicidade
G
4138122.2
Integration terminal
Guaraituba
H
4063932.8
Integration terminal
Maracanã
I
3352379.2
Integration terminal
Hauer
J
3039188.2
Integration terminal
Campina do Siqueira
The alias identifier is used to geographically locate the bus stops in Figure15.Figure 14
Betweenness centrality of CPTS.Figure 15
Map of CPTS bus stops with the highest betweenness centrality or the highest potential for bus congestion.From the results of betweenness centrality analysis summarized in Table4, it was possible to determine the bus stops with higher potential for bus congestion, which could be critical for CPTS. All the bus stops in the Table 4 are integration terminals.Figure15 shows 10 bus stops in the metropolitan region served by CPTS. Doing an analysis in accordance with [38, 39], the bus stops A and B in Table 4 are those with the highest potential for bus congestion based on betweenness centrality. Geographically, Figure 15 also shows that bus stops are spread along the city. It is noteworthy that none of the bus stops in Table 4 were located in downtown area.


## 6.1. Degree Distribution (k and k
i)

An edge between two nodes means that there is a direct bus that links them. So the degree of an analyzed bus stop (k
i) represents the number of its reachable bus stops without transferring between bus lines and is described mathematically by (1). The degree of the ith bus stop in P-Space is proportional to the number of lines served by this bus stop [9]:(1)
k
i
=
∑
j
N
a
i
j
.In Figure7, the lowest, the highest, and the average degree (k) of k
i were2,2969,and65.72, respectively. The later result means that approximately65bus stops can be reached from any CPTS bus stop without transferring from the current bus line to the other one.Figure 7
Degree distribution of all CPTS bus stops (nodes). The solid line is a power-law distribution curve best fitted to degree data.It is important to mention that nodes withk
i
=
2 were obtained because there were records of special bus lines in Curitiba’s transportation which are intended to stop only at a single bus stop during late night or whose disembarking does not occur at existing bus stops. The main characteristic of special lines is that they are composed of two interconnected nodes, that is, a graph of two points.The degree distribution in Figure7 also shows that there are around 10 bus stops from which a passenger can reach more than 1000 bus stops without bus transferring. It also shows the high average degree of Curitiba’s bus stops. In terms of type of bus stop, Table 2 shows that two of the ten bus stops with the highest degree are regular bus stops, while others ones are integration terminals. In terms of connectivity these bus stops may have remarkable importance for the CPTS.Table 2
Top 10 bus stops in CPTS with the highest degree.
Tag
Degree (k)
Type of bus stop
Bus stop name
A
2969
Integration terminal
Pinheirinho
B
2945
Integration terminal
Capão Raso
C
2178
Integration terminal
Hauer
D
2075
Integration terminal
Cabral
E
1618
Integration terminal
Campina do Sequeira
F
1603
Integration terminal
Capão da Imbuia
G
1440
Integration terminal
CIC
H
1439
Regular
St. SandroCarlos Sarda, 371-Jardim Amelia
I
1405
Integration terminal
Portão
J
1384
Regular
St. Campos Sales; 842-Juvevê
The tag is used to geographically locate the bus stops in Figure8.Figure8 shows that 50 percent of top 10 bus stops with the highest degree are concentrated in southwestern neighbors in Curitiba. This fact will be discussed later.Figure 8
Map of CPTS bus stops with the highest degree distribution.


## 6.2. Cumulative Degree DistributionP
k
i

In order to reduce large fluctuations, the cumulative distributionP
k
i [1] was also used to describe the degree distribution in P-Space. On the downside, the resulting plot does not give a direct visualization of the degree distribution itself. The cumulative distribution (2) in the P-Space is presented in Figure 9: (2)
P
k
i
=
∑
k
′
=
k
i
∞
p
k
′
.Figure 9
Cumulative degree distribution of the bus stops (node) CPTS under double-logarithmic coordinate scale.Based on Figure9, it is possible to say that the degree of CPTS network does not follow a Poisson distribution (a characteristic of small-world networks) but has a power-law distribution behavior in the log-log plot, growing with a preferential attachment.Many empirical studies have shown that the degree distribution is mostly between a power-law and an exponential decay [32]. The degree distributions of these networks have been described as “having a power-law tail,” “truncated power-law,” “truncated exponential,” “double power-law,” and so forth. These distributions are better described using stretched exponential distribution (SED) as was proposed by Laherrère and Sornette in 1998 [33]. The latter form indicates a linear relation between ln
⁡
ln
⁡
P
k and ln
⁡
k. Obviously, SED degenerates to an exponential distribution when k is close to 1 and to a power-law when k is close to 0. When k is between 0 and 1, the degree distribution is between a power-law and an exponential function. The center region of an empirical distribution in a log-log plot may appear to have a linear part (scale-free region). However, there are typically curvatures in the head and tail parts. The closer the value of k to 0, the wider the scale-free region.Node degree in scale-free networks presents power-law distribution. Such distribution has no peak, most of its nodes have only few connections, and few of its nodes have large amount of connections. Based on analysis of cumulative degree distribution, which showed an approximately straight-line shape on doubly logarithmic scale, CPTS degree distribution resembles a power-law distribution. Therefore Curitiba’s transportation system showed scale-free network behavior.


## 6.3. Average Shortest Path Lengthl

It is calculated from the shortest length between two network nodes since generally there are more than one way to connect them. The average shortest path has the property to reflect the network information efficiency. Mathematically (3) is the average shortest number of steps between all pairs of nodes, where l
i
j is the shortest path between the ith and the jth nodes and V is the number of vertices. In Figure 10, this metric was approximately equal to3.37. It means that any bus stop in the CPTS can be reached from any other bus stop by changing bus 3.37
-
1
=
2.37 times on average:(3)
l
=
2
∗
∑
i
<
j
l
i
j
V
∗
V
-
1
.Figure 10
Average shortest path length distribution of the CPTS.


## 6.4. Cluster Coefficientc

It refers to the number of connections between the closest neighbors of theith node. It has the property of characterizing the local cohesiveness of the ith node or how the network nodes are clustered [2]. This metric reflects how easily passengers can move between the ith bus stop and its neighbor ones possibly transferring between bus lines. It is calculated from (4) where k
i is degree of the ith node and g
i is the number of connections between its neighbors. The average clustering coefficient of the entire network is described as (5). The resulting average for PTS was0.809:(4)
c
i
=
2
g
i
k
i
k
i
-
1
,
(5)
c
=
1
N
∑
i
=
1
N
c
i
.It has been shown [8] that the clustering coefficient in the P-Space decays linearly with the logarithm of degree for large k
i and is almost constant and close to unity for small k
i. Here, Figure 11 shows this dependency which can be described by a power-law distribution. It is mentioned [10] that all bus stops belonging to a complete subgraph of a single bus line have c
i
=
1 while c
i generally decreases if the ith bus stop belongs to more than one bus line. This indicates that the clustering coefficient of a node is strongly correlated with the node degree in public transport network. As k
i grows, the relationship between c
k
i, the average clustering coefficient of nodes with degree k
i, and k
i approximates to a power-law distribution; that is,(6)
c
k
i
~
k
i
-
α
.In CPTS’s case, α
=
0.74.Figure 11
Distribution of average clustering coefficient of nodes with degreek
i
-
c
k
i, clustering-degree correlations, of CPTS network in P-Space. The solid line is a power-law distribution curve best fitted to degree data.


## 6.5. Community StructureQ

It is possible to find communities inV-edges complex networks with few edges between the communities themselves [34]. The metric aims to detect the summation of the weights of intercommunity and intracommunity edges. In CPTS187communities were found. For the sake of comparison, the amount of Curitiba city neighborhoods was only75[17]. In many complex networks, communities can be defined hierarchically. When there are communities inside other communities, the concept of modularity is used to obtain the quality of such a hierarchical division in the community structure: higher modularity means stronger interconnections in the community structure. Newman and Girvan [35] proposed the measure of modularity Q described by (7). For a division with g groups, it defines a matrix E
g
×
g, where e
i
j is the fraction of edges in the original network that connect vertices in the ith group to those in the jth group. So for Q
=
0 a network is formed of disconnected modules and for higher Q the network presents modular structures. Values of Q close to1 (maximum possible value) indicate strong community structure. Typically Q varies from0.3to0.7while higher values are rare [35].Due to the large number of detected communities, CPTS modularity wasQ
=
0.676, which indicates a strong community structure:(7)
Q
=
∑
i
e
i
i
-
∑
i
j
k
e
i
j
e
k
i
.According to [35], the property that seems to be common to many networks is community structure (dense intergroup and sparse intragroup node connections).Based on the result, the CPTS has the same characteristic of different complex systems that can overlap and interfere with each other in real-life, forming a network of networks. So in CPTS it is possible to say that individual network is one component within a much larger complex network of networks. As technology has advanced, coupling between networks has become increasingly strong. Node failures in one network will cause the failure of dependent nodes in other networks and vice versa based on the strong community structure noticed from the CPTS data. This recursive process can lead to a cascade of failures throughout the network of networks system.Such is also the case in network theory, where the study of isolated single networks brings extremely limited results; real-world noninteracting systems are extremely rare in both classical physics and network study. Most real-world network systems continuously interact with other networks, especially since modern technology has accelerated network interdependency.To adequately model most real-world systems, understanding the interdependence of networks and effect of this interdependence on the structural and functional behavior of the coupled system is crucial. Introducing coupling between networks is analogous to the introduction of interactions between particles in statistical physics, which allowed physicists to understand the cooperative behavior of such rich phenomena as phase transitions. Surprisingly, recent results on mathematical models [36] show that analyzing complex systems as a network of coupled networks may alter the basic assumptions that network theory has relied on for single networks.


## 6.6. Closeness Centrality (c
c)

It measures how close a node is from the other ones in a network. It is the inverse of the sum of the shortest distances between each node and all other nodes as described in(8)
c
c
i
=
∑
j
d
i
j
-
1
=
1
∑
j
d
i
j
,where i is the central node, j is another node (i
≠
j), and d
i
j is the shortest distance between both nodes. The nodes with high closeness centrality are central in the network because they are close to most other nodes, while nodes with low closeness centrality are remote in the network [35]. According to Table 3 and Figures 12 and 13, 10 main bus stops of CPTS presented the shortest distance to any other bus stops since they presented the highest closeness centrality.Table 3
Top 10 bus stops and their respective bus lines based on the highest closeness centrality.
Alias
Value
Type of bus stop
Bus stop name
A
0.4410788
Integration terminal
Cabral
B
0.43344954
Integration terminal
Capão Raso
C
0.41930044
Integration terminal
Pinheirinho
D
0.41579488
Integration terminal
Fazendinha
E
0.41356078
Integration terminal
Santa Cândida
F
0.41196212
Integration terminal
Portão
G
0.40734208
Integration terminal
Hauer
H
0.4061649
Integration terminal
CIC
I
0.4061649
Integration terminal
Maracanã
J
0.40094262
Integration terminal
Bairro Alto
The alias identifier is used to geographically locate the bus stops in Figure13.Figure 12
Closeness centrality of CPTS.Figure 13
Map of CPTS bus stops with the highest closeness centrality or how close a bus stop is from the other ones.It is important to mention that all of the bus stops shown in Table3 are an integration terminal. Notably the largest bus flows were concentrated in integration terminals. Figure 12 shows that 60 percent of top 10 bus stops with the highest closeness centrality are concentrated in Southwestern Curitiba, the same behavior previously exhibited by the top 10 bus stops with the highest degree.


## 6.7. Betweenness Centrality (c
b)

This centrality measurement is a very interesting quantity which characterizes the importance of a node in the network. The more central the node, the larger the number of shortest paths going through this node [37]. The metric can also be used to identify the nodes with high congestion [38, 39]. It can be defined for the ith node by the sum of the fraction of all pairs of shortest paths which passes through the ith node as shown in (9). Figures 14 and 15 and Table 4 show the obtained results for CPTS:(9)
c
b
i
=
∑
j
≠
k
σ
j
k
i
σ
j
k
,where σ
j
k
i means the number of shortest paths from the jth bus stop to the kth bus stop and σ
j
k is the number of those that pass through the ith bus stop.Table 4
Bus stops and their respective bus lines based on the betweenness centrality.
Alias
Value
Type of bus stop
Bus stop name
A
1.1264549E7
Integration terminal
Pinheirinho
B
8512526.0
Integration terminal
Capão raso
C
7870579.0
Integration terminal
Cabral
D
6025762.0
Integration terminal
Campo Comprido
E
5832170.5
Integration terminal
Pinhais
F
5832170.5
Integration terminal
Santa Felicidade
G
4138122.2
Integration terminal
Guaraituba
H
4063932.8
Integration terminal
Maracanã
I
3352379.2
Integration terminal
Hauer
J
3039188.2
Integration terminal
Campina do Siqueira
The alias identifier is used to geographically locate the bus stops in Figure15.Figure 14
Betweenness centrality of CPTS.Figure 15
Map of CPTS bus stops with the highest betweenness centrality or the highest potential for bus congestion.From the results of betweenness centrality analysis summarized in Table4, it was possible to determine the bus stops with higher potential for bus congestion, which could be critical for CPTS. All the bus stops in the Table 4 are integration terminals.Figure15 shows 10 bus stops in the metropolitan region served by CPTS. Doing an analysis in accordance with [38, 39], the bus stops A and B in Table 4 are those with the highest potential for bus congestion based on betweenness centrality. Geographically, Figure 15 also shows that bus stops are spread along the city. It is noteworthy that none of the bus stops in Table 4 were located in downtown area.


## 7. CPTS Compared with Other Cities

The results for CPTS were compared with those obtained for other Chinese cities [10] (Shanghai, Beijing, and Guangzhou) and Polish cities [8] (GOP, Warszawa, and Łódź). Their public transportation systems were also evaluated through P-Space complex networks.Humphries et al. [40] introduced a quantitative metric—the small-world coefficient σ—which uses the ratio of network clustering to the average shortest path length, both calculated from the studied complex network (c and l) and an equivalent random network (c
r
a
n
d and l
r
a
n
d). Then their ratios are used to calculate the small-world coefficient as (10)
σ
=
c
/
c
r
a
n
d
l
/
l
r
a
n
d
=
γ
λ
.The conditions that must be met for a network to be classified as small-world one arel
≥
l
r
a
n
d
(or
l
≈
l
r
a
n
d) and c
≫
c
r
a
n
d which results in σ
>
1 [40]. In case of CPTS, l
r
a
n
d
=
1.95, c
r
a
n
d
=
0.0050, and σ
=
4.86, which means that CPTS should be classified as a small-world network according to [40]. Analyzing only c and l would classify CPTS as a small-world network since CPTS presented shorter average path length and higher clustering coefficient. However only few bus stops had high degree (according to Figure 7), which is a characteristic of scale-free networks considering [19, 31]. Therefore, this mixing behavior (CPTS being classified as both small-world and scale-free network) seemed to happen in transportation systems of both Chinese and Polish cities (Table 5). k is intended to show how many bus stops can be reached from a given bus stop without transferring between bus lines. In Curitiba the values of k and c indicated that Curitiba had good transportation performance. Particularly the value of c obtained for Curitiba showed a very sparse network, the same behavior observed in [19]. However l was worse in CPTS when compared to other cities, except Shanghai. It is possible to infer that Curitiba city planners tried to compensate such a situation by increasing the number of bus lines that did not have a hub as a bus stop (based on the analysis they could be the integration terminals listed on Table 4), making “short cuts” across the city. It amplified the small-world characteristic of Curitiba transportation system. Since the amount of bus stops in Curitiba, Shanghai, and Beijing is quite close, it is possible to infer that CPTS had better performance if their population size was considered in a comparative analysis: Curitiba transportation system had higher number of bus stops by population, higher c, and lower k, and lower population than Chinese and Polish cities. Therefore, through these metrics, Curitiba may have better public transportation system in comparison to [8, 10].Table 5
Statistical parameters of public transportation networks.
City
r
bs
p
k
l
c
Curitiba - CPTS
615
9699
3800
65.72
3.37
0.809
Shanghai
1641
9502
22000
44.40
3.45
0.772
Beijing
1714
9361
19000
92.54
3.00
0.754
Guangzhou
1256
3891
11000
75.58
3.13
0.750
GOP
1412
2811
2100
68.42
2.90
0.760
Warszawa
494
1530
1615
90.93
2.42
0.691
Łódź
294
1023
800
59.79
2.45
0.721
r: routes or bus lines; bs: number of bus stops; k: average degree; l: average path length; c: clustering coefficient; p: city population in thousands of inhabitants based on [12, 17, 18].


## 8. Conclusions

Here a P-Space representation of Curitiba’s bus-based public transportation enabled the analysis of the main topological static properties of CPTS: the betweenness and closeness centrality. Through P-Space modeling, it was feasible to say that accessibility in CPTS was good due to its bus stops distribution (number of bus stops/number of bus lines). This was emphasized by examining the complex network results along with the geographic position of the bus stops. Also the mobility was considered better than Chinese and Polish cities because any of its destination bus stop could be reached by any other65.72bus stops (on average) located in metropolitan area (include bus stops located far from downtown). A comparative analysis of the results from [8, 10] was carried out and showed that CPTS has characteristics of both scale-free and small-world networks, which is a behavior encountered in the bus transportation networks. Since CPTS has also high modularity, it is possible to consider it as a scale-free network (hub-based network) with small-world characteristics and hierarchical structures built up around its hubs. These statistical results are similar to features observed in other transport networks (underground, railway, or airline systems) [9, 27–31] where such networks tend to share small-world characteristics. It is possible to speculate that bus transportation system of other cities with comparable population and transportation infrastructure can be modeled as complex networks with mixing characteristics. Particularly for Curitiba and based on the results of Tables 2, 3, and 4 (the top 10 bus stops with the highest degree, closeness centrality, and betweenness centrality) the integration terminals named as “Pinheirinho,” “Capão Raso,” and “Cabral” (all located in Southwestern Curitiba) are the most important bus stops and these are the main hubs of the Curitiba transportation system. It is possible to say that these points focus much on CPTS congestion flow. Based on this congestion the city planners could use this high flow congestion information to improve the infrastructure of these terminals.Thus it can be said that in case of possible failure in one of these three integration terminals network could suffer large impact which would compromise the entire public transportation system. Also the location of the most important bus stops in the system identified by this complex network analysis showed that the north-south lines seemed to be the main lines of the CPTS in comparison with the east-west lines. It could be explained by population density distribution across the city or their social level distribution. City planners could use such information in order, for example, to verify the causes for such an unbalance in north-south lines in comparison to east-west lines.With the results of Table2 city planners may replan the bus stops “H” and “J,” promoting them to integration terminals, enabling better quality.Finally, the presented results from P-Space modeling of CPTS could be used as reference and guidance to explore the mechanism of evolution and modeling Curitiba’s urban public transport both statically or dynamically, and through this model planners can view clearly and objectively the main characteristics of networks, but only through empirical knowledge.Future works will address the effect of other variables (like travel time, bus line capacity, and time schedule) to evaluate their influence on complex network modeling of transportation systems and also evaluate how changes and possible failures in Curitiba transportation system affect the complex network metrics.



---

*Source: 3898762-2016-06-22.xml*