Sample solutions
Markov chain analysis of the US airport network
One way to view the airline transportation infrastructure is in the form of a directed network or graph, in which vertices are airports and edges are the
...
Sample solutions
Markov chain analysis of the US airport network
One way to view the airline transportation infrastructure is in the form of a directed network or graph, in which vertices are airports and edges are the directflight segments that connect them. For instance, if there is a direct flight from Atlanta's Hartsfield-Jackson International Airport ("ATL") to Los Angeles
International Airport ("LAX"), then the airport network would have a directed edge from ATL to LAX.
Given the airport network, one question we might ask is, which airports are most critical to disruption of the overall network? That is, if an airport is shut down,
thereby leading to all inbound and outbound flights being cancelled, will that catastrophic event have a big impact or a small impact on the overall network?
You would expect "importance" to be related to whether an airport has lots of inbound or outgoing connections. In graph lingo, that's also called the degree of a
vertex or node. But if there are multiple routes that can work around a highly connected hub (i.e., a vertex with a high indegree or outdegree), that might not be
the case. So let's try to use a PageRank-like scheme to see what we get and compare that to looking at degree.
As it happens, the US Bureau of Transportation Statistics collects data on all flights originating or arriving in the United States. In this notebook, you'll use this
data to build an airport network and then use Markov chain analysis to rank the networks by some measure of "criticality."
Sources: This notebook is adapted from the following: https://www.mongodb.com/blog/post/pagerank-on-flights-dataset
(https://www.mongodb.com/blog/post/pagerank-on-flights-dataset). The dataset you will use was taken from the repository available here:
https://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236 (https://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236)
The formal analysis problem
Let's model the analysis problem as follows.
Consider a "random flyer" to be a person who arrives at an airport , and then randomly selects any direct flight that departs from and arrives at . We refer
to the direct flight from to as the flight segment . Upon arriving at , the flyer repeats the process of randomly selecting a new segment, . He or
she repeats this process forever.
[Show More]