nx.draw_networkx(FG, with_labels=True) # Quick view of the Graph. As expected we see 3 very busy airports

nx.algorithms.degree_centrality(FG) # Notice the 3 airports from which all of our 100 rows of data originates
nx.density(FG) # Average edge density of the Graphs

输出：

0.09047619047619047
nx.average_shortest_path_length(FG) # Average shortest path length for ALL paths in the Graph

输出：

2.36984126984127
nx.average_degree_connectivity(FG) # For a node of degree k - What is the average of its neighbours' degree?

输出：

{1: 19.307692307692307, 2: 19.0625, 3: 19.0, 17: 2.0588235294117645, 20: 1.95}

从可视化中（上面的方式）可以明显看出 - 从一些机场到其他机场有多条路径 。假如想要计算2个机场之间的最短路线 。我们可以想到几种方法：
距离最短的路径 。
飞行时间最短的路径 。
我们可以通过距离或飞行时间来给路径赋予权重 ， 并用算法计算最短路径 。请注意 ， 这是一个近似的解决方案 - 实际问题是计算当你到达中转机场时的航班可用性加候机的等待时间 ， 这才是一种更完整的方法 ， 也是人们计划旅行的方式 。出于本文的目的 ， 我们将假设你到达机场时可以随时使用航班并使用飞行时间作为权重 ， 从而计算最短路径 。
让我们以JAX和DFW机场为例：

# Let us find all the paths available
for path in nx.all_simple_paths(FG, source='JAX', target='DFW'):
print(path)
# Let us find the dijkstra path from JAX to DFW.
# You can read more in-depth on how dijkstra works from this resource - https://courses.csail.mit.edu/6.006/fall11/lectures/lecture16.pdf
dijpath = nx.dijkstra_path(FG, source='JAX', target='DFW')
dijpath

输出：

['JAX', 'JFK', 'SEA', 'EWR', 'DFW']
# Let us try to find the dijkstra path weighted by airtime (approximate case)
shortpath = nx.dijkstra_path(FG, source='JAX', target='DFW', weight='air_time')
shortpath

输出：

['JAX', 'JFK', 'BOS', 'EWR', 'DFW']

结语
本文充其量只是对图论和网络分析这一非常有趣的领域进行了粗浅的介绍 。对理论和Python软件包的了解将为任何数据科学家的工具库增加一个有价值的工具 。对于上面使用的数据集 ， 可以提出一系列其他问题 ， 例如：
在给定成本 ， 飞行时间和可用性的情况下 ， 找到两个机场之间的最短路径？
作为一家航空公司 ， 你们拥有一队飞机 。你了解航班的需求 。假设你有权再运营2架飞机（或者为你的机队添加2架飞机） ， 把这两架飞机投入到哪条航线可以最大限度地提高盈利能力？
你可以重新安排航班和时刻表以优化某个参数吗？（如时效性或盈利能力等）
如果你解决了这些问题 ， 请在下面的评论中告诉我们！
网络分析将有助于解决一些常见的数据科学问题 ， 并在更大规模和抽象的情况下对其进行可视化 。如果想了解更多有关其他内容的信息 ， 请发表评论 。
参考文献

1. History of Graph Theory || S.G. Shrinivas et. al
2. Big O Notation cheatsheet
3. Networkx reference documentation
4. Graphviz download
5. Pygraphvix
6. Star visualization
7. Dijkstra Algorithm

原文标题：
An Introduction to Graph Theory and Network Analysis (with Python codes)
链接：
https://www.analyticsvidhya.com/blog/2018/04/introduction-to-graph-theory-network-analysis-python-codes/

译者简介



和中华 ， 留德软件工程硕士 。由于对机器学习感兴趣 ， 硕士论文选择了利用遗传算法思想改进传统kmeans 。目前在杭州进行大数据相关实践 。加入数据派THU希望为IT同行们尽自己一份绵薄之力 ， 也希望结交许多志趣相投的小伙伴 。