本文約6300字，建議閱讀20+分鐘。
本文從圖的概念以及歷史講起，並介紹了一些必備的術語，隨後引入了networkx庫，並以一個航班信息數據集為例，帶領讀者完成了一些基本分析。
簡介俗話說一圖勝千言。但是「圖」（Graph）說的遠不止於此。以圖形式呈現的數據可視化能幫助我們獲得見解，並基於它們做出更好的數據驅動型決策。
但要真正理解圖是什麼以及為什麼使用它們，我們需要理解一個稱為圖論（Graph Theory）的概念。理解它可以使我們成為更好的程式設計師。
如果你曾經嘗試理解這個概念，應該會遇到大量的公式和乾澀的理論。這便是為什麼我們要寫這篇博文的原因。我們先解釋概念，然後提供實例，以便你可以跟隨並弄明白它的執行方式。這是一篇詳細的文章，因為我們認為提供概念的正確解釋要比簡潔的定義更受歡迎。
在本文中，我們將了解圖是什麼，它們的應用以及一些歷史背景。我們還將介紹一些圖論概念，然後使用進行案例研究以鞏固理解。
準備好了嗎？我們開始吧。
目錄圖及其應用
圖論的歷史、為何使用圖論
必備術語
圖論概念
熟悉Python中的圖
數據分析案例
圖及其應用
讓我們看一個簡單的圖（Graph）來理解這個概念。如下圖所示：
假設此圖代表某個城市的熱門景點位置，以及遊客所遵循的路徑。我們把V視為景點位置，將E視為從一個地方到另一個地方的路徑。
V = {v1, v2, v3, v4, v5}
E = {(v1,v2), (v2,v5), (v5, v5), (v4,v5), (v4,v4)}
邊（u，v）與邊（v，u）相同 - 它們是無序對。
具體而言，圖（Graph）是用於研究對象和實體之間成對關係的數學結構。它是離散數學的一個分支，在計算機科學，化學，語言學，運籌學，社會學等領域有多種應用。
數據科學和分析領域也使用圖來模擬各種結構和問題。作為一名數據科學家，你應該能以有效的方式解決問題，如果數據是以特定方式排列的，則圖可以提供一種解決問題的機制。
形式上看，
圖是一對集合。G = (V, E)，V是頂點集合，E是邊集合。 E由V中的元素對組成（無序對）
有向圖（DiGraph）也是一對集合。D = (V, A)，V是頂點集合，A是弧集合。A由V中的元素對組成（有序對）
在有向圖的情況下，（u，v）和（v，u）之間存在區別。通常在這種情況下，邊被稱為弧，以指示方向的概念。
R和Python中都有使用圖論概念分析數據的包。在本文中，我們將簡要介紹一些概念並使用Networkx Python包分析一個數據集。
from IPython.display import Image
Image('images/network.PNG')
Image('images/usecase.PNG')
從上面的例子可以清楚地看出，圖在數據分析中的應用是廣泛的。我們來看幾個用例場景：
圖可用於找出社交網絡中最有影響力的人。廣告商和營銷人員可以通過社交網絡中最有影響力的人員傳達他們的信息，從而估算最大的營銷價格。
圖可用於查找有助於減少欺詐交易的異常模式。有一些例子可以通過分析銀行網絡的資金流動來偵測恐怖主義活動。
圖有助於確定送貨卡車的最佳路線以及識別倉庫和交付中心的位置。
製藥公司可以使用圖論優化銷售人員的路線。這有助於降低成本並縮短銷售人員的行程時間。
電信公司通常使用圖（Voronoi圖）來了解基站的數量和位置，以確保最大的覆蓋範圍。
圖的歷史以及為何使用圖圖的歷史
如果想更多地了解關於圖的想法是如何形成的，請繼續閱讀！
該理論的起源可以追溯到柯尼斯堡七橋問題（大約1730年代）。它提問是否可以在以下限制條件下遍歷柯尼斯堡市的七座橋梁
小故事：歐拉於1736年研究並解決了此問題，他把問題歸結為如「一筆畫」問題。他的《柯尼斯堡七橋》的論文圓滿解決了這一問題，同時開創了數學一個新分支---圖論。
這等價於詢問4個節點和7個邊的多圖（multigraph）是否具有歐拉環（歐拉環是在同一個頂點上開始和結束的歐拉路徑。而歐拉路徑是指在圖中僅僅遍歷每個邊一次的路徑。更多術語後文中給出）。這個問題引出了歐拉圖的概念。柯尼斯堡七橋問題的答案是否定的，它最早由歐拉解答。
譯者註：在圖論中，多圖（相對於簡單圖）是指圖中允許出現多邊（也叫平行邊），即兩個頂點可以有多條邊連接，如下圖中的紅色就是多邊，所以該圖屬於多圖。
1840年，A.F Mobius提出了完全圖（complete graph）和二分圖（bipartite graph）的概念，Kuratowski通過趣味謎題證明它們是平面的。樹的概念（沒有環的連通圖）由Gustav Kirchhoff於1845年提出，他在計算電網或電路中的電流時使用了圖論思想。
1852年，Thomas Gutherie發現了著名的四色問題。然後在1856年，Thomas P. Kirkman和William R.Hamilton研究了多面體的循環，並通過研究僅訪問某些地點一次的旅行，發明了稱為哈密頓圖的概念。1913年，H.Dudeney提到了一個難題。儘管發明了四色問題，但Kenneth Appel和Wolfgang Haken在一個世紀後才解決了這個問題。這一次被認為是圖論真正的誕生。
Caley研究了微分學的特定分析形式來研究樹。這在理論化學中有許多含義。這也導致了枚舉圖論（enumerative graph theory）的發明。不管怎麼說，「圖」這個術語是由Sylvester在1878年引入的，他在「量子不變量」與代數和分子圖的協變量之間進行了類比。
1941年，Ramsey致力於著色問題，這產生了另一個圖論的分支 - 極值圖論（Extremal graph theory）。1969年，Heinrich使用計算機解決了四色問題。對漸近圖連通性的研究產生了隨機圖論。圖論和拓撲學的歷史也密切相關，它們有許多共同的概念和定理。
Image('images/Konigsberg.PNG', width = 800)
為何使用圖？
以下幾點可以激勵你在日常數據科學問題中使用圖：
圖提供了一種處理關係和交互等抽象概念的更好的方法。它還提供了直觀的視覺方式來思考這些概念。圖很自然地成了分析社會關係的基礎。
圖資料庫已成為一種常用的計算工具，並且是SQL和NoSQL資料庫的替代方案。
圖用於以DAG（定向非循環圖）的形式建模分析工作流。
一些神經網絡框架還使用DAG來模擬不同層中的各種操作。
圖理論用於研究和模擬社交網絡，欺詐模式，功耗模式，社交媒體的病毒性和影響力。社交網絡分析（SNA）可能是圖理論在數據科學中最著名的應用。
它用於聚類算法 - 特別是K-Means。
系統動力學也使用一些圖理論 - 特別是循環。
路徑優化是優化問題的一個子集，它也使用圖的概念。
從計算機科學的角度來看，圖提供了計算效率。某些算法的Big O複雜度對於以圖形式排列的數據更好（與表格數據相比）。
必備術語在進一步閱讀本文之前，建議你熟悉這些術語。
頂點u和v稱為邊（u，v）的末端頂點。
如果兩條邊具有相同的末端頂點，則它們是平行的。
形式為（v，v）的邊是循環。
如果圖沒有平行邊和循環，則圖被稱為簡單圖。
如果圖沒有邊，則稱其為Empty，即E是空的。
如果圖沒有頂點，則稱其為Null，即V和E是空的。
只有1個頂點的圖是一個Trivial graph。
具有共同頂點的邊是相鄰的。具有共同邊的頂點是相鄰的。
頂點v的度，寫作d（v），是指以v作為末端頂點的邊數。按照慣例，我們把一個循環計作兩次，並且平行邊緣分別貢獻一個度。
孤立頂點是度數為1的頂點。d（1）頂點是孤立的。
如果圖的邊集合包含了所有頂點之間的所有可能邊，則圖是完備的。
圖G =（V，E）中的步行（Walk）是指由圖中頂點和邊組成的一個形如ViEiViEi的有限交替序列。
如果初始頂點和最終頂點不同，則Walk是開放的（Open）。如果初始頂點和最終頂點相同，則Walk是關閉的（Closed）。
如果任何邊緣最多遍歷一次，則步行是一條Trail。
如果任何頂點最多遍歷一次，則Trail是一條路徑Path（除了一個封閉的步行）。
封閉路徑（Closed Path）是一條迴路Circuit，類似於電路。
在本節中，我們將介紹一些對數據分析有用的概念（無特定順序）。請注意，另外還有很多概念的深度超出了本文的範圍。我們開始吧。
平均路徑長度
所有可能節點對應的最短路徑長度的平均值。給出了圖的「緊密度」度量，可用於了解此網絡中某些內容的流動速度。
BFS和DFS
廣度優先搜索和深度優先搜索是用於在圖中搜索節點的兩種不同算法。它們通常用於確定我們是否可以從給定節點到達某個節點。這也稱為圖遍歷。
BFS的目的是儘可能接近根節點遍歷圖，而DFS算法旨在儘可能遠離根節點。
中心性（Centrality）
用於分析網絡的最廣泛使用和最重要的概念工具之一。中心性旨在尋找網絡中最重要的節點。可能存在對「重要」的不同理解，因此存在許多中心性度量標準。中心性標準本身就可以分成好多類。有一些標準是以沿著邊的流動為特徵，還有一些標準以步行結構（Walk Structure）為特徵。
一些最常用的標準是：
度中心性（Degree Centrality） - 第一個也是概念上最簡單的中心性定義。表示連接到某節點的邊數。在有向圖中，我們可以有2個度中心性度量。流入和流出的中心性。
緊密中心性（Closeness Centrality） - 從某節點到所有其他節點的最短路徑的平均長度。
中介中心性（Betweenness Centrality） - 某節點在多少對節點的最短路徑上。
這些中心性度量有不同變種，並且可以使用各種算法來實現定義。總而言之，這方面有大量的定義和算法。
網絡密度
圖的邊數的度量。實際定義將根據圖的類型和所提問問題的上下文而不同。對於完備的無向圖，密度為1，而空圖（empty）為0。在某些情況下（包含循環時），圖密度可能大於1。
圖隨機化（Graph Randomization）
儘管一些圖度量指標可能很容易計算，但要理解它們的相對重要性並不容易。在這種情況下，我們使用網絡/圖隨機化。我們計算了手頭的圖和隨機生成的另一些類似圖的度量。例如，這些相似圖可以有相同數量的密度和節點。通常我們生成1000個相似的隨機圖並計算每個圖的度量標準，然後與手頭圖的相同度量進行比較，以得出某些基準（benchmark）。
在數據科學中，當嘗試對某個圖進行聲明時，如果與某些隨機生成的圖進行對比，則會有所幫助。
熟悉Python中的圖我們將在Python中使用networkx包。它可以安裝在Anaconda的Root環境中（如果你使用的是Anaconda的Python分發版）。你也可以pip install安裝它。
讓我們看一下使用Networkx軟體包可以完成的一些常見事情。包括導入和創建圖以及可視化圖的方法。
圖形創建
import networkx as nx
# Creating a Graph
G = nx.Graph() # Right now G is empty
# Add a node
G.add_node(1)
G.add_nodes_from([2,3]) # You can also add a list of nodes by passing a list argument
# Add edges
G.add_edge(1,2)
e = (2,3)
G.add_edge(*e) # * unpacks the tuple
G.add_edges_from([(1,2), (1,3)]) # Just like nodes we can add edges from a list
通過傳遞包含節點和屬性dict的元組，可以在創建節點和邊的時候添加節點和邊的屬性。
除了逐個節點或逐個邊地構建圖形之外，還可以通過一些經典的圖操作來生成它們，例如：
subgraph(G, nbunch) - induced subgraph view of G on nodes in nbunch
union(G1,G2) - graph union
disjoint_union(G1,G2) - graph union assuming all nodes are different
cartesian_product(G1,G2) - return Cartesian product graph
compose(G1,G2) - combine graphs identifying nodes common to both
complement(G) - graph complement
create_empty_copy(G) - return an empty copy of the same graph class
convert_to_undirected(G) - return an undirected representation of G
convert_to_directed(G) - return a directed representation of G
對於不同類型的圖，存在單獨的類。例如，nx.DiGraph類允許創建有向圖。可以使用單個方法直接創建包含路徑的特定圖。有關圖創建方法的完整列表，請參閱完整文檔。連結在本文末尾給出。
Image('images/graphclasses.PNG', width = 400)
訪問邊和節點
可以使用G.nodes和G.edges方法訪問節點和邊。可以使用括號/下標法訪問各個節點和邊。
G.nodes()
NodeView((1, 2, 3))
G.edges()
EdgeView([(1, 2), (1, 3), (2, 3)])
G[1] # same as G.adj[1]
AtlasView({2: {}, 3: {}})
G[1][2]
{}
G.edges[1, 2]
{}
圖可視化
Networkx提供了可視化圖的基本功能，但其主要目標是幫助圖分析而不是圖的可視化。圖可視化很難，我們將使用專門用於此任務的工具。Matplotlib提供了一些便利功能。但是GraphViz可能是最好的工具，因為它提供了一個PyGraphViz的Python接口（連結在文檔的末尾）。
%matplotlib inline
import matplotlib.pyplot as plt
nx.draw(G)
首先必須安裝Graphviz。然後使用該命令pip install pygraphviz --install-option =「<>。在安裝選項中，你必須提供Graphviz 中lib和include文件夾的路徑。
import pygraphviz as pgv
d={'1': {'2': None}, '2': {'1': None, '3': None}, '3': {'1': None}}
A = pgv.AGraph(data=d)
print(A) # This is the 'string' or simple representation of the Graph
Output:
strict graph "" {
1 -- 2;
2 -- 3;
3 -- 1;
}
PyGraphviz可以很好地控制邊和節點的各個屬性。我們可以使用它獲得非常漂亮的可視化。
# Let us create another Graph where we can individually control the colour of each node
B = pgv.AGraph()
# Setting node attributes that are common for all nodes
B.node_attr['style']='filled'
B.node_attr['shape']='circle'
B.node_attr['fixedsize']='true'
B.node_attr['fontcolor']='#FFFFFF'
# Creating and setting node attributes that vary for each node (using a for loop)
for i in range(16):
B.add_edge(0,i)
n=B.get_node(i)
n.attr['fillcolor']="#%2x0000"%(i*16)
n.attr['height']="%s"%(i/16.0+0.5)
n.attr['width']="%s"%(i/16.0+0.5)
B.draw('star.png',prog="circo") # This creates a .png file in the local directory. Displayed below.
Image('images/star.png', width=650) # The Graph visualization we created above.
通常，可視化被認為是與圖分析獨立的任務。分析後的圖將導出為Dotfile。然後單獨顯示該Dotfile以展示我們想表達的內容。
數據分析案例我們將尋找一個通用數據集（不是專門用於圖的數據集）並進行一些操作（在pandas中），以便它可以以邊列表（edge list）的形式輸入到圖中。邊列表是一個元組列表，其中的元組包含定義每條邊的頂點
我們將關注的數據集來自航空業。它有一些關於航線的基本信息。有某段旅程的起始點和目的地。還有一些列表示每段旅程的到達和起飛時間。如你所想，這個數據集非常適合作為圖進行分析。想像一下通過航線（邊）連接的幾個城市（節點）。如果你是航空公司，你可以問如下幾個問題：
import pandas as pd
import numpy as np
data = pd.read_csv('data/Airlines.csv')
data.shape
(100, 16)
data.dtypes
year int64
month int64
day int64
dep_time float64
sched_dep_time int64
dep_delay float64
arr_time float64
sched_arr_time int64
arr_delay float64
carrier object
flight int64
tailnum object
origin object
dest object
air_time float64
distance int64
dtype: object
# converting sched_dep_time to 'std' - Scheduled time of departure
data['std'] = data.sched_dep_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_dep_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting sched_arr_time to 'sta' - Scheduled time of arrival
data['sta'] = data.sched_arr_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_arr_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting dep_time to 'atd' - Actual time of departure
data['atd'] = data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting arr_time to 'ata' - Actual time of arrival
data['ata'] = data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
現在時間列被轉換成了我們想要的格式。最後，我們可能希望將年，月和日列合併到日期列中。這一步不是絕對必要的。但是，一旦轉換為日期時間（datetime）格式，我們就可以輕鬆獲取年，月，日（和其他）信息。
data['date'] = pd.to_datetime(data[['year', 'month', 'day']])
# finally we drop the columns we don't need
data = data.drop(columns = ['year', 'month', 'day'])
現在使用networkx函數導入數據集，該函數直接讀如pandas DataFrame。就像圖創建一樣，多種方法可以將數據從多種格式中輸入到圖中。
import networkx as nx
FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True,)
FG.nodes()
輸出：
NodeView(('EWR', 'MEM', 'LGA', 'FLL', 'SEA', 'JFK', 'DEN', 'ORD', 'MIA', 'PBI', 'MCO', 'CMH', 'MSP', 'IAD', 'CLT', 'TPA', 'DCA', 'SJU', 'ATL', 'BHM', 'SRQ', 'MSY', 'DTW', 'LAX', 'JAX', 'RDU', 'MDW', 'DFW', 'IAH', 'SFO', 'STL', 'CVG', 'IND', 'RSW', 'BOS', 'CLE'))
FG.edges()
輸出：
EdgeView([('EWR', 'MEM'), ('EWR', 'SEA'), ('EWR', 'MIA'), ('EWR', 'ORD'), ('EWR', 'MSP'), ('EWR', 'TPA'), ('EWR', 'MSY'), ('EWR', 'DFW'), ('EWR', 'IAH'), ('EWR', 'SFO'), ('EWR', 'CVG'), ('EWR', 'IND'), ('EWR', 'RDU'), ('EWR', 'IAD'), ('EWR', 'RSW'), ('EWR', 'BOS'), ('EWR', 'PBI'), ('EWR', 'LAX'), ('EWR', 'MCO'), ('EWR', 'SJU'), ('LGA', 'FLL'), ('LGA', 'ORD'), ('LGA', 'PBI'), ('LGA', 'CMH'), ('LGA', 'IAD'), ('LGA', 'CLT'), ('LGA', 'MIA'), ('LGA', 'DCA'), ('LGA', 'BHM'), ('LGA', 'RDU'), ('LGA', 'ATL'), ('LGA', 'TPA'), ('LGA', 'MDW'), ('LGA', 'DEN'), ('LGA', 'MSP'), ('LGA', 'DTW'), ('LGA', 'STL'), ('LGA', 'MCO'), ('LGA', 'CVG'), ('LGA', 'IAH'), ('FLL', 'JFK'), ('SEA', 'JFK'), ('JFK', 'DEN'), ('JFK', 'MCO'), ('JFK', 'TPA'), ('JFK', 'SJU'), ('JFK', 'ATL'), ('JFK', 'SRQ'), ('JFK', 'DCA'), ('JFK', 'DTW'), ('JFK', 'LAX'), ('JFK', 'JAX'), ('JFK', 'CLT'), ('JFK', 'PBI'), ('JFK', 'CLE'), ('JFK', 'IAD'), ('JFK', 'BOS')])
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
連結：
https://www.analyticsvidhya.com/blog/2018/04/introduction-to-graph-theory-network-analysis-python-codes/
和中華，留德軟體工程碩士。由於對機器學習感興趣，碩士論文選擇了利用遺傳算法思想改進傳統kmeans。目前在杭州進行大數據相關實踐。加入數據派THU希望為IT同行們儘自己一份綿薄之力，也希望結交許多志趣相投的小夥伴。
工作內容：需要一顆細緻的心，將選取好的外文文章翻譯成流暢的中文。如果你是數據科學/統計學/計算機類的留學生，或在海外從事相關工作，或對自己外語水平有信心的朋友歡迎加入翻譯小組。
你能得到：定期的翻譯培訓提高志願者的翻譯水平，提高對於數據科學前沿的認知，海外的朋友可以和國內技術應用發展保持聯繫，THU數據派產學研的背景為志願者帶來好的發展機遇。
其他福利：來自於名企的數據科學工作者，北大清華以及海外等名校學生他們都將成為你在翻譯小組的夥伴。
點擊文末「閱讀原文」加入數據派團隊~
轉載須知
如需轉載，請在開篇顯著位置註明作者和出處（轉自：數據派ID：datapi），並在文章結尾放置數據派醒目二維碼。有原創標識文章，請發送【文章名稱-待授權公眾號名稱及ID】至聯繫郵箱，申請白名單授權並按要求編輯。
發布後請將連結反饋至聯繫郵箱（見下方）。未經許可的轉載以及改編者，我們將依法追究其法律責任。
點擊「閱讀原文」擁抱組織