圖論與圖學習（二）：圖演算法

選自towardsdatascience

作者：Ma?l Fabien

機器之心編譯

參與：熊貓

圖（graph）近來正逐漸變成機器學習的一大核心領域，比如你可以通過預測潛在的連接來理解社交網路的結構、檢測欺詐、理解汽車租賃服務的消費者行為或進行實時推薦。近日，數據科學家 Ma?l Fabien 在其博客上發布了涉及圖論、圖演算法和圖學習的系列文章《圖論與圖學習》。

本文是其中第二篇，介紹了圖演算法。更多文章和對應代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials

本文涵蓋以下主題：

主要的圖演算法

示意圖和用例

Python 示例

首先進行一些準備工作，打開 Jupyter Notebook，導入以下軟體包：

後文會使用 networkx 最新的 2.0 版本。networkx 是一個用於複雜網路的結構、動態和功能的創建、操作和研究的 Python 軟體包。

我會盡量以實用為目標，努力闡釋每個概念。

前一篇文章介紹了圖的主要種類以及描述一個圖的基本特性。現在我們更加詳細地介紹圖分析/演算法以及分析圖的不同方式。

為了理解上下文，這裡給出一些圖演算法的用例：

實時欺詐檢測

實時推薦

精簡法規遵從性

複雜網路的管理和監控

身份和訪問管理

社交應用/功能

…

目前大多數框架（比如 Python 的 networkx 或 Neo4J）支持的圖演算法類別主要有三個：

Pathfinding（尋路）：根據可用性和質量等條件確定最優路徑。我們也將搜索演算法包含在這一類別中。這可用於確定最快路由或流量路由。

Centrality（中心性）：確定網路中節點的重要性。這可用於識別社交網路中有影響力的人或識別網路中潛在的攻擊目標。

Community detection（社群檢測）：評估群體聚類的方式。這可用於劃分客戶或檢測欺詐等。

我們將在第三篇文章中介紹圖中的機器學習和圖學習。

networkx 中的所有演算法都可在這裡找到：https://networkx.github.io/documentation/stable/reference/algorithms/index.html

我們只會介紹 networkx 中實現的最常見的基本演算法。

一 尋路和圖搜索演算法

尋路演算法是通過最小化跳（hop）的數量來尋找兩個節點之間的最短路徑。

搜索演算法不是給出最短路徑，而是根據圖的相鄰情況或深度來探索圖。這可用於信息檢索。

1. 搜索演算法

圖搜索演算法主要有兩種：

寬度優先搜索（BFS）：首先探索每個節點的相鄰節點，然後探索相鄰節點的相鄰節點……

深度優先搜索（DFS）：會嘗試儘可能地深入一條路徑，如有可能便訪問新的相鄰節點。

搜索演算法

2. 尋路演算法

a. 最短路徑

最短路徑計算的是一對節點之間的最短的加權（如果圖有加權的話）路徑。

這可用於確定最優的駕駛方向或社交網路上兩個人之間的分離程度。

計算圖中的最短路徑的方法有很多，包括 Dijkstra 演算法，這是 networkx 中的默認演算法。

根據維基百科，該演算法的偽代碼如下：

將圖中所有節點標記為未訪問。創建一個所有未訪問節點的集合，稱為未訪問集。

為每個節點分配一個暫定的距離值：將我們的初始節點的該值設置為零，將其它所有節點的該值設置為無窮。將初始起始節點設置為當前節點。

對於當前節點，考察其所有未被訪問過的相鄰節點並計算通過當前節點的暫定距離。比較新計算出的暫定距離與當前分配的值，配之以其中更小的值。舉個例子，如果當前節點 A 標記的距離為 6，將其與相鄰節點 B 連接的邊的長度為 2，則通過 A 到達 B 的距離為 6 2=8。如果 B 之前被標記的距離大於 8，則將其改為 8。否則，保持其當前的值。

當我們考察完當前節點的所有未訪問節點時，將當前節點標記為已訪問，並將其移出未訪問集。已訪問節點不會再次進行檢查。

如果目標節點已被標記為已訪問（當規劃兩個特定節點之間的路由時）或未訪問集中節點之間的最小暫定距離為無窮時（當規劃一次完整的遍歷時；當初始節點與剩餘的未訪問節點之間沒有連接時才會出現這種情況），那麼就停止操作。演算法結束。

否則，選擇標記有最小暫定距離的未訪問節點，將其設置為新的「當前節點」，然後回到步驟 3。

更多有關最短路徑問題的介紹請參閱：https://en.wikipedia.org/wiki/Shortest_path_problem

維基百科上 Dijkstra 演算法示意圖

該演算法的 Python 實現簡單直接：

