|
本文約6300字，建議閱讀20+分鐘。
本文從圖的概念以及歷史講起，并介紹了一些必備的術(shù)語，隨后引入了networkx庫，并以一個(gè)航班信息數(shù)據(jù)集為例，帶領(lǐng)讀者完成了一些基本分析。
簡介
俗話說一圖勝千言。但是“圖”（Graph）說的遠(yuǎn)不止于此。以圖形式呈現(xiàn)的數(shù)據(jù)可視化能幫助我們獲得見解，并基于它們做出更好的數(shù)據(jù)驅(qū)動型決策。 但要真正理解圖是什么以及為什么使用它們，我們需要理解一個(gè)稱為圖論（Graph Theory）的概念。理解它可以使我們成為更好的程序員。
如果你曾經(jīng)嘗試?yán)斫膺@個(gè)概念，應(yīng)該會遇到大量的公式和干澀的理論。這便是為什么我們要寫這篇博文的原因。我們先解釋概念，然后提供實(shí)例，以便你可以跟隨并弄明白它的執(zhí)行方式。這是一篇詳細(xì)的文章，因?yàn)槲覀冋J(rèn)為提供概念的正確解釋要比簡潔的定義更受歡迎。 在本文中，我們將了解圖是什么，它們的應(yīng)用以及一些歷史背景。我們還將介紹一些圖論概念，然后使用進(jìn)行案例研究以鞏固理解。 準(zhǔn)備好了嗎？我們開始吧。
目錄
圖及其應(yīng)用 圖論的歷史、為何使用圖論 必備術(shù)語 圖論概念 熟悉Python中的圖 數(shù)據(jù)分析案例
圖及其應(yīng)用
讓我們看一個(gè)簡單的圖（Graph）來理解這個(gè)概念。如下圖所示：
假設(shè)此圖代表某個(gè)城市的熱門景點(diǎn)位置，以及游客所遵循的路徑。我們把V視為景點(diǎn)位置，將E視為從一個(gè)地方到另一個(gè)地方的路徑。
V = {v1, v2, v3, v4, v5} E = {(v1,v2), (v2,v5), (v5, v5), (v4,v5), (v4,v4)}
邊（u，v）與邊（v，u）相同 - 它們是無序?qū)Α?/span> 具體而言，圖（Graph）是用于研究對象和實(shí)體之間成對關(guān)系的數(shù)學(xué)結(jié)構(gòu)。它是離散數(shù)學(xué)的一個(gè)分支，在計(jì)算機(jī)科學(xué)，化學(xué)，語言學(xué)，運(yùn)籌學(xué)，社會學(xué)等領(lǐng)域有多種應(yīng)用。 數(shù)據(jù)科學(xué)和分析領(lǐng)域也使用圖來模擬各種結(jié)構(gòu)和問題。作為一名數(shù)據(jù)科學(xué)家，你應(yīng)該能以有效的方式解決問題，如果數(shù)據(jù)是以特定方式排列的，則圖可以提供一種解決問題的機(jī)制。 形式上看，
圖是一對集合。G = (V, E)，V是頂點(diǎn)集合，E是邊集合。 E由V中的元素對組成（無序?qū)Γ?/span> 有向圖（DiGraph）也是一對集合。D = (V, A)，V是頂點(diǎn)集合，A是弧集合。A由V中的元素對組成（有序?qū)?/span>）
在有向圖的情況下，（u，v）和（v，u）之間存在區(qū)別。通常在這種情況下，邊被稱為弧，以指示方向的概念。 R和Python中都有使用圖論概念分析數(shù)據(jù)的包。在本文中，我們將簡要介紹一些概念并使用Networkx Python包分析一個(gè)數(shù)據(jù)集。
from IPython.display import Image Image('images/network.PNG')
Image('images/usecase.PNG')
從上面的例子可以清楚地看出，圖在數(shù)據(jù)分析中的應(yīng)用是廣泛的。我們來看幾個(gè)用例場景： 圖可用于找出社交網(wǎng)絡(luò)中最有影響力的人。廣告商和營銷人員可以通過社交網(wǎng)絡(luò)中最有影響力的人員傳達(dá)他們的信息，從而估算最大的營銷價(jià)格。 圖可用于查找有助于減少欺詐交易的異常模式。有一些例子可以通過分析銀行網(wǎng)絡(luò)的資金流動來偵測恐怖主義活動。 圖有助于確定送貨卡車的最佳路線以及識別倉庫和交付中心的位置。 制藥公司可以使用圖論優(yōu)化銷售人員的路線。這有助于降低成本并縮短銷售人員的行程時(shí)間。 電信公司通常使用圖（Voronoi圖）來了解基站的數(shù)量和位置，以確保最大的覆蓋范圍。
圖的歷史以及為何使用圖
圖的歷史 如果想更多地了解關(guān)于圖的想法是如何形成的，請繼續(xù)閱讀！
該理論的起源可以追溯到柯尼斯堡七橋問題（大約1730年代）。它提問是否可以在以下限制條件下遍歷柯尼斯堡市的七座橋梁 每座橋只經(jīng)過一次（即不重復(fù)） 從哪出發(fā)，最終回到哪
小故事：歐拉于1736年研究并解決了此問題，他把問題歸結(jié)為如“一筆畫”問題。他的《柯尼斯堡七橋》的論文圓滿解決了這一問題，同時(shí)開創(chuàng)了數(shù)學(xué)一個(gè)新分支---圖論。
這等價(jià)于詢問4個(gè)節(jié)點(diǎn)和7個(gè)邊的多圖（multigraph）是否具有歐拉環(huán)（歐拉環(huán)是在同一個(gè)頂點(diǎn)上開始和結(jié)束的歐拉路徑。而歐拉路徑是指在圖中僅僅遍歷每個(gè)邊一次的路徑。更多術(shù)語后文中給出）。這個(gè)問題引出了歐拉圖的概念。柯尼斯堡七橋問題的答案是否定的，它最早由歐拉解答。 譯者注：在圖論中，多圖（相對于簡單圖）是指圖中允許出現(xiàn)多邊（也叫平行邊），即兩個(gè)頂點(diǎn)可以有多條邊連接，如下圖中的紅色就是多邊，所以該圖屬于多圖。
1840年，A.F Mobius提出了完全圖（complete graph）和二分圖（bipartite graph）的概念，Kuratowski通過趣味謎題證明它們是平面的。樹的概念（沒有環(huán)的連通圖）由Gustav Kirchhoff于1845年提出，他在計(jì)算電網(wǎng)或電路中的電流時(shí)使用了圖論思想。 1852年，Thomas Gutherie發(fā)現(xiàn)了著名的四色問題。然后在1856年，Thomas P. Kirkman和William R.Hamilton研究了多面體的循環(huán)，并通過研究僅訪問某些地點(diǎn)一次的旅行，發(fā)明了稱為哈密頓圖的概念。1913年，H.Dudeney提到了一個(gè)難題。盡管發(fā)明了四色問題，但Kenneth Appel和Wolfgang Haken在一個(gè)世紀(jì)后才解決了這個(gè)問題。這一次被認(rèn)為是圖論真正的誕生。 Caley研究了微分學(xué)的特定分析形式來研究樹。這在理論化學(xué)中有許多含義。這也導(dǎo)致了枚舉圖論（enumerative graph theory）的發(fā)明。不管怎么說，“圖”這個(gè)術(shù)語是由Sylvester在1878年引入的，他在“量子不變量”與代數(shù)和分子圖的協(xié)變量之間進(jìn)行了類比。
1941年，Ramsey致力于著色問題，這產(chǎn)生了另一個(gè)圖論的分支 - 極值圖論（Extremal graph theory）。1969年，Heinrich使用計(jì)算機(jī)解決了四色問題。對漸近圖連通性的研究產(chǎn)生了隨機(jī)圖論。圖論和拓?fù)鋵W(xué)的歷史也密切相關(guān)，它們有許多共同的概念和定理。
Image('images/Konigsberg.PNG', width = 800)
為何使用圖？ 以下幾點(diǎn)可以激勵(lì)你在日常數(shù)據(jù)科學(xué)問題中使用圖： 圖提供了一種處理關(guān)系和交互等抽象概念的更好的方法。它還提供了直觀的視覺方式來思考這些概念。圖很自然地成了分析社會關(guān)系的基礎(chǔ)。 圖數(shù)據(jù)庫已成為一種常用的計(jì)算工具，并且是SQL和NoSQL數(shù)據(jù)庫的替代方案。 圖用于以DAG（定向非循環(huán)圖）的形式建模分析工作流。 一些神經(jīng)網(wǎng)絡(luò)框架還使用DAG來模擬不同層中的各種操作。 圖理論用于研究和模擬社交網(wǎng)絡(luò)，欺詐模式，功耗模式，社交媒體的病毒性和影響力。社交網(wǎng)絡(luò)分析（SNA）可能是圖理論在數(shù)據(jù)科學(xué)中最著名的應(yīng)用。 它用于聚類算法 - 特別是K-Means。 系統(tǒng)動力學(xué)也使用一些圖理論 - 特別是循環(huán)。 路徑優(yōu)化是優(yōu)化問題的一個(gè)子集，它也使用圖的概念。 從計(jì)算機(jī)科學(xué)的角度來看，圖提供了計(jì)算效率。某些算法的Big O復(fù)雜度對于以圖形式排列的數(shù)據(jù)更好（與表格數(shù)據(jù)相比）。
必備術(shù)語
在進(jìn)一步閱讀本文之前，建議你熟悉這些術(shù)語。 頂點(diǎn)u和v稱為邊（u，v）的末端頂點(diǎn)。 如果兩條邊具有相同的末端頂點(diǎn)，則它們是平行的。 形式為（v，v）的邊是循環(huán)。 如果圖沒有平行邊和循環(huán)，則圖被稱為簡單圖。 如果圖沒有邊，則稱其為Empty，即E是空的。 如果圖沒有頂點(diǎn)，則稱其為Null，即V和E是空的。 只有1個(gè)頂點(diǎn)的圖是一個(gè)Trivial graph。 具有共同頂點(diǎn)的邊是相鄰的。具有共同邊的頂點(diǎn)是相鄰的。 頂點(diǎn)v的度，寫作d（v），是指以v作為末端頂點(diǎn)的邊數(shù)。按照慣例，我們把一個(gè)循環(huán)計(jì)作兩次，并且平行邊緣分別貢獻(xiàn)一個(gè)度。 孤立頂點(diǎn)是度數(shù)為1的頂點(diǎn)。d（1）頂點(diǎn)是孤立的。 如果圖的邊集合包含了所有頂點(diǎn)之間的所有可能邊，則圖是完備的。 圖G =（V，E）中的步行（Walk）是指由圖中頂點(diǎn)和邊組成的一個(gè)形如ViEiViEi的有限交替序列。 如果初始頂點(diǎn)和最終頂點(diǎn)不同，則Walk是開放的（Open）。如果初始頂點(diǎn)和最終頂點(diǎn)相同，則Walk是關(guān)閉的（Closed）。 如果任何邊緣最多遍歷一次，則步行是一條Trail。 如果任何頂點(diǎn)最多遍歷一次，則Trail是一條路徑Path（除了一個(gè)封閉的步行）。 封閉路徑（Closed Path）是一條回路Circuit，類似于電路。
圖論概念
在本節(jié)中，我們將介紹一些對數(shù)據(jù)分析有用的概念（無特定順序）。請注意，另外還有很多概念的深度超出了本文的范圍。我們開始吧。 平均路徑長度 所有可能節(jié)點(diǎn)對應(yīng)的最短路徑長度的平均值。給出了圖的“緊密度”度量，可用于了解此網(wǎng)絡(luò)中某些內(nèi)容的流動速度。 BFS和DFS 廣度優(yōu)先搜索和深度優(yōu)先搜索是用于在圖中搜索節(jié)點(diǎn)的兩種不同算法。它們通常用于確定我們是否可以從給定節(jié)點(diǎn)到達(dá)某個(gè)節(jié)點(diǎn)。這也稱為圖遍歷。 BFS的目的是盡可能接近根節(jié)點(diǎn)遍歷圖，而DFS算法旨在盡可能遠(yuǎn)離根節(jié)點(diǎn)。 中心性（Centrality） 用于分析網(wǎng)絡(luò)的最廣泛使用和最重要的概念工具之一。中心性旨在尋找網(wǎng)絡(luò)中最重要的節(jié)點(diǎn)?？赡艽嬖趯Α爸匾钡牟煌斫猓虼舜嬖谠S多中心性度量標(biāo)準(zhǔn)。中心性標(biāo)準(zhǔn)本身就可以分成好多類。有一些標(biāo)準(zhǔn)是以沿著邊的流動為特征，還有一些標(biāo)準(zhǔn)以步行結(jié)構(gòu)（Walk Structure）為特征。 一些最常用的標(biāo)準(zhǔn)是： 度中心性（Degree Centrality） - 第一個(gè)也是概念上最簡單的中心性定義。表示連接到某節(jié)點(diǎn)的邊數(shù)。在有向圖中，我們可以有2個(gè)度中心性度量。流入和流出的中心性。 緊密中心性（Closeness Centrality） - 從某節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑的平均長度。 中介中心性（Betweenness Centrality） - 某節(jié)點(diǎn)在多少對節(jié)點(diǎn)的最短路徑上。
這些中心性度量有不同變種，并且可以使用各種算法來實(shí)現(xiàn)定義。總而言之，這方面有大量的定義和算法。 網(wǎng)絡(luò)密度 圖的邊數(shù)的度量。實(shí)際定義將根據(jù)圖的類型和所提問問題的上下文而不同。對于完備的無向圖，密度為1，而空圖（empty）為0。在某些情況下（包含循環(huán)時(shí)），圖密度可能大于1。 圖隨機(jī)化（Graph Randomization） 盡管一些圖度量指標(biāo)可能很容易計(jì)算，但要理解它們的相對重要性并不容易。在這種情況下，我們使用網(wǎng)絡(luò)/圖隨機(jī)化。我們計(jì)算了手頭的圖和隨機(jī)生成的另一些類似圖的度量。例如，這些相似圖可以有相同數(shù)量的密度和節(jié)點(diǎn)。通常我們生成1000個(gè)相似的隨機(jī)圖并計(jì)算每個(gè)圖的度量標(biāo)準(zhǔn)，然后與手頭圖的相同度量進(jìn)行比較，以得出某些基準(zhǔn)（benchmark）。 在數(shù)據(jù)科學(xué)中，當(dāng)嘗試對某個(gè)圖進(jìn)行聲明時(shí)，如果與某些隨機(jī)生成的圖進(jìn)行對比，則會有所幫助。
熟悉Python中的圖
我們將在Python中使用networkx包。它可以安裝在Anaconda的Root環(huán)境中（如果你使用的是Anaconda的Python分發(fā)版）。你也可以pip install安裝它。 讓我們看一下使用Networkx軟件包可以完成的一些常見事情。包括導(dǎo)入和創(chuàng)建圖以及可視化圖的方法。
圖形創(chuàng)建
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
通過傳遞包含節(jié)點(diǎn)和屬性dict的元組，可以在創(chuàng)建節(jié)點(diǎn)和邊的時(shí)候添加節(jié)點(diǎn)和邊的屬性。 除了逐個(gè)節(jié)點(diǎn)或逐個(gè)邊地構(gòu)建圖形之外，還可以通過一些經(jīng)典的圖操作來生成它們，例如：
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
對于不同類型的圖，存在單獨(dú)的類。例如，nx.DiGraph類允許創(chuàng)建有向圖?？梢允褂脝蝹€(gè)方法直接創(chuàng)建包含路徑的特定圖。有關(guān)圖創(chuàng)建方法的完整列表，請參閱完整文檔。鏈接在本文末尾給出。
Image('images/graphclasses.PNG', width = 400)
訪問邊和節(jié)點(diǎn) 可以使用G.nodes和G.edges方法訪問節(jié)點(diǎn)和邊?？梢允褂美ㄌ?下標(biāo)法訪問各個(gè)節(jié)點(diǎn)和邊。
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提供了可視化圖的基本功能，但其主要目標(biāo)是幫助圖分析而不是圖的可視化。圖可視化很難，我們將使用專門用于此任務(wù)的工具。Matplotlib提供了一些便利功能。但是GraphViz可能是最好的工具，因?yàn)樗峁┝艘粋€(gè)PyGraphViz的Python接口（鏈接在文檔的末尾）。
%matplotlib inline import matplotlib.pyplot as plt nx.draw(G)
首先必須安裝Graphviz。然后使用該命令pip install pygraphviz --install-option =“<>。在安裝選項(xiàng)中，你必須提供Graphviz 中l(wèi)ib和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可以很好地控制邊和節(jié)點(diǎn)的各個(gè)屬性。我們可以使用它獲得非常漂亮的可視化。 # 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.
通常，可視化被認(rèn)為是與圖分析獨(dú)立的任務(wù)。分析后的圖將導(dǎo)出為Dotfile。然后單獨(dú)顯示該Dotfile以展示我們想表達(dá)的內(nèi)容。
數(shù)據(jù)分析案例
我們將尋找一個(gè)通用數(shù)據(jù)集（不是專門用于圖的數(shù)據(jù)集）并進(jìn)行一些操作（在pandas中），以便它可以以邊列表（edge list）的形式輸入到圖中。邊列表是一個(gè)元組列表，其中的元組包含定義每條邊的頂點(diǎn) 我們將關(guān)注的數(shù)據(jù)集來自航空業(yè)。它有一些關(guān)于航線的基本信息。有某段旅程的起始點(diǎn)和目的地。還有一些列表示每段旅程的到達(dá)和起飛時(shí)間。如你所想，這個(gè)數(shù)據(jù)集非常適合作為圖進(jìn)行分析。想象一下通過航線（邊）連接的幾個(gè)城市（節(jié)點(diǎn)）。如果你是航空公司，你可以問如下幾個(gè)問題：
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'
現(xiàn)在時(shí)間列被轉(zhuǎn)換成了我們想要的格式。最后，我們可能希望將年，月和日列合并到日期列中。這一步不是絕對必要的。但是，一旦轉(zhuǎn)換為日期時(shí)間（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'])
現(xiàn)在使用networkx函數(shù)導(dǎo)入數(shù)據(jù)集，該函數(shù)直接讀如pandas DataFrame。就像圖創(chuàng)建一樣，多種方法可以將數(shù)據(jù)從多種格式中輸入到圖中。
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}
從可視化中（上面的方式）可以明顯看出 - 從一些機(jī)場到其他機(jī)場有多條路徑。 假如想要計(jì)算2個(gè)機(jī)場之間的最短路線。我們可以想到幾種方法：
我們可以通過距離或飛行時(shí)間來給路徑賦予權(quán)重，并用算法計(jì)算最短路徑。請注意，這是一個(gè)近似的解決方案 - 實(shí)際問題是計(jì)算當(dāng)你到達(dá)中轉(zhuǎn)機(jī)場時(shí)的航班可用性加候機(jī)的等待時(shí)間，這才是一種更完整的方法，也是人們計(jì)劃旅行的方式。出于本文的目的，我們將假設(shè)你到達(dá)機(jī)場時(shí)可以隨時(shí)使用航班并使用飛行時(shí)間作為權(quán)重，從而計(jì)算最短路徑。 讓我們以JAX和DFW機(jī)場為例：
# 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./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']
結(jié)語
本文充其量只是對圖論和網(wǎng)絡(luò)分析這一非常有趣的領(lǐng)域進(jìn)行了粗淺的介紹。對理論和Python軟件包的了解將為任何數(shù)據(jù)科學(xué)家的工具庫增加一個(gè)有價(jià)值的工具。 對于上面使用的數(shù)據(jù)集，可以提出一系列其他問題，例如： 在給定成本，飛行時(shí)間和可用性的情況下，找到兩個(gè)機(jī)場之間的最短路徑？ 作為一家航空公司，你們擁有一隊(duì)飛機(jī)。你了解航班的需求。假設(shè)你有權(quán)再運(yùn)營2架飛機(jī)（或者為你的機(jī)隊(duì)添加2架飛機(jī)），把這兩架飛機(jī)投入到哪條航線可以最大限度地提高盈利能力？ 你可以重新安排航班和時(shí)刻表以優(yōu)化某個(gè)參數(shù)嗎？（如時(shí)效性或盈利能力等）
如果你解決了這些問題，請?jiān)谙旅娴脑u論中告訴我們！ 網(wǎng)絡(luò)分析將有助于解決一些常見的數(shù)據(jù)科學(xué)問題，并在更大規(guī)模和抽象的情況下對其進(jìn)行可視化。如果想了解更多有關(guān)其他內(nèi)容的信息，請發(fā)表評論。 參考文獻(xiàn)
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
原文標(biāo)題：An Introduction to Graph Theory and Network Analysis (with Python codes)鏈接： https://www./blog/2018/04/introduction-to-graph-theory-network-analysis-python-codes/
和中華，留德軟件工程碩士。由于對機(jī)器學(xué)習(xí)感興趣，碩士論文選擇了利用遺傳算法思想改進(jìn)傳統(tǒng)kmeans。目前在杭州進(jìn)行大數(shù)據(jù)相關(guān)實(shí)踐。加入數(shù)據(jù)派THU希望為IT同行們盡自己一份綿薄之力，也希望結(jié)交許多志趣相投的小伙伴。 工作內(nèi)容：需要一顆細(xì)致的心，將選取好的外文文章翻譯成流暢的中文。如果你是數(shù)據(jù)科學(xué)/統(tǒng)計(jì)學(xué)/計(jì)算機(jī)類的留學(xué)生，或在海外從事相關(guān)工作，或?qū)ψ约和庹Z水平有信心的朋友歡迎加入翻譯小組。
你能得到：定期的翻譯培訓(xùn)提高志愿者的翻譯水平，提高對于數(shù)據(jù)科學(xué)前沿的認(rèn)知，海外的朋友可以和國內(nèi)技術(shù)應(yīng)用發(fā)展保持聯(lián)系，THU數(shù)據(jù)派產(chǎn)學(xué)研的背景為志愿者帶來好的發(fā)展機(jī)遇。 其他福利：來自于名企的數(shù)據(jù)科學(xué)工作者，北大清華以及海外等名校學(xué)生他們都將成為你在翻譯小組的伙伴。
|
