=Paper=
{{Paper
|id=Vol-2170/paper8
|storemode=property
|title=A Multilayer and Time-Varying Structural Analysis of the Brazilian Air Transportation Network
|pdfUrl=https://ceur-ws.org/Vol-2170/paper8.pdf
|volume=Vol-2170
|authors=Klaus Wehmuth,Bernardo Costa,Joao Victor Bechara,Artur Ziviani
|dblpUrl=https://dblp.org/rec/conf/vldb/WehmuthCBZ18
}}
==A Multilayer and Time-Varying Structural Analysis of the Brazilian Air Transportation Network==
https://ceur-ws.org/Vol-2170/paper8.pdf
LADaS 2018 - Latin America Data Science Workshop
A Multilayer and Time-varying Structural Analysis of the
Brazilian Air Transportation Network ⇤
Klaus Wehmuth, Bernardo B. A. Costa,
João Victor M. Bechara, Artur Ziviani
1
National Laboratory for Scientific Computing (LNCC)
Av. Getúlio Vargas, 333, Quitandinha – CEP 25651-075 – Petrópolis, RJ – Brazil
{klaus, bantunes,joaovmb,ziviani}@lncc.br
Abstract. This paper provides a multilayer and time-varying structural analysis
of one air transportation network, having the Brazilian air transportation net-
work as a case study. Using a single mathematical object called MultiAspect
Graph (MAG) for this analysis, the multi-layer perspective enables the unveil-
ing of the particular strategies of each airline to both establish and adapt in a
moment of crisis its specific flight network.
1. Introduction
Recent analyses of the Brazilian domestic air transportation network focused on flight
delay analysis [Sternberg et al. 2016] or aggregated structural analysis of the net-
work [Couto et al. 2015]. Such recent structural analysis of the Brazilian domestic air
transportation network [Couto et al. 2015], as well as the global air transportation net-
work [Verma et al. 2014, Wei et al. 2014], were elaborated using aggregated network
graphs, containing basically information about airports (localities) and routes (links be-
tween airports). This type of analysis disregards the temporal information of scheduling
of flights, making information about connecting flights (i.e. network paths) not reliable,
since no time information is available to the flights. Therefore, in these network models,
it is not possible to guarantee the time sequence of the connecting flights, since there is
no temporal information in the route graph. The aggregated view of the air transportation
network also conceals the structural subnetwork of each one of the airline companies, thus
being oblivious to the particular strategies adopted by each company when defining their
specific air transportation network.
In this paper, we analyze the Brazilian domestic air transportation network in such
a way that all time scheduling information is preserved. Furthermore, information iden-
tifying the company of each flight is also made available, so that the network may be
studied as a whole, or using different perspectives such as views from independent air-
line companies, used routes, and performed flights. In contrast, previous work typically
focused on a single aspect of the concerned flight network, such as the aggregated struc-
ture [Couto et al. 2015], the multilayer perspective [Tsiotas and Polyzos 2015], or a prop-
erty of the network such as flight delays [Sternberg et al. 2016].
This paper is organized as follows. Section 2 describes our methodology. Sec-
tion 3 analyzes the results. Finally, in Section 4, we conclude the paper.
⇤
In [Couto et al. 2015], an extended version of this paper is presented as a research report no. 6/2018 at
the National Laboratory for Scientific Computing (LNCC)
57
LADaS 2018 - Latin America Data Science Workshop
2. Methodology
In this section, we describe the methods and tools that we use in the model construction
as well as to obtain the results presented in this article.
2.1. MAG
MultiAspect Graph (MAG) [Wehmuth et al. 2016] is a graph generalization that can rep-
resent high-order networks, such as multi-layer, time-varying, or time-varying multi-layer
complex networks, and so on. In this context, an aspect is an independent feature of the
complex networked system to be modeled, such as localities, layers, and time instants.
One of the key characteristics of a MAG is to be isomorphic to a directed graph and a
companion tuple [Wehmuth et al. 2017]. In this way, with a MAG, it is possible to apply
the already available knowledge from graph theory for analyzing directed graphs directly
into the MAG environment.
In this work, we model the Brazilian air transportation network as a network com-
posed of localities (airports), layers (corresponding to the individual air transportation
network of each airline company), and time instants. However, the results obtained are
expressed only regarding locations (airports) and their links (routes). The achieved results
take into account the time and layer structure of the model to respect the time sequence
of available flights as well as the operating boundaries between different airlines.
2.2. K-Core
In our analysis, we use the K-Core algorithm [Seidman 1983] to identify the network core.
The K-Core of a network is obtained through a continuous decomposition of the network
that removes all vertices with connectivity lower than the value of k and their respective
connections. For example, eliminating all vertices of degree 1, the result is a core with
vertices with at least degree 2. The resulting graph in this case is the 2-core. Increasing
the value of k, the final round of the algorithm happens when it is impossible to eliminate
more vertices, in other words, the network with (k+1)-core is empty. In other words, in
this case, the maximum K-Core is achieved. Note that for two cores to be considered
equal they must be composed of the same vertices and edges, i.e., they must have the
vertices linked by the same topological structure.
By adopting the K-Core algorithm to analyze the air transportation network, the
intent in this paper is to focus on a structural analysis of the most relevant vertices of
the Brazilian air transportation network (i.e., those that compose the core of the network)
under different perspectives as discussed in Section 3.
3. Results
This section presents the adopted datasets corresponding to the Brazilian air transportation
network in two different periods of time and the structural analysis of this network taking
into account different viewpoints, such as time-varying and multilayer perspectives.
3.1. Model construction
To represent the Brazilian domestic air transportation network, we use two flight sched-
ules: one from June 3, 2015, and the other from May 13, 2016, both published by the
National Civil Aviation Agency (ANAC) on its website. These schedule tables contain
58
LADaS 2018 - Latin America Data Science Workshop
information about domestic, international, postal, and cargo flights covering a period of
one week. We extract from these tables the information about domestic commercial pas-
senger flights, the target of this paper, on both periods (2015 and 2016), separated by
approximately 11 months.
The MAG-based model proposed in this paper to analyze the Brazilian air trans-
portation network has four aspects: airports, airlines, flight time instants, and the time
period of the dataset. The first aspect contains all airports in Brazil that had at least one
flight registered in the week each dataset refers to. There are 110 and 109 airports in
the 2015 and in the 2016 dataset, respectively. The second aspect contains all the air-
line companies. In the 2015 dataset, there are seven airlines (Azul, Avianca, Gol, Map,
Passaredo, Tam, and Sete). In the 2016 dataset, there are eight airlines (Azul, Avianca,
Gol, Map, Passaredo, Tam, and Sete). We focus our structural analysis on the four largest
airline companies, namely Gol, TAM, Azul, and Avianca, as they together concentrate
more than 90% of the routes between airports and 95% of the flights that use these routes
in the Brazilian domestic air transportation network.
To ease the modeling, we create two layers for each airline: The first layer repre-
sents the actual flights and the second layer represents the possible connections between
flights, resulting in fourteen layers for the first dataset and in sixteen layers for the second
one. In the third aspect, there is information about all the flight times, in minutes, in a
week. The forth aspect identifies the corresponding time period of the dataset: The value
one is used for the 2015 dataset and the value two for the 2016 dataset.
(a) July 2015 (b) May 2016
Figure 1. Brazilian domestic air transportation network.
3.2. Comparison of the Brazilian air transportation network: 2015 x 2016
The severe economic crisis in Brazil in 2016 directly impacted several sectors of the
economy, making them to adapt to the new reality. In this context, civil aviation was no
exception, and there has been an adjustment on the part of the airline companies in their
availability of flights, resulting in a change in the Brazilian domestic air transportation
network from 2015 to 2016 that we start analyzing in this section. Figure 1 shows the full
Brazilian air transportation network for both the 2015 and 2016 datasets, sub-determined
to show only the first MAG aspect, i.e., the locations (airports). In this representation, a
59
LADaS 2018 - Latin America Data Science Workshop
Table 1. Number of served airports in the Brazilian air transportation network.
Company # Airports in 2015 # Airports in 2016 Difference (%)
Gol 56 53 -5
Azul 100 94 -6
TAM 43 46 +7
Avianca 23 24 +4
Table 2. Number of routes in the Brazilian air transportation network.
Company # Routes in 2015 # Routes in 2016 Difference (%)
Gol 324 242 -25
Azul 454 377 -17
TAM 250 234 -6
Avianca 102 109 +6
Total 1130 962 -15
vertex is an airport and an edge is a route between two airports. Table 1 shows the num-
ber of served airports by each airline in the Brazilian air transportation network in 2015
and 2016. There are some slight changes with some airlines serving less airports while
others started serving more airports. imposing changes in the Brazilian air transportation
network. We here analyze not only the changes in the number of served airports, but most
importantly we analyze how these airports are served in terms of routes between them
and also in terms of the number of flights using these routes. In particular, we show that
changes are in general more significant when taking those perspectives into account.
Table 2 shows a reduction of 15% in the number of routes of the main airlines
in the Brazilian air transportation network between June 2015 and May 2016. The three
largest airlines in the country (Gol, Azul, and TAM) had significant reductions in their
number of routes, specially Gol with a 25% decrease in the number of routes in the time
period. Nevertheless, Avianca increased the number of routes by 6%, showing that it
took advantage of the route reduction made by larger airlines to occupy some niches and
expand. Therefore, the average growth of smaller companies in times of crisis is their
strategy to partially fill the gaps in routes left by larger companies.
Furthermore, Table 3 shows the difference in the number of flights between June
2015 and May 2016, indicating a 20% decrease in the number of flights. In general, the
changes in the number of flights follow a similar trend as in the change in the number of
routes, but the intensity of the increase or reduction in the number of flights is even larger
in the extreme cases. Considering the number of flights, for instance, Gol had a decrease
of 37%, whereas Avianca had an increase of 13% in their number of flight, suggesting
that the intensity that the airline companies use the route by offering more or less flights
along a week in each route also represents a change in another dimension.
Additionally, codesharing is regularly used to optimize occupation in flights on
low volume routes. Considering the analyzed datasets, the number of cases of codeshar-
ing went from 923 to 1234 flights per week, an increase of about 33%. This strategy
60
LADaS 2018 - Latin America Data Science Workshop
Table 3. Number of flights in the Brazilian air transportation network.
Company # Flights in 2015 # Flights in 2016 Difference (%)
Gol 6644 4188 -37
Azul 5839 5075 -13
TAM 4814 4158 -14
Avianca 1386 1561 +13
Total 18683 14982 -20
virtually keeps a declared flight active in a per airline view, but it actually represents a
reduction in the number of real flights on air.
3.3. Digraph analysis: The route-based perspective
A digraph is a simple directed graph. In our context, a digraph represents the existing
routes between the airports, disregarding how busy each route is (i.e., how many daily
flights compose the route). We first analyze the Brazilian air transportation network with
the digraph format. In contrast to [Couto et al. 2015], which also uses the digraph ap-
proach, we apply the K-Core methodology to the Brazilian air transportation network.
Moreover, we also apply such a methodology to the flight network of each airline com-
pany, allowing a number of different analyses concerning the structure of the network at
its basic core structure. These properties of the Brazilian air transportation network were
analyzed in two different time periods (2015 and 2016). The resulting central core of the
flight network of each airline company indicates the key airports for each company, thus
unveiling the strategy of each company in defining its flight network. Therefore, the ob-
tained information with the K-Core methodology allows the analysis of the concentration
of the activities of each airline, a comparison of the strategies taken by the companies,
and the identification of the hubs of the companies.
First, we analyze the connectivity of the maximum K-Core in the digraph corre-
sponding to the whole Brazilian air transportation network, thus focusing on the structural
analysis of the basic core of the flight network. Figure 2 shows the geo-referenced K-Core
of the digraph corresponding to the route-based perspective of the complete Brazilian air
transportation network, as indicated by the 2015 and 2016 dataset. The 2015 core network
results from the maximum K-Core with K=18, 17 airports, and 196 routes. Similarly, the
2016 core network results from the maximum K-Core with K=18, 16 airports, and 182
routes. As it could be expected, the south and southeast regions, which present the largest
share in Brazil’s economy, are also the regions that compose the central core of the air
transportation network, with a small trend of even stronger concentration in 2016.
We now consider the connectivity of the maximum K-Core in the digraph cor-
responding to the flight network of each of the four main airline companies in Brazil.
Table 4 shows the maximum core number K as well as the number of airports and routes
in the maximum K-Core of each of the main airline companies, both in June 2015 and
May 2016. The maximum core number K of all airlines remained the same between the
two time periods, although the number of airports and routes in the maximum core of the
main airline companies has been significantly reduced, except for Avianca, which kept
the same core. This indicates that the main airlines have significantly reduced the number
61
LADaS 2018 - Latin America Data Science Workshop
(a) 2015 (b) 2016
Figure 2. Geo-referenced K-Core of the Brazilian air transportation network with
a digraph (route-based) perspective as of July 2015 and May 2016.
Table 4. Comparison of maximum K-Cores in the digraph representation.
Core (K) # Airports # Routes
Company
2015 2016 2015 2016 2015 2016
Gol 12 12 13 8 106 50
Azul 10 10 21 15 174 110
TAM 10 10 13 10 92 64
Avianca 8 8 8 8 42 42
of key airports and routes among them in their core structures, although the same level
of connectivity was kept. The exception here is Avianca that kept the same level on its
structure (the same K-Core size) with only some slight changes in the structure of its core.
3.4. Multi-digraph analysis: The flight-based perspective
In this section, we analyze the results obtained from the multi-digraph corresponding to
the flights in the Brazilian air transportation network. Multi-digraph is the oriented graph
that may have multiple (or parallel) edges, i.e., two vertices may be connected by more
than one edge. In other words, a single route between two airports, as seen in the digraph
format in Section 3.3, can be split into multiple flights that use that route. This feature of
the multi-digraph can thus better represent the real usage of a route, since typically many
airport pairs are connected by multiple flights along a single day. The multi-digraph
representation thus allows quantifying how busy a route between an airport pair is.
Figure 3 shows the geo-referenced K-Core of the Brazilian air transportation net-
work with a multi-digraph (flight-based) perspective for 2015 and 2016. The trend to-
wards concentration emerges in Figure 3(b) showing the busiest airports in the country.
We analyze the connectivity of the maximum K-Core in the multi-digraph corre-
sponding to flight network of each of the four main airline companies in Brazil. Table 5
shows the maximum core number K as well as the number of airports and flights in the
maximum K-Core of each of the main airline companies, both in June 2015 and May
2016.
62
LADaS 2018 - Latin America Data Science Workshop
(a) 2015 (b) 2016
Figure 3. Geo-referenced K-Core of the Brazilian air transportation network with
a multi-digraph (flight-based) perspective as of July 2015 and May 2016.
Table 5. Comparison of maximum K-Cores in the multi-digraph representation.
Core (K) # Airports # Flights
Company
2015 2016 2015 2016 2015 2016
Gol 395 308 2 2 395 308
Azul 288 288 6 6 1131 1120
TAM 381 345 2 2 381 345
Avianca 160 160 2 2 160 160
4. Conclusion
This paper provides a structural analysis of the Brazilian air transportation network in two
time periods (June 2015 and May 2016).A comparative analysis between this two time
periods brings results on how the economic crisis impacted the Brazilian air transportation
network, as it is shown that the main airline companies have reduced the routes they
use between airports and the number of flights that use these routes by 15% and 20%,
respectively, representing a significative contraction of the Brazilian air transportation
network.
Moreover, adopting MultiAspect Graphs (MAGs) [Wehmuth et al. 2016,
Wehmuth et al. 2017] for the modeling enabled a multilayer and time-varying structural
analysis of the Brazilian air transportation network using a single mathematical object,
thus easing the processing and analysis. With such an approach, the multi-layer perspec-
tive enabled the unveiling of the particular strategies of each airline to both establish and
adapt in a moment of crisis their specific flight networks. Similarly, the time-varying
perspective allowed analyses considering different time periods, and thus assessing the
impact of the economic crisis, but also analyzing the different airlines concerning their
routes as well as the flights that use these routes. Altogether, these different perspectives
allowed the analysis of the impact on the Brazilian air transportation network due to eco-
nomic restrictions. Therefore, besides the multilayer and time-varying structural analysis
of the Brazilian air transportation network, this paper also acts as a proof-of-concept for
the MAG potential for the modeling and analysis of high-order networks.
63
LADaS 2018 - Latin America Data Science Workshop
Future work includes the development and application of new centrality measures
to be applied in MAGs, including time centralities [Costa et al. 2015], in particular con-
sidering applications for transportation networks.
Acknowledgments
This work was partially supported by CNPq through the grants authors receive(d). In
particular, authors acknowledge the INCT in Data Sciences (CNPq no. 465560/2014-8).
Authors also acknowledge the support of CAPES, FAPERJ, and FAPESP.
References
Costa, B., Bechara, J. V., Wehmuth, K., and Ziviani, A. (2017). A multilayer and time-
varying structural analysis of the Brazilian air transportation network. Technical report.
Available at http://arxiv.org/abs/1709.03360.
Costa, E. C., Vieira, A. B., Wehmuth, K., Ziviani, A., and da Silva, A. P. C. (2015). Time
centrality in dynamic complex networks. Advances in Complex Systems, 18(07n08).
Couto, G. S., da Silva, A. P. C., Ruiz, L. B., and Benevenuto, F. (2015). Structural
properties of the brazilian air transportation network. Anais da Academia Brasileira
de Ciências, 87:1653–1674.
Seidman, S. B. (1983). Network structure and minimum degree. Social Networks,
5(3):269–287.
Sternberg, A., Carvalho, D., Murta, L., Soares, J., and Ogasawara, E. (2016). An analysis
of Brazilian flight delays based on frequent patterns. Transportation Research Part E:
Logistics and Transportation Review, 95:282–298.
Tsiotas, D. and Polyzos, S. (2015). Decomposing multilayer transportation networks
using complex network analysis: a case study for the Greek aviation network. Journal
of Complex Networks, 3(4):642–670.
Verma, T., Araújo, N. A. M., and Herrmann, H. J. (2014). Revealing the structure of the
world airline network. Scientific Reports, 4:1–6.
Wehmuth, K., Fleury, É., and Ziviani, A. (2016). On MultiAspect graphs. Theoretical
Computer Science, 651:50–61.
Wehmuth, K., Fleury, É., and Ziviani, A. (2017). MultiAspect Graphs: Algebraic Repre-
sentation and Algorithms. Algorithms, 10(1):1–36.
Wei, P., Chen, L., and Sun, D. (2014). Algebraic connectivity maximization of an air
transportation network: The flight routes’ addition/deletion problem. Transportation
Research Part E: Logistics and Transportation Review, 61:13–27.
64