來源：數據科學一線DSFrontier

本篇博文的主要內容來源於 O』Reilly 系列的《GraphAlgorithms》，對圖演算法進行了綜述介紹，作者為 Amy E. Hodler & Mark Needham。

網址：https://learning.oreilly.com/library/view/graph-algorithms-/9781492060116/

你肯定沒有讀過這本書，因為這本書的發布日期是2019年5月。本文會覆蓋該書的大部分內容，讀完這篇，你能夠了解圖演算法的基本概念。關於此書，作為市面上為數不多的面向數據科學應用的圖演算法書籍，寫的比較全面系統和易懂。當然，書在細節上的提高空間還有很多。今天內容很多，坐穩~

目錄

圖演算法 & 圖分析

圖基礎知識

連通圖與非連通圖

未加權圖與加權圖

有向圖與無向圖

非循環圖和循環圖

圖演算法

路徑搜索演算法

DFS & BFS

最短路徑

最小生成樹

隨機遊走

中心性演算法

DegreeCentrality

ClosenessCentrality

BetweennessCentrality

PageRank

社群發現演算法

MeasuringAlgorithm

ComponentsAlgorithm

LabelPropagation Algorithm

LouvainModularity Algorithm

結論

圖演算法 & 圖分析

圖分析使用基於圖的方法來分析連接的數據。我們可以：查詢圖數據，使用基本統計信息，可視化地探索圖、展示圖，或者將圖信息預處理後合併到機器學習任務中。圖的查詢通常用於局部數據分析，而圖計算通常涉及整張圖和迭代分析。

圖演算法是圖分析的工具之一。圖演算法提供了一種最有效的分析連接數據的方法，它們描述了如何處理圖以發現一些定性或者定量的結論。圖演算法基於圖論，利用節點之間的關係來推斷複雜系統的結構和變化。我們可以使用這些演算法來發現隱藏的信息，驗證業務假設，並對行為進行預測。

圖分析和圖演算法具有廣泛的應用潛力：從防止欺詐，優化呼叫路由，到預測流感的傳播。下圖是 Martin Grandjean 創建的航線網路圖，這幅圖清楚地展示了航空運輸集群高度連接的結構，幫助我們了解航空運力如何流動。航線網路採用典型的輻射式結構（hub-and-spoke structure），這樣的結構在有限運力的前提下，增大了航線的網路的始發-到達對（OD Pair），然而卻也帶來了系統級聯延遲的可能。

圖基礎知識

我們已經在前一篇博文中介紹了屬性圖的概念。我們已經知道了節點、關係、屬性（Property）、標籤等概念。

子圖（Subgraph）是一張圖的一部分。當我們需要對圖中的特定節點，特定關係，或者特定標籤或者屬性進行特定分析時，子圖就會很有用。

路徑（Path）是一組節點及他們的關係的集合。以上圖為例，「Dan」 開過型號為 「Volvo V70」 的車，這輛車是屬於 「Ann」 的。那麼節點 「Dan」 「Ann」 「Car」和關係 「Drives」 「Owns」 組成了一個簡單的路徑。

我們在介紹圖演算法前，先梳理一下圖的不同屬性（Attribute）。

連通圖與非連通圖

連通圖（Connected Graphs）指圖內任意兩個節點間，總能找到一條路徑連接它們，否則，為非連通圖（Disconnected Graphs）。也就是說，如果圖中包含島（Island）,則是非連通圖。如果島內的節點都是連通的，這些島就被成為一個部件（Component，有時也叫 Cluster）。

有些圖演算法在非連通圖上可能產生無法預見的錯誤。如果我們發現了未預見的結果，可以首先檢查圖的結構是否連通。

未加權圖與加權圖

未加權圖（Unweighted Graphs）的節點和邊上均沒有權重。對於加權圖（Weighted Graphs），所加權重可以代表：成本、時間、距離、容量、甚至是指定域的優先順序。下圖給出了示意圖。

基本的圖演算法可以通過處理權重來代表關係的強度。許多演算法通過計算指標，用作後續演算法的權重。也有些演算法通過更新權重值，來查找累計總數、最小值或最優化結果。

關於加權圖的一個典型用途是路徑尋找演算法。這些演算法支持我們手機上的地圖應用程序，並計算位置之間最短/最便宜/最快的運輸路線。例如，下圖使用了兩種不同的方法來計算最短路線。

