Python學習教程：5個你一定要知道的圖算法，附Python代碼

相信大家已經對 Pandas 或 SQL 等其他關系數據庫非常熟悉了。我們習慣于將行中的用戶視為列。但現實世界的表現真的如此嗎？

在互聯世界中，用戶不能被視為獨立實體。他們之間具有一定的關系，在構建機器學習模型時，有時也希望包含這樣的關系。

在關系型數據庫中，我們無法在不同的行（用戶）之間使用這種關系，但在圖形數據庫中，這樣做是相當簡單的。 在這篇Python學習教程中將為大家介紹一些重要的圖算法，以及Python 的代碼實現。

1、連通分量

具有三個連通分量的圖

將上圖中的連通分量算法近似看作一種硬聚類算法，該算法旨在尋找相關數據的簇類。舉一個具體的例子：假設擁有連接世界上任意城市的路網數據，我們需要找出世界上所有的大陸，以及它們所包含的城市。我們該如何實現這一目標呢？

基于BFS / DFS的連通分量算法能夠達成這一目的，接下來，我們將用 Networkx 實現這一算法。

代碼

使用 Python 中的 Networkx 模塊來創建和分析圖數據庫。如下面的示意圖所示，圖中包含了各個城市和它們之間的距離信息。

示意圖

首先創建邊的列表，列表中每個元素包含兩個城市的名稱，以及它們之間的距離。

edgelist = [['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250],["Mumbai", "Delhi",400],["Delhi", "Kolkata",500],["Kolkata", "Bangalore",600],["TX", "NY",1200],["ALB", "NY",800]]

然后，使用 Networkx 創建圖：

g = nx.Graph()
for edge in edgelist:
 g.add_edge(edge[0],edge[1], weight = edge[2])

現在，我們想從這張圖中找出不同的大陸及其包含的城市。我們可以使用使用連通分量算法來執行此操作：

for i, x in enumerate(nx.connected_components(g)):
 print("cc"+str(i)+":",x)
cc0: {'Frankfurt', 'Kassel', 'Munchen', 'Numberg', 'Erfurt', 'Stuttgart', 'Karlsruhe', 'Wurzburg', 'Mannheim', 'Augsburg'}
cc1: {'Kolkata', 'Bangalore', 'Mumbai', 'Delhi'}
cc2: {'ALB', 'NY', 'TX'}

從結果中可以看出，只需使用邊緣和頂點，我們就能在數據中找到不同的連通分量。 該算法可以在不同的數據上運行，以滿足前文提到的兩種其他運用。

應用：

零售：很多客戶使用大量賬戶，可以利用連通分量算法尋找數據集中的不同簇類。假設使用相同信用卡的客戶 ID 存在連邊（edges），或者將該條件替換為相同的住址，或者相同的電話等。一旦我們有了這些連接的邊，就可以使用連通分量算法來對客戶 ID 進行聚類，并對每個簇類分配一個家庭 ID。然后，通過使用這些家庭 ID，我們可以根據家庭需求提供個性化建議。此外，通過創建基于家庭的分組功能，我們還能夠提高分類算法的性能。

財務：我們可以利用這些家庭 ID 來識別金融欺詐。如果某個賬戶曾經有過欺詐行為，那么它的關聯帳戶很可能發生欺詐行為。

2、最短路徑

繼續第一節中的例子，我們擁有了德國的城市群及其相互距離的圖表。為了計算從法蘭克福前往慕尼黑的最短路徑，我們需要用到 Dijkstra 算法。Dijkstra 是這樣描述他的算法的：

從鹿特丹到格羅寧根的最短途徑是什么？或者換句話說：從特定城市到特定城市的最短路徑是什么？這便是最短路徑算法，而我只用了二十分鐘就完成了該算法的設計。 一天早上，我和未婚妻在阿姆斯特丹購物，我們逛累了，便在咖啡館的露臺上喝了一杯咖啡。而我，就想著我能夠做到這一點，于是我就設計了這個最短路徑算法。正如我所說，這是一個二十分鐘的發明。事實上，它發表于1959年，也就是三年后。它之所以如此美妙，其中一個原因在于我沒有用鉛筆和紙張就設計了它。后來我才知道，沒有鉛筆和紙的設計的一個優點就是，你幾乎被迫避免所有可避免的復雜性。最終，這個算法讓我感到非常驚訝，而且也成為了我名聲的基石之一。——Edsger Dijkstra于2001年接受ACM通訊公司 Philip L. Frana 的采訪時的回答

代碼

print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight'))
print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))
['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']
503

使用以下命令可以找到所有對之間的最短路徑：

for x in nx.all_pairs_dijkstra_path(g,weight='weight'):
 print(x)
