在互聯世界中，用戶不能被視為獨立的實體。他們之間存在一定的關系，我們有時希望在構建機器學習模型時考慮到這些關系。

在關系數據庫中，我們無法在不同的行（用戶）之間利用這種關系，但在圖數據庫中，這樣做非常簡單。

在這篇文章中，我們將討論一些數據科學家應該了解的非常重要的圖算法，以及如何使用 Python 實現它們。

連接組件

我們都知道聚類的工作機制，你可以將連接組件視為一種在關聯/連接數據中查找集群/個體的硬聚類算法。

舉個例子：假設你有連接世界上任何兩個城市道路的數據。現在你需要找出世界上所有大洲以及它們所包含的城市。

你將如何實現這一目標呢？

我們采用的連接組件算法是基于廣度優先搜索算法（Breadth First Search，BFS）/深度優先搜索算法（Depth First Search，DFS）的特殊情況。這里不再展開介紹工作原理，我們只看一下如何使用 Networkx 啟動和運行此代碼。

應用

從零售角度看：假設我們有很多客戶使用大量賬戶。使用連接組件算法的一種方法是在這個數據集中找出不同的族。

我們可以根據相同的信用卡使用情況、相同地址、相同手機號碼來建立某些客戶 ID 之間的連接。一旦有這些連接，我們就可以運行連接組件算法為有連接的客戶創建單個集群，然后為其分配一個家庭 ID。

然后，我們可以利用這些家庭 ID，根據家庭需求提供個性化推薦。我們還可以利用家庭 ID，通過創建基于家庭的分組功能來推進分類算法。

從金融角度：另一個用例是利用這些家庭 ID 抓捕詐騙犯。如果某個帳戶有過被欺詐經歷，那么關聯帳戶很容易再次受到欺詐。

實施的可能性僅僅受到自身想象力的限制。（想象力越豐富，算法的應用越廣泛。）

代碼

我們將使用 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'} 

如你所見，只需要利用頂點和邊，我們就能夠在數據中找到不同的組件。該算法可以在不同的數據上運行，從而滿足上面提到的各種用例。

最短路徑

繼續使用上述示例，現在我們有德國城市及城市之間距離的圖。如何找到從法蘭克福（起始節點）到慕尼黑的最短距離？我們用來解決此問題的算法被稱為 Dijkstra。用 Dijkstra 自己的話說：

從鹿特丹到格羅寧根旅行的最短路線是什么？這就是最短路徑算法，我花了大約 20 分鐘設計了它。一天早上，我和我的未婚妻在阿姆斯特丹購物，累了，我們便坐在咖啡館的露臺上喝咖啡，我只想著能否實現最短路徑算法，然后我成功了。

正如我所說，這是一個二十分鐘的發明。事實上，它發表于 1959 年，現在來看它的可讀性也非常高。它之所以如此美妙，其中一個原因就是我沒用筆紙就設計了它。后來我才知道，沒有筆紙設計的有點之一是你不得不避免所有可避免的復雜問題。最終，令我驚訝的是，這個算法成為我的著名成果之一。

應用

Dijkstra 算法的變體在 Google 地圖中有著廣泛使用，用于尋找最短路線。

假設你有沃爾瑪商店中各個過道位置和過道之間距離的數據。您希望為從 A 到 D 的顧客提供最短路徑。

你已經看到 LinkedIn 顯示一級連接和二級連接的方式。而這背后的機制是什么呢？

代碼

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']}) 
.... 

最小生成樹（Minimum Spanning Tree，MST）

現在我們面臨另一個問題。假設我們在水管鋪設公司或電線公司工作。我們需要使用最少的電線/管道來連接圖中所有城市。我們如何做到這一點？

左： 無向圖； 右： 對應 MST

應用

• 最小生成樹在網絡設計中有直接應用，包括計算機網絡、電信網絡、交通網絡、供水網絡和電網（最初是為它們發明的）。

• MST 用于近似旅行商問題。

• 聚類：首先構建 MST，然后使用類間距離和類內距離確定閾值，用于打破 MST 中某些邊。

• 圖像分割：首先在圖上構建 MST，其中像素是節點，像素之間的距離基于某種相似性度量（顏色、強度等）

代碼

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

左： 無向圖； 右： 對應 MST.

Pagerank

上圖為谷歌提供長期支持的頁面排序算法（page sorting algorithm）。它根據輸入和輸出鏈接的數量和質量為頁面打分。

應用

Pagerank 可用于任何我們想要估算網絡節點重要性的地方。

• 它已被用于查找影響力最高的論文；

• 它已被 Google 用于網頁排名；

• 它可用于將推文-用戶和推文排序為節點。如果用戶 A 跟帖用戶 B，則在用戶之間創建鏈接；如果用戶發推/轉推，則在用戶和推文之間建立鏈接；

• 推薦引擎。

代碼

在本次練習中，我們將使用 Facebook 數據。我們在 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() 

Facebook 用戶圖

現在我們想要找出具有高影響力的用戶。直觀地說，Pagerank 算法會給擁有很多朋友的用戶打高分，而這些朋友又擁有很多 Facebook 朋友。

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),......] 

以上 ID 即為最有影響力的用戶。最具影響力用戶的子圖如下所示：

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() 

黃色為最具影響力用戶

中心性度量

你可以將許多中心性度量用作機器學習模型的特征，這里只談其中的兩個。

其他度量鏈接：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。

介數中心性：不僅擁有眾多朋友的用戶很重要，將一個地理位置連接到另一個位置的用戶也很重要，因為這樣可以讓用戶看到不同地點的內容。

介數中心性量化了一個特定節點在其他兩個節點之間最短路徑中出現的次數。

點度中心性：它只是節點的連接數。

代碼

以下是查找子圖介數中心性的代碼：

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') 

你可以在此處查看按介數中心性值確定大小的節點。他們可以被認為是信息傳遞者。打破任何具有高介數中心性的節點將會將圖形分成許多部分。