如果沒有權重，計算最短路徑時，實則在計算關係（Relation，也稱 Hop）的數量。那麼在上圖左邊，我們找到 A 和 E 之間的最短距離為 2，經過 D 點。如果像上圖右邊所示，邊被賦予了權重，用以代表節點之間的物理距離（單位：KM）。那麼我們可以找到 A 和 E 之間的最短距離是 50 KM，需要經過 C 和 D 兩個點。而此時，在未加權圖中計算的最短路徑 A-D-E 距離為 70 KM，比我們找到的路徑 A-C-D-E 距離遠。

有向圖與無向圖

在無向圖（Undirected Graphs）中，節點的關係被認為是雙向的（bi-directional），例如朋友關係。而在有向圖（Directed Graphs）中，節點的關係可以指定方向。邊如果指向了一個節點，我們稱為 in-link，邊如果從一個節點出發，我們稱為 out-link。

邊的方向加入了更多維度的信息，同樣關係的邊，卻包含不同的方向，則代表了不同的語義信息。如下圖所示，有向圖繪製了一個簡單的同學網路，邊的方向代表著 「喜歡」。那麼從圖中，我們可以知道，同學中 「最受歡迎的」 的人是 「A」 和 「C」。

我們還可以用道路網路幫我們理解為什麼需要有向圖和無向圖。例如，高速公路一般都是雙向的，我們使用無向圖即可。但是，在城市內部，經常會有單向車道，我們必須使用有向圖。

非循環圖和循環圖

圖論中，循環指一些特殊的路徑，它們的起點和終點是同一個節點。在非循環圖（Acyclic Graph）中，不存在循環路徑，相反則為循環圖（Cyclic Graphs）。如下圖所示，有向圖和無向圖都可能包含循環，所不同的是，有向圖的路徑必須遵循邊的方向。圖中的 Graph 1 是一個典型的 DAG（Directed Acyclic Graph，有向無循環圖），並且 DAG 通常有葉子節點（leaf node，也稱 dead node）。

Graph 1 和 Graph 2 是無循環的，因為我們在不重複任何一條邊的情況下，無法從任何一個點出發，再回到它。Graph 3 中有一個簡單的循環 A-D-C-A。而 Graph 4 中，我們可以發現多個循環：B-F-C-D-A-C-B，C-B-F-C 等等。

循環在圖中非常常見。有時，我們為了提高處理效率，會將循環圖轉化為非循環圖（通過剪除一些關係）。DAG 在調度、版本控制等問題中十分常見。實際上，我們在數學或者計算機科學中經常遇見的樹（Tree）就是一個典型的 DAG，只是對於樹來說，只能擁有一個 Parent，而 DAG 沒有這個限制。

圖演算法

我們關注三類核心的圖演算法：路徑搜索（Pathfinding and Search）、中心性計算（Centrality Computation）和社群發現（Community Detection）。

路徑搜索演算法

圖搜索演算法（Pathfinding and Search Algorithms）探索一個圖，用於一般發現或顯式搜索。這些演算法通過從圖中找到很多路徑，但並不期望這些路徑是計算最優的（例如最短的，或者擁有最小的權重和）。圖搜索演算法包括廣度優先搜索和深度優先搜索，它們是遍歷圖的基礎，並且通常是許多其他類型分析的第一步。

路徑搜索（Pathfinding）演算法建立在圖搜索演算法的基礎上，並探索節點之間的路徑。這些路徑從一個節點開始，遍歷關係，直到到達目的地。路徑搜索演算法識別最優路徑，用於物流規劃，最低成本呼叫或者叫IP路由問題，以及遊戲模擬等。

下圖是路徑搜索類演算法的分類：

DFS & BFS

圖演算法中最基礎的兩個遍歷演算法：廣度優先搜索（Breadth First Search，簡稱 BFS）和深度優先搜索（Depth First Search，簡稱 DFS）。BFS 從選定的節點出發，優先訪問所有一度關係的節點之後再繼續訪問二度關係節點，以此類推。DFS 從選定的節點出發，選擇任一鄰居之後，儘可能的沿著邊遍歷下去，知道不能前進之後再回溯。

下面是兩張同樣的圖，分別採用 BFS 和 DFS 進行圖的遍歷，圖上節點的數字標識這遍歷順序。

BFS

DFS