('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
....

應用

• Dijkstra 算法的變體在 Google 地圖中廣泛使用，用于計算最短的路線。
• 想象身處在沃爾瑪商店，我們知道了各個過道之間的距離，我們希望為從過道 A 到過道 D 的客戶提供最短路徑。

• 如下圖所示，當我們知道了領英中用戶的一級連接、二級連接時，如何得知幕后的信息呢？Dijkstra 算法可以幫到我們。

3、最小生成樹

假設我們在水管工程公司或互聯網光纖公司工作，我們需要使用最少的電線（或者管道）連接圖表中的所有城市。我們如何做到這一點？

無向圖和它的最小生成樹

代碼

# nx.minimum_spanning_tree(g) returns a instance of type graph
nx.draw_networkx(nx.minimum_spanning_tree(g))

使用最小生成樹算法鋪設電線

應用

• 最小生成樹在網絡設計中有著最直接的應用，包括計算機網絡，電信網絡，運輸網絡，供水網絡和電網。（最小生成樹最初就是為此發明的）
• 最小生成樹可用于求解旅行商問題的近似解
• 聚類——首先構造最小生成樹，然后使用類間距離和類內距離來設定閾值，從而破壞最小生成樹中的某些連邊，最終完成聚類的目的
• 圖像分割——首先在圖形上構建最小生成樹，其中像素是節點，像素之間的距離基于某種相似性度量（例如顏色，強度等），然后進行圖的分割。

4、網頁排序（Pagerank）

Pagerank 是為谷歌提供長期支持的頁面排序算法。根據輸入和輸出鏈接的數量和質量，該算法對每個頁面進行打分。

代碼

在本節中，我們將使用 Facebook 數據。首先，利用 Facebook 用戶之間的連接，我們使用以下方法創建圖：

# reading the dataset
fb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)

將圖進行可視化：

pos = nx.spring_layout(fb)
import warnings
warnings.filterwarnings('ignore')
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(fb, pos, with_labels = False, node_size = 35)
plt.show()

現在，我們想要找到具有高影響力的用戶。直觀上來講，Pagerank 會給擁有很多朋友的用戶提供更高的分數，而這些用戶的朋友反過來會擁有很多朋友。

pageranks = nx.pagerank(fb)
print(pageranks)
------------------------------------------------------
{0: 0.006289602618466542,
 1: 0.00023590202311540972,
 2: 0.00020310565091694562,
 3: 0.00022552359869430617,
 4: 0.00023849264701222462,
........}

使用如下代碼，我們可以獲取排序后 PageRank 值，或者最具有影響力的用戶：

import operator
sorted_pagerank = sorted(pagerank.items(), key=operator.itemgetter(1),reverse = True)
print(sorted_pagerank)
------------------------------------------------------
[(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262), (698, 0.0013171153138368807), (483, 0.0012974283300616082), (3830, 0.0011844348977671688), (376, 0.0009014073664792464), (2047, 0.000841029154597401), (56, 0.0008039024292749443), (25, 0.000800412660519768), (828, 0.0007886905420662135), (322, 0.0007867992190291396),......]

將含有最具影響力用戶的子圖進行可視化：

first_degree_connected_nodes = list(fb.neighbors(3437))
second_degree_connected_nodes = []
for x in first_degree_connected_nodes:
 second_degree_connected_nodes+=list(fb.neighbors(x))
second_degree_connected_nodes.remove(3437)
second_degree_connected_nodes = list(set(second_degree_connected_nodes))
subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)
pos = nx.spring_layout(subgraph_3437)
node_color = ['yellow' if v == 3437 else 'red' for v in subgraph_3437]
node_size = [1000 if v == 3437 else 35 for v in subgraph_3437]
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(subgraph_3437, pos, with_labels = False, node_color=node_color,node_size=node_size )
plt.show()

黃色的節點代表最具影響力的用戶

應用

Pagerank 可以估算任何網絡中節點的重要性。

• 已被用于根據引文尋找最具影響力的論文
• 已被谷歌用于網頁排名
• 它可以對推文進行排名，其中，用戶和推文作為網絡的節點。如果用戶 A 跟隨用戶 B，則在用戶之間創建連邊；如果用戶推文或者轉發推文，則在用戶和推文之間建立連邊。
• 用于推薦系統

5、中心性度量

一些中心性度量的指標可以作為機器學習模型的特征，我們主要介紹其中的兩個指標

• 介數中心性：擁有最多朋友的用戶很重要，而起到橋梁作用、將一個領域和另一個領域進行連接的用戶也很重要，因為這樣可以讓更多的用戶看到不同領域的內容。介數中心性衡量了特定節點出現在兩個其他節點之間最短路徑集的次數。
• 度中心性：即節點的連接數。

代碼

使用下面的代碼可以計算子圖的介數中心性：

pos = nx.spring_layout(subgraph_3437)
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size = [v * 10000 for v in betweennessCentrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
 node_size=node_size )
plt.axis('off')

如上圖所示，節點的尺寸大小和介數中心性的大小成正比。具有較高介數中心性的節點被認為是信息的傳遞者，移除任意高介數中心性的節點將會撕裂網絡，將完整的圖打碎成幾個互不連通的子圖。

應用

中心性度量的指標可以作為機器學習模型的特征。

總結

在這篇文章中，我們介紹了了一些最有影響力的圖算法。隨著社交數據的出現，圖網絡分析可以幫助我們改進模型和創造價值，甚至更多地了解這個世界。