這會返回圖中每個節點之間的最小路徑的列表：

b. 單源最短路徑

單源最短路徑（Single Source Shortest Path/SSSP）是找到給定節點與圖中其它所有節點之間的最短路徑。

這常用於 IP 網路的路由協議。

c. 所有配對最短路徑

所有配對最短路徑（All Pairs Shortest Path / APSP）演算法是找到所有節點對之間的最短路徑。

儘管能夠提供相近的結果，但這比為每個節點對調用單源最短路徑演算法更快。該演算法通常可用於確定交通網格的不同分區的流量負載。

這會返回：

d. 最小權重生成樹

最小權重生成樹（minimum spanning tree）是圖（一個樹）的一個子圖，其用權重和最小的邊連接了圖中的所有節點。

最小生成樹應該用於無向圖。

這會返回：

二 社群檢測

社群檢測是根據給定的質量指標將節點劃分為多個分組。

這通常可用於識別社交社群、客戶行為或網頁主題。

社區是指一組相連節點的集合。但是，目前關於社群還沒有廣泛公認的定義，只是社群內的節點應該要密集地相連。

社群

Girvan Newman 演算法是一個用於發現社群的常用演算法。其通過逐步移除網路內的邊來定義社區。我們將居間性稱為「邊居間性（edge betweenness）」。這是一個正比於穿過該邊的節點對之間最短路徑的數量的值。

該演算法的步驟如下：

計算網路中所有已有邊的居間性。

移除居間性最高的邊。

移除該邊後，重新計算所有邊的居間性。

重複步驟 2 和 3，直到不再剩餘邊。

你可以通過 Python 使用以下代碼實現它：

這會得到一個屬於每個社群的節點的列表（k=1 的意思是我們期望得到 2 個社群）：

如上給出的那樣，這個方法實在沒法擴展。由於這個原因，Louvain 等方法已被開發出來。但是，如果要運行大規模的圖，這些方法需要很長的時間。

3. Louvain 模塊性

在定義 Louvain 方法之前，需要介紹一下模塊性（modularity）的概念。模塊性是一個度量，衡量的是分組被劃分為聚類的程度：

模塊性

Louvain 方法的偽代碼如下：

首先為每個節點分配一個社群

交替執行接下來的兩個步驟，直到收斂

創建一個帶有相鄰節點的新社群，以最大化模塊性

創建一個新的加權的圖。之前步驟的社群變成圖的節點。

這個現在可能看起來有些讓人迷惑。事實上，我們現在唯一做的事情是將最近的節點劃分為分組，以便我們優化模塊性指標。

Louvain 方法

注意，Louvain 方法沒有理論上的保證，但實踐效果很好。Louvain 方法是 networkx 的一個子項目，參閱：https://python-louvain.readthedocs.io/en/latest/

首先，安裝軟體包：

然後，計算最佳的劃分方式（基於 Louvain 方法）：

使用 Louvain 對空手道圖執行的最佳劃分

4. 強互連的組分

強互連的組分（Strongly Connected Components /SCC）演算法能找到有向圖中的互連節點的分組。注意，在同一個分組中，每個節點都必須從任意其它節點從兩個方向都到達。

這通常用在圖分析過程的早期階段，能讓我們了解圖構建的方式。舉個例子，這能讓我們探索財務報表數據，了解誰擁有什麼公司的股份。

5. 弱互連的組分（並查集）

弱互連的組分（Weakly Connected Components），也稱為並查集（Union Find）演算法，能找到有向圖中的互連節點的集合，在同一個集合中，每個節點都可從任意其它節點到達。

這隻需要節點對之間在一個方向上存在一條路徑即可，而 SCC 則需要兩個方向都存在路徑。和 SCC 一樣，並查集通常用在分析的早期階段，以理解圖的結構。

並查集是一個預處理步驟，為了理解圖的結構，在任何演算法之前都是必需的。

我們可以使用下面的方法測試相連的有向圖：

或使用下面的方法測試無向圖：

這會返回一個布爾值。

一定要看看 networkx 文檔中有關連接性實現的問題：https://networkx.github.io/documentation/stable/reference/algorithms/component.html

6. 分層聚類

在分層聚類（hierarchical clustering）中，我們構建聚類的層次結構。我們用樹狀圖的形式表示聚類。

樹狀圖

其思想是以不同的規模分析社群結構。我們通常自下而上構建樹狀圖。我們從每個節點一個聚類開始，然後合併兩個「最近」的節點。

但我們如何衡量聚類是否相近呢？我們使用相似度距離。令 d(i,j) 為 i 和 j 之間的最短路徑的長度。

相似度距離