對於我們數據科學的角色來說，我們很少真正需要使用 BFS 和 DFS。這兩個圖搜索演算法更多地作為底層演算法支持其他圖演算法。例如，最短路徑問題和 Closeness Centrality （在後文會有介紹）都使用了 BFS 演算法；而 DFS 可以用於模擬場景中的可能路徑，因為按照 DFS 訪問節點的順序，我們總能在兩個節點之間找到相應的路徑。感興趣的話，可以猜一猜，後文介紹的演算法是否使用了圖搜索演算法，並且分別使用了 DFS 還是 BFS。

最短路徑

最短路徑（Shortest Paths）演算法計算給定的兩個節點之間最短（最小權重和）的路徑。演算法能夠實時地交互和給出結果，可以給出關係傳播的度數（degree），可以快速給出兩點之間的最短距離，可以計算兩點之間成本最低的路線等等。例如：

• 導航：谷歌、百度、高德地圖均提供了導航功能，它們就使用了最短路徑演算法（或者非常接近的變種）；
• 社交網路關係：當我們在 LinkedIn、人人（暴露年齡了）等社交平台上查看某人的簡介時，平台會展示你們之間有多少共同好友，並列出你們之間的關係。

最常見的最短路徑演算法來自於 1956 年的 Edsger Dijkstra。Dijkstra 的演算法首先選擇與起點相連的最小權重的節點，也就是 「最臨近的」 節點，然後比較 起點到第二臨近的節點的權重 與 最臨近節點的下一個最臨近節點的累計權重和 從而決定下一步該如何行走。可以想像，演算法記錄的累計權重和 如同地理的 「等高線」 一樣，在圖上以 「波」 的形式傳播，直到到達目的地節點。

最短路徑演算法有兩個常用的變種：A （可以念作 A Star）algorithm和 Yen』s K-Shortest Paths。A algorithm 通過提供的額外信息，優化演算法下一步探索的方向。Yen』s K-Shortest Paths 不但給出最短路徑結果，同時給出了最好的 K 條路徑。

所有節點對最短路徑（All Pairs Shortest Path）也是一個常用的最短路徑演算法，計算所有節點對的最短路徑。相比較一個一個調用單個的最短路徑演算法，All Pairs Shortest Path 演算法會更快。演算法並行計算多個節點的信息，並且這些信息在計算中可以被重用。

本文不打算再深入了，下圖是從A節點開始的計算過程，看懂這張圖，你就明白了。

All Pairs Shortest Path 演算法通常用於，當最短路徑受限或者變成了非最優時，如何尋找替代線路。其實演算法非常常用：

• 優化城市設施的位置和貨物的分配：例如確定運輸網格中不同路段上預期的交通負荷，例如快遞線路設計，從而保證運輸對突發事件的應對；
• 作為數據中心設計演算法的一部分：查找具有最大帶寬和最小延遲的網路。

最小生成樹

最小生成樹（Minimum Spanning Tree）演算法從一個給定的節點開始，查找其所有可到達的節點，以及將節點與最小可能權重連接在一起，行成的一組關係。它以最小的權重從訪問過的節點遍歷到下一個未訪問的節點，避免了循環。

最常用的最小生成樹演算法來自於 1957 年的 Prim 演算法。Prim 演算法與Dijkstra 的最短路徑類似，所不同的是， Prim 演算法每次尋找最小權重訪問到下一個節點，而不是累計權重和。並且，Prim 演算法允許邊的權重為負。

上圖是最小生成樹演算法的步驟分解，演算法最終用最小的權重將圖進行了遍歷，並且在遍歷的過程中，不產生環。

演算法可以用於優化連接系統（如水管和電路設計）的路徑。它還用於近似一些計算時間未知的問題，如旅行商問題。雖然該演算法不一定總能找到絕對最優解，但它使得複雜度極高和計算密集度極大的分析變得更加可能。例如：

• 旅行計劃：儘可能降低探索一個國家的旅行成本；
• 追蹤流感傳播的歷史：有人使用最小生成樹模型對丙型肝炎病毒感染的醫院暴發進行分子流行病學調查

隨機遊走

隨機遊走（Random Walk）演算法從圖上獲得一條隨機的路徑。隨機遊走演算法從一個節點開始，隨機沿著一條邊正向或者反向尋找到它的鄰居，以此類推，直到達到設置的路徑長度。這個過程有點像是一個醉漢在城市閑逛，他可能知道自己大致要去哪兒，但是路徑可能極其「迂迴」，畢竟，他也無法控制自己~

