在本文中，我將討論一些你應該知道的最重要的圖算法，以及如何使用Python實現它們。

作者：AI公園

導讀

因為圖分析是數據科學家的未來。

作為數據科學家，我們對pandas、SQL或任何其他關系數據庫非常熟悉。

我們習慣于將用戶的屬性以列的形式顯示在行中。但現實世界真的是這樣嗎?

在一個互聯的世界里，用戶不能被視為獨立的實體。它們之間有一定的關系，我們在建立機器學習模型的時候，有時也會考慮這些關系。

現在，雖然在關系數據庫中，我們不能在不同的行(用戶)之間使用這樣的關系，但是在圖形數據庫中，這樣做非常簡單。

在本文中，我將討論一些你應該知道的最重要的圖算法，以及如何使用Python實現它們。

1. 連通組件

一個包含3個連通組件的圖

我們都知道聚類是如何工作的。

你可以用外行人的術語來理解連通組件，它是一種硬聚類算法，可以在相關/連接的數據中找到聚類/島嶼

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

你將如何實現這一點?來想想吧。

我們使用的連通組件算法是基于BFS/DFS的特殊情況。我不會在這里過多地討論它是如何工作的，但是我們將看到如何使用Networkx編寫和運行代碼。

應用

從零售的角度來看：假設我們有很多客戶，使用很多賬戶。使用連通組件算法的一種方法是在數據集中找出明顯不同的家族。

我們可以根據相同的信用卡使用情況、相同的地址或相同的移動電話號碼等設定客戶ID之間的邊(路)。一旦我們有了這些連接，我們就可以運行連通組件算法來創建單獨的簇，然后我們可以為其分配一個家族ID。

然后，我們可以使用這些家族ID根據家族需求提供個性化的推薦。我們還可以使用這個家族ID，通過創建基于家族的分組特征來支持我們的分類算法。

從財務的角度來看：另一個用例是使用這些家族ID捕獲欺詐。如果一個賬戶在過去有過欺詐行為，關聯賬戶很可能也容易進行欺詐。

可能性只受你自己想象力的限制。

代碼

我們將使用Python中的Networkx模塊來創建和分析圖。

讓我們從一個示例圖開始，我們使用它來實現我們的目的。包含城市和城市之間的距離信息。

使用隨機距離的圖

我們首先創建一個帶有距離的邊的列表，我們把距離作為邊的權重：

使用Networkx構建圖：

現在我們想從這張圖中找出不同的大陸及其包含的城市。

我們現在可以使用連通組件算法做到這一點：

正如你所看到的，我們能夠在數據中找到不同的部分。只需要使用邊和頂點。這個算法可以在不同的數據上運行，以滿足我上面提到的任何用例。

2. 最短路徑

繼續上面的例子，我們得到了一個德國城市的圖以及它們之間的距離。

你想知道如何從法蘭克福(起始節點)到慕尼黑的最短距離。

我們用來解決這個問題的算法叫做Dijkstra。用Dijkstra自己的話來說：

從鹿特丹到[格羅寧根的最短路線是什么?一般來說，最短路徑的算法是這樣的，我花了大約20分鐘來設計它。一天早上我在阿姆斯特丹和我的年輕的未婚妻購物，累了，我們坐在咖啡館露臺喝一杯咖啡，我就在想我能不能想出這個最短路徑算法，然后我就想出來了。正如我所說，這是一個20分鐘的發明。事實上，它是在1959年出版的。三年后，還可以讀到，事實上，它相當不錯。它如此漂亮的原因之一是我不用鉛筆和紙來設計它。后來我了解到，不用鉛筆和紙設計的好處之一是，你幾乎不得不避免所有可以避免的復雜性。最終，令我大為驚訝的是，這個算法成了我成名的基石之一。

- Edsger Dijkstra，在對Philip L. Frana的采訪中

應用

Dijkstra算法的變體廣泛應用于谷歌地圖中，用于尋找最短路徑。

你在沃爾瑪，你有不同的通道和所有通道之間的距離。你想要提供從A通道到D通道到客戶的最短路徑。

你可以看到LinkedIn如何顯示1級和2級的連接。幕后發生了什么?

代碼

你也可以找到所有的地點對之間的最短路徑：

3. 最小生成樹

現在我們有另一個問題。我們為一家水管鋪設公司或互聯網光纖公司工作。我們需要用最少的電線/管道連接圖中所有的城市，我們該怎么做?

一個無向圖，右邊是它的最小生成樹

應用

最小生成樹直接應用于網絡設計，包括計算機網絡、電信網絡、交通網絡、供水網絡和電網(它們最初是為這些網絡而發明的)

MST用于逼近旅行商問題

聚類 — 首先構造MST，然后使用簇間距離和簇內距離確定MST中某些邊緣的分割閾值。

圖像分割 — 用于圖像分割，我們首先在一個圖上構造一個MST，其中像素是節點，像素之間的距離基于一些相似性度量(顏色、強度等)。

代碼

我們的圖的最小生成樹

可以看到，上面就是我們需要鋪設的電線。

4. Pagerank

這就是長期以來支持谷歌的頁面排序算法。它根據輸入和輸出鏈接的數量和質量為頁面分配一個分數。

應用

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

它被用來尋找最具影響力的論文使用引文。

被谷歌用來排列頁面

它可以用來把tweets-用戶和以及tweets-tweets當成節點進行排序。如果用戶A關注了用戶B，那么創建用戶之間的鏈接，如果用戶tweet/retwets一條tweet，則創建用戶和tweet之間的鏈接。

推薦引擎

代碼

在這個練習中，我們將使用Facebook數據。我們有一個facebook用戶之間的邊/鏈接文件。我們首先創建FB圖，使用：

它是這樣的：

FaceBook用戶圖

現在我們想要找到具有高影響力的用戶。

直觀地說，Pagerank算法會給有很多朋友的用戶打高分，而這些朋友又有很多facebook上的朋友。

我們可以用PageRank得到最有影響力的用戶排序：

以上id適用于最有影響力的用戶。

我們可以看到最具影響力用戶的子圖：

最有影響力的用戶(黃色)

5. 中心度量

有許多中心度量，你都可以將其用作機器學習模型的特征。我將討論其中的兩個。

內中心：重要的不僅是擁有最多朋友的用戶，將一個地理位置與另一個地理位置連接起來的用戶也很重要，因為這讓用戶可以看到來自不同地理位置的內容。內中心度量了一個特定節點在另外兩個節點之間的最短路徑中出現的次數

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

應用

中心度量可以作為任何機器學習模型的一個特征。

代碼

面的代碼用于查找子圖的內中心。

可以看到，在這里按它們的內中心值調整節點的大小。他們可以被認為是信息傳遞者。將具有高內中心的任何節點斷開將會將圖分成許多部分。

總結

在這篇文章中，我討論了一些最具影響力的圖算法，它們改變了我們的生活方式

隨著如此多的社會數據的出現，網絡分析可以在很大程度上幫助我們改進模型和產生價值。

甚至更多地了解這個世界。