要得到最大連接，在每個步驟，被最短距離分開的兩個聚類被組合到一起。相似度距離可用以下示意圖闡釋：

連接方式

回到我們的空手道示例。在應用分層聚類之前，我們需要定義每個節點之間的距離矩陣。

現在，我們將使用 sklearn 的 AgglomerativeClustering 函數來確定分層聚類。

最後，根據聚類結果，用不同顏色繪出所得到的圖：

分層聚類

7. 聚類係數

聚類係數衡量的是兩個節點傾向於聚類到一起的程度。

局部聚類係數是以節點 i 為中心的三角形的數量與以節點 i 為中心的三節點的數量的比。某種程度而言，這衡量的是節點 i 與其相鄰節點接近完備圖（complete graph）的程度。

聚類係數

我通過以下圖演示了聚類係數的計算：

聚類係數

全局聚類係數衡量的是圖中三角形（局部聚類）的密度：

全局聚類係數

上面的圖的全局聚類係數為：

對於 Erdos-Rényi 隨機圖，E[Clustering Coefficient]=E[Ci]=p，其中 p 是前一篇文章中定義的概率。

對於 Baràbasi-Albert 隨機圖，全局聚類係數根據節點的數量遵循冪律。度為 k 的節點的平均聚類係數正比於 k 的倒數：

度較低的節點連接的是它們社群中的其它節點。度較高的節點連接的是其它社群的節點。

對於一個給定的圖，在 networkx 中，聚類係數很容易算出。首先，我們來計算局部聚類係數：

這會得到類似下面的結果：

然後平均這些結果，得到該圖的全局聚類稀疏：

這會得到：

三 中心度演算法

中心度（Centrality）衡量的是節點的重要程度。這並非一個明晰的定義，但如果我們想要確定重要的網頁、交通網路中的瓶頸……，那這就會很有用。

遊走（walk）是可以多次經過同一個節點的路徑。根據所考慮的遊走類型和統計它們的方式，中心度度量也會各有不同。

1. PageRank 演算法

PageRank 是根據所連接的相鄰節點，然後再根據它們各自的相鄰節點估計當前節點的重要性。

儘管是谷歌讓這種演算法流行起來的，但這種方法能夠用於檢測任何網路中的高影響力節點。比如可用在社交網路上進行推薦。

PageRank 要麼是通過在相鄰節點上迭代地分配節點的秩（原本是基於度）來計算，要麼是通過隨機遍歷圖並統計每次遊走期間到達每個節點的頻率來計算。

Neo4J 對 PageRank 演算法的總結

PageRank 通常是在有向圖上計算，但也可通過將有向圖中的每條邊轉換成兩條邊而在無向圖上執行。

舉個例子，空手道圖的 PageRank 可以這樣獲得：

其中 alpha 是阻尼參數（默認為 0.85）。這應該能返回一個排名列表：

2. 度中心度

度中心度（Degree Centrality）統計的是終止於節點 i 的長度為 1 的遊走的數量。

這能夠衡量傳入和傳出關係。這能通過 C(Xi)=di 給出。度中心度可用於識別社交網路中最有影響力的人。

3. 特徵向量中心度

特徵向量中心度（Eigenvector Centrality）是終止於節點 i 的長度為無窮的遊走的數量。

這能讓有很好連接相鄰節點的節點有更高的重要度。

特徵向量中心度

4. 接近度中心度

接近度中心度（Closeness Centrality）檢測的是可以在圖中有效傳播信息的節點。

這可用於識別假新聞賬戶或恐怖分子，以便隔離能向圖中其它部分傳播信息的個體。

接近度中心度反比於到其它節點的最短路徑長度的總和。

5. 居間性中心度

居間性中心度（Betweenness Centrality）檢測的是節點在圖中的信息流上所具有的影響量。

這通常可用於發現用作從圖的一部分到另一部分的橋的節點，比如用在電信網路的數據包傳遞處理器或假新聞傳播分析中。

其中：

σ_jk 是 j 和 k 之間的最短路徑的數量

σ_jk(i) 是 j 和 k 之間的經過 i 的最短路徑的數量

居間性中心度衡量的是一個節點用作兩個節點之間的橋的次數，比如：

中心度度量

Python 中實現依賴於 networkx 的內置函數：

不同的中心度度量

可以觀察到，不同的中心度度量關注的節點也不同。比如，居間性中心度得到的結果與其它方法的結果非常不同，因為它們衡量的不是同一個指標。

四 總結

現在我們已經介紹了圖的基礎知識、圖的主要類型、不同的圖演算法和它們使用 networkx 的 Python 實現。

下一篇文章我們將介紹圖學習，這能提供預測圖中節點和邊的方法，從而處理缺失值或預測新的關係。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！