隨機遊走演算法一般用於隨機生成一組相關的節點數據，作為後續數據處理或者其他演算法使用。例如：

• 作為 node2vec 和 graph2vec 演算法的一部分，這些演算法可以用於節點向量的生成，從而作為後續深度學習模型的輸入；這一點對於了解 NLP （自然語言處理）的朋友來說並不難理解，詞是句子的一部分，我們可以通過詞的組合（語料）來訓練詞向量。那麼，我們同樣可以通過節點的組合（Random Walk）來訓練節點向量。這些向量可以表徵詞或者節點的含義，並且能夠做數值計算。這一塊的應用很有意思，我們會找機會來詳細介紹；
• 作為 Walktrap 和 Infomap 演算法的一部分，用於社群發現。如果隨機遊走總是返回同一組節點，表明這些節點可能在同一個社群；
• 其他機器學習模型的一部分，用於隨機產生相關聯的節點數據。

中心性演算法

中心性演算法（Centrality Algorithms）用於識別圖中特定節點的角色及其對網路的影響。中心性演算法能夠幫助我們識別最重要的節點，幫助我們了解組動態，例如可信度、可訪問性、事物傳播的速度以及組與組之間的連接。儘管這些演算法中有許多是為社會網路分析而發明的，但它們已經在許多行業和領域中得到了應用。

下圖羅列了我們所有需要了解的中心性演算法指標。

Degree Centrality

Degree Centrality （度中心性，以度作為標準的中心性指標）可能是整篇博文最簡單的 「演算法」 了。Degree 統計了一個節點直接相連的邊的數量，包括出度和入度。Degree 可以簡單理解為一個節點的訪問機會的大小。例如，在一個社交網路中，一個擁有更多 degree 的人（節點）更容易與人發生直接接觸，也更容易獲得流感。

一個網路的平均度（average degree），是邊的數量除以節點的數量。當然，平均度很容易被一些具有極大度的節點 「帶跑偏」 （skewed）。所以，度的分布（degree distribution）可能是表徵網路特徵的更好指標。

如果你希望通過出度入度來評價節點的中心性，就可以使用 degree centrality。度中心性在關注直接連通時具有很好的效果。應用場景例如，區分在線拍賣的合法用戶和欺詐者，欺詐者由於嘗嘗人為太高拍賣價格，擁有更高的加權中心性（weighted centrality）。

Closeness Centrality

Closeness Centrality（緊密性中心性）是一種檢測能夠通過子圖有效傳播信息的節點的方法。緊密性中心性計量一個節點到所有其他節點的緊密性（距離的倒數），一個擁有高緊密性中心性的節點擁有著到所有其他節點的距離最小值。

對於一個節點來說，緊密性中心性是節點到所有其他節點的最小距離和的倒數：

其中 u 是我們要計算緊密性中心性的節點，n 是網路中總的節點數，d(u,v) 代表節點 u 與節點 v 的最短路徑距離。更常用的公式是歸一化之後的中心性，即計算節點到其他節點的平均距離的倒數，你知道如何修改上面的公式嗎？對了，將分子的 1 變成 n-1 即可。

理解公式我們就會發現，如果圖是一個非連通圖，那麼我們將無法計算緊密性中心性。那麼針對非連通圖，調和中心性（Harmonic Centrality）被提了出來（當然它也有歸一化的版本，你猜這次n-1應該加在哪裡？）：

Wasserman and Faust 提出過另一種計算緊密性中心性的公式，專門用於包含多個子圖並且子圖間不相連接的非連通圖：

其中，N 是圖中總的節點數量，n 是一個部件（component）中的節點數量。

當我們希望關注網路中傳播信息最快的節點，我們就可以使用緊密性中心性。

Betweenness Centrality

中介中心性（Betweenness Centrality）是一種檢測節點對圖中信息或資源流的影響程度的方法。它通常用於尋找連接圖的兩個部分的橋樑節點。因為很多時候，一個系統最重要的 「齒輪」 不是那些狀態最好的，而是一些看似不起眼的 「媒介」，它們掌握著資源或者信息的流動性。

中間中心性演算法首先計算連接圖中每對節點之間的最短（最小權重和）路徑。每個節點都會根據這些通過節點的最短路徑的數量得到一個分數。節點所在的路徑越短，其得分越高。計算公式：

其中，p 是節點 s 與 t 之間最短路徑的數量，p(u) 是其中經過節點 u 的數量。下圖給出了對於節點 D 的計算過程：

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