|
來源：數(shù)據(jù)科學(xué)一線DSFrontier
網(wǎng)址：https://learning./library/view/graph-algorithms-/9781492060116/ 你肯定沒有讀過這本書，因?yàn)檫@本書的發(fā)布日期是2019年5月。本文會(huì)覆蓋該書的大部分內(nèi)容，讀完這篇，你能夠了解圖算法的基本概念。關(guān)于此書，作為市面上為數(shù)不多的面向數(shù)據(jù)科學(xué)應(yīng)用的圖算法書籍，寫的比較全面系統(tǒng)和易懂。當(dāng)然，書在細(xì)節(jié)上的提高空間還有很多。今天內(nèi)容很多，坐穩(wěn)~ 目錄 圖算法 & 圖分析 圖基礎(chǔ)知識(shí) 連通圖與非連通圖 未加權(quán)圖與加權(quán)圖 有向圖與無向圖 非循環(huán)圖和循環(huán)圖 圖算法 路徑搜索算法 DFS & BFS 最短路徑 最小生成樹 隨機(jī)游走 中心性算法 DegreeCentrality ClosenessCentrality BetweennessCentrality PageRank 社群發(fā)現(xiàn)算法 MeasuringAlgorithm ComponentsAlgorithm LabelPropagation Algorithm LouvainModularity Algorithm 結(jié)論 圖算法 & 圖分析圖分析使用基于圖的方法來分析連接的數(shù)據(jù)。我們可以：查詢圖數(shù)據(jù)，使用基本統(tǒng)計(jì)信息，可視化地探索圖、展示圖，或者將圖信息預(yù)處理后合并到機(jī)器學(xué)習(xí)任務(wù)中。圖的查詢通常用于局部數(shù)據(jù)分析，而圖計(jì)算通常涉及整張圖和迭代分析。 圖算法是圖分析的工具之一。圖算法提供了一種最有效的分析連接數(shù)據(jù)的方法，它們描述了如何處理圖以發(fā)現(xiàn)一些定性或者定量的結(jié)論。圖算法基于圖論，利用節(jié)點(diǎn)之間的關(guān)系來推斷復(fù)雜系統(tǒng)的結(jié)構(gòu)和變化。我們可以使用這些算法來發(fā)現(xiàn)隱藏的信息，驗(yàn)證業(yè)務(wù)假設(shè)，并對行為進(jìn)行預(yù)測。 圖分析和圖算法具有廣泛的應(yīng)用潛力：從防止欺詐，優(yōu)化呼叫路由，到預(yù)測流感的傳播。下圖是 Martin Grandjean 創(chuàng)建的航線網(wǎng)絡(luò)圖，這幅圖清楚地展示了航空運(yùn)輸集群高度連接的結(jié)構(gòu)，幫助我們了解航空運(yùn)力如何流動(dòng)。航線網(wǎng)絡(luò)采用典型的輻射式結(jié)構(gòu)（hub-and-spoke structure），這樣的結(jié)構(gòu)在有限運(yùn)力的前提下，增大了航線的網(wǎng)絡(luò)的始發(fā)-到達(dá)對（OD Pair），然而卻也帶來了系統(tǒng)級(jí)聯(lián)延遲的可能。 圖基礎(chǔ)知識(shí)我們已經(jīng)在前一篇博文中介紹了屬性圖的概念。我們已經(jīng)知道了節(jié)點(diǎn)、關(guān)系、屬性（Property）、標(biāo)簽等概念。 子圖（Subgraph）是一張圖的一部分。當(dāng)我們需要對圖中的特定節(jié)點(diǎn)，特定關(guān)系，或者特定標(biāo)簽或者屬性進(jìn)行特定分析時(shí)，子圖就會(huì)很有用。 路徑（Path）是一組節(jié)點(diǎn)及他們的關(guān)系的集合。以上圖為例，“Dan” 開過型號(hào)為 “Volvo V70” 的車，這輛車是屬于 “Ann” 的。那么節(jié)點(diǎn) “Dan” “Ann” “Car”和關(guān)系 “Drives” “Owns” 組成了一個(gè)簡單的路徑。 我們在介紹圖算法前，先梳理一下圖的不同屬性（Attribute）。 連通圖與非連通圖 連通圖（Connected Graphs）指圖內(nèi)任意兩個(gè)節(jié)點(diǎn)間，總能找到一條路徑連接它們，否則，為非連通圖（Disconnected Graphs）。也就是說，如果圖中包含島（Island）,則是非連通圖。如果島內(nèi)的節(jié)點(diǎn)都是連通的，這些島就被成為一個(gè)部件（Component，有時(shí)也叫 Cluster）。 有些圖算法在非連通圖上可能產(chǎn)生無法預(yù)見的錯(cuò)誤。如果我們發(fā)現(xiàn)了未預(yù)見的結(jié)果，可以首先檢查圖的結(jié)構(gòu)是否連通。 未加權(quán)圖與加權(quán)圖 未加權(quán)圖（Unweighted Graphs）的節(jié)點(diǎn)和邊上均沒有權(quán)重。對于加權(quán)圖（Weighted Graphs），所加權(quán)重可以代表：成本、時(shí)間、距離、容量、甚至是指定域的優(yōu)先級(jí)。下圖給出了示意圖。 基本的圖算法可以通過處理權(quán)重來代表關(guān)系的強(qiáng)度。許多算法通過計(jì)算指標(biāo)，用作后續(xù)算法的權(quán)重。也有些算法通過更新權(quán)重值，來查找累計(jì)總數(shù)、最小值或最優(yōu)化結(jié)果。 關(guān)于加權(quán)圖的一個(gè)典型用途是路徑尋找算法。這些算法支持我們手機(jī)上的地圖應(yīng)用程序，并計(jì)算位置之間最短/最便宜/最快的運(yùn)輸路線。例如，下圖使用了兩種不同的方法來計(jì)算最短路線。 如果沒有權(quán)重，計(jì)算最短路徑時(shí)，實(shí)則在計(jì)算關(guān)系（Relation，也稱 Hop）的數(shù)量。那么在上圖左邊，我們找到 A 和 E 之間的最短距離為 2，經(jīng)過 D 點(diǎn)。如果像上圖右邊所示，邊被賦予了權(quán)重，用以代表節(jié)點(diǎn)之間的物理距離（單位：KM）。那么我們可以找到 A 和 E 之間的最短距離是 50 KM，需要經(jīng)過 C 和 D 兩個(gè)點(diǎn)。而此時(shí)，在未加權(quán)圖中計(jì)算的最短路徑 A-D-E 距離為 70 KM，比我們找到的路徑 A-C-D-E 距離遠(yuǎn)。 有向圖與無向圖 在無向圖（Undirected Graphs）中，節(jié)點(diǎn)的關(guān)系被認(rèn)為是雙向的（bi-directional），例如朋友關(guān)系。而在有向圖（Directed Graphs）中，節(jié)點(diǎn)的關(guān)系可以指定方向。邊如果指向了一個(gè)節(jié)點(diǎn)，我們稱為 in-link，邊如果從一個(gè)節(jié)點(diǎn)出發(fā)，我們稱為 out-link。 邊的方向加入了更多維度的信息，同樣關(guān)系的邊，卻包含不同的方向，則代表了不同的語義信息。如下圖所示，有向圖繪制了一個(gè)簡單的同學(xué)網(wǎng)絡(luò)，邊的方向代表著 “喜歡”。那么從圖中，我們可以知道，同學(xué)中 “最受歡迎的” 的人是 “A” 和 “C”。 我們還可以用道路網(wǎng)絡(luò)幫我們理解為什么需要有向圖和無向圖。例如，高速公路一般都是雙向的，我們使用無向圖即可。但是，在城市內(nèi)部，經(jīng)常會(huì)有單向車道，我們必須使用有向圖。 非循環(huán)圖和循環(huán)圖 圖論中，循環(huán)指一些特殊的路徑，它們的起點(diǎn)和終點(diǎn)是同一個(gè)節(jié)點(diǎn)。在非循環(huán)圖（Acyclic Graph）中，不存在循環(huán)路徑，相反則為循環(huán)圖（Cyclic Graphs）。如下圖所示，有向圖和無向圖都可能包含循環(huán)，所不同的是，有向圖的路徑必須遵循邊的方向。圖中的 Graph 1 是一個(gè)典型的 DAG（Directed Acyclic Graph，有向無循環(huán)圖），并且 DAG 通常有葉子節(jié)點(diǎn)（leaf node，也稱 dead node）。 Graph 1 和 Graph 2 是無循環(huán)的，因?yàn)槲覀冊诓恢貜?fù)任何一條邊的情況下，無法從任何一個(gè)點(diǎn)出發(fā)，再回到它。Graph 3 中有一個(gè)簡單的循環(huán) A-D-C-A。而 Graph 4 中，我們可以發(fā)現(xiàn)多個(gè)循環(huán)：B-F-C-D-A-C-B，C-B-F-C 等等。 循環(huán)在圖中非常常見。有時(shí)，我們?yōu)榱颂岣咛幚硇?，?huì)將循環(huán)圖轉(zhuǎn)化為非循環(huán)圖（通過剪除一些關(guān)系）。DAG 在調(diào)度、版本控制等問題中十分常見。實(shí)際上，我們在數(shù)學(xué)或者計(jì)算機(jī)科學(xué)中經(jīng)常遇見的樹（Tree）就是一個(gè)典型的 DAG，只是對于樹來說，只能擁有一個(gè) Parent，而 DAG 沒有這個(gè)限制。 圖算法我們關(guān)注三類核心的圖算法：路徑搜索（Pathfinding and Search）、中心性計(jì)算（Centrality Computation）和社群發(fā)現(xiàn)（Community Detection）。 路徑搜索算法 圖搜索算法（Pathfinding and Search Algorithms）探索一個(gè)圖，用于一般發(fā)現(xiàn)或顯式搜索。這些算法通過從圖中找到很多路徑，但并不期望這些路徑是計(jì)算最優(yōu)的（例如最短的，或者擁有最小的權(quán)重和）。圖搜索算法包括廣度優(yōu)先搜索和深度優(yōu)先搜索，它們是遍歷圖的基礎(chǔ)，并且通常是許多其他類型分析的第一步。 路徑搜索（Pathfinding）算法建立在圖搜索算法的基礎(chǔ)上，并探索節(jié)點(diǎn)之間的路徑。這些路徑從一個(gè)節(jié)點(diǎn)開始，遍歷關(guān)系，直到到達(dá)目的地。路徑搜索算法識(shí)別最優(yōu)路徑，用于物流規(guī)劃，最低成本呼叫或者叫IP路由問題，以及游戲模擬等。 下圖是路徑搜索類算法的分類： DFS & BFS 圖算法中最基礎(chǔ)的兩個(gè)遍歷算法：廣度優(yōu)先搜索（Breadth First Search，簡稱 BFS）和深度優(yōu)先搜索（Depth First Search，簡稱 DFS）。BFS 從選定的節(jié)點(diǎn)出發(fā)，優(yōu)先訪問所有一度關(guān)系的節(jié)點(diǎn)之后再繼續(xù)訪問二度關(guān)系節(jié)點(diǎn)，以此類推。DFS 從選定的節(jié)點(diǎn)出發(fā)，選擇任一鄰居之后，盡可能的沿著邊遍歷下去，知道不能前進(jìn)之后再回溯。 下面是兩張同樣的圖，分別采用 BFS 和 DFS 進(jìn)行圖的遍歷，圖上節(jié)點(diǎn)的數(shù)字標(biāo)識(shí)這遍歷順序。 BFS DFS 對于我們數(shù)據(jù)科學(xué)的角色來說，我們很少真正需要使用 BFS 和 DFS。這兩個(gè)圖搜索算法更多地作為底層算法支持其他圖算法。例如，最短路徑問題和 Closeness Centrality （在后文會(huì)有介紹）都使用了 BFS 算法；而 DFS 可以用于模擬場景中的可能路徑，因?yàn)榘凑?DFS 訪問節(jié)點(diǎn)的順序，我們總能在兩個(gè)節(jié)點(diǎn)之間找到相應(yīng)的路徑。感興趣的話，可以猜一猜，后文介紹的算法是否使用了圖搜索算法，并且分別使用了 DFS 還是 BFS。 最短路徑 最短路徑（Shortest Paths）算法計(jì)算給定的兩個(gè)節(jié)點(diǎn)之間最短（最小權(quán)重和）的路徑。算法能夠?qū)崟r(shí)地交互和給出結(jié)果，可以給出關(guān)系傳播的度數(shù)（degree），可以快速給出兩點(diǎn)之間的最短距離，可以計(jì)算兩點(diǎn)之間成本最低的路線等等。例如：
最常見的最短路徑算法來自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先選擇與起點(diǎn)相連的最小權(quán)重的節(jié)點(diǎn)，也就是 “最臨近的” 節(jié)點(diǎn)，然后比較 起點(diǎn)到第二臨近的節(jié)點(diǎn)的權(quán)重 與 最臨近節(jié)點(diǎn)的下一個(gè)最臨近節(jié)點(diǎn)的累計(jì)權(quán)重和 從而決定下一步該如何行走?？梢韵胂?，算法記錄的累計(jì)權(quán)重和 如同地理的 “等高線” 一樣，在圖上以 “波” 的形式傳播，直到到達(dá)目的地節(jié)點(diǎn)。 最短路徑算法有兩個(gè)常用的變種：A （可以念作 A Star）algorithm和 Yen’s K-Shortest Paths。A algorithm 通過提供的額外信息，優(yōu)化算法下一步探索的方向。Yen’s K-Shortest Paths 不但給出最短路徑結(jié)果，同時(shí)給出了最好的 K 條路徑。 所有節(jié)點(diǎn)對最短路徑（All Pairs Shortest Path）也是一個(gè)常用的最短路徑算法，計(jì)算所有節(jié)點(diǎn)對的最短路徑。相比較一個(gè)一個(gè)調(diào)用單個(gè)的最短路徑算法，All Pairs Shortest Path 算法會(huì)更快。算法并行計(jì)算多個(gè)節(jié)點(diǎn)的信息，并且這些信息在計(jì)算中可以被重用。 本文不打算再深入了，下圖是從A節(jié)點(diǎn)開始的計(jì)算過程，看懂這張圖，你就明白了。
All Pairs Shortest Path 算法通常用于，當(dāng)最短路徑受限或者變成了非最優(yōu)時(shí)，如何尋找替代線路。其實(shí)算法非常常用：
最小生成樹 最小生成樹（Minimum Spanning Tree）算法從一個(gè)給定的節(jié)點(diǎn)開始，查找其所有可到達(dá)的節(jié)點(diǎn)，以及將節(jié)點(diǎn)與最小可能權(quán)重連接在一起，行成的一組關(guān)系。它以最小的權(quán)重從訪問過的節(jié)點(diǎn)遍歷到下一個(gè)未訪問的節(jié)點(diǎn)，避免了循環(huán)。 最常用的最小生成樹算法來自于 1957 年的 Prim 算法。Prim 算法與Dijkstra 的最短路徑類似，所不同的是， Prim 算法每次尋找最小權(quán)重訪問到下一個(gè)節(jié)點(diǎn)，而不是累計(jì)權(quán)重和。并且，Prim 算法允許邊的權(quán)重為負(fù)。
上圖是最小生成樹算法的步驟分解，算法最終用最小的權(quán)重將圖進(jìn)行了遍歷，并且在遍歷的過程中，不產(chǎn)生環(huán)。 算法可以用于優(yōu)化連接系統(tǒng)（如水管和電路設(shè)計(jì)）的路徑。它還用于近似一些計(jì)算時(shí)間未知的問題，如旅行商問題。雖然該算法不一定總能找到絕對最優(yōu)解，但它使得復(fù)雜度極高和計(jì)算密集度極大的分析變得更加可能。例如：
隨機(jī)游走 隨機(jī)游走（Random Walk）算法從圖上獲得一條隨機(jī)的路徑。隨機(jī)游走算法從一個(gè)節(jié)點(diǎn)開始，隨機(jī)沿著一條邊正向或者反向?qū)ふ业剿泥従?，以此類推，直到達(dá)到設(shè)置的路徑長度。這個(gè)過程有點(diǎn)像是一個(gè)醉漢在城市閑逛，他可能知道自己大致要去哪兒，但是路徑可能極其“迂回”，畢竟，他也無法控制自己~ 隨機(jī)游走算法一般用于隨機(jī)生成一組相關(guān)的節(jié)點(diǎn)數(shù)據(jù)，作為后續(xù)數(shù)據(jù)處理或者其他算法使用。例如：
中心性算法 中心性算法（Centrality Algorithms）用于識(shí)別圖中特定節(jié)點(diǎn)的角色及其對網(wǎng)絡(luò)的影響。中心性算法能夠幫助我們識(shí)別最重要的節(jié)點(diǎn)，幫助我們了解組動(dòng)態(tài)，例如可信度、可訪問性、事物傳播的速度以及組與組之間的連接。盡管這些算法中有許多是為社會(huì)網(wǎng)絡(luò)分析而發(fā)明的，但它們已經(jīng)在許多行業(yè)和領(lǐng)域中得到了應(yīng)用。 下圖羅列了我們所有需要了解的中心性算法指標(biāo)。
Degree Centrality Degree Centrality （度中心性，以度作為標(biāo)準(zhǔn)的中心性指標(biāo)）可能是整篇博文最簡單的 “算法” 了。Degree 統(tǒng)計(jì)了一個(gè)節(jié)點(diǎn)直接相連的邊的數(shù)量，包括出度和入度。Degree 可以簡單理解為一個(gè)節(jié)點(diǎn)的訪問機(jī)會(huì)的大小。例如，在一個(gè)社交網(wǎng)絡(luò)中，一個(gè)擁有更多 degree 的人（節(jié)點(diǎn)）更容易與人發(fā)生直接接觸，也更容易獲得流感。 一個(gè)網(wǎng)絡(luò)的平均度（average degree），是邊的數(shù)量除以節(jié)點(diǎn)的數(shù)量。當(dāng)然，平均度很容易被一些具有極大度的節(jié)點(diǎn) “帶跑偏” （skewed）。所以，度的分布（degree distribution）可能是表征網(wǎng)絡(luò)特征的更好指標(biāo)。 如果你希望通過出度入度來評(píng)價(jià)節(jié)點(diǎn)的中心性，就可以使用 degree centrality。度中心性在關(guān)注直接連通時(shí)具有很好的效果。應(yīng)用場景例如，區(qū)分在線拍賣的合法用戶和欺詐者，欺詐者由于嘗嘗人為太高拍賣價(jià)格，擁有更高的加權(quán)中心性（weighted centrality）。 Closeness Centrality Closeness Centrality（緊密性中心性）是一種檢測能夠通過子圖有效傳播信息的節(jié)點(diǎn)的方法。緊密性中心性計(jì)量一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的緊密性（距離的倒數(shù)），一個(gè)擁有高緊密性中心性的節(jié)點(diǎn)擁有著到所有其他節(jié)點(diǎn)的距離最小值。 對于一個(gè)節(jié)點(diǎn)來說，緊密性中心性是節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小距離和的倒數(shù)：
其中 u 是我們要計(jì)算緊密性中心性的節(jié)點(diǎn)，n 是網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)，d(u,v) 代表節(jié)點(diǎn) u 與節(jié)點(diǎn) v 的最短路徑距離。更常用的公式是歸一化之后的中心性，即計(jì)算節(jié)點(diǎn)到其他節(jié)點(diǎn)的平均距離的倒數(shù)，你知道如何修改上面的公式嗎？對了，將分子的 1 變成 n-1 即可。 理解公式我們就會(huì)發(fā)現(xiàn)，如果圖是一個(gè)非連通圖，那么我們將無法計(jì)算緊密性中心性。那么針對非連通圖，調(diào)和中心性（Harmonic Centrality）被提了出來（當(dāng)然它也有歸一化的版本，你猜這次n-1應(yīng)該加在哪里？）：
Wasserman and Faust 提出過另一種計(jì)算緊密性中心性的公式，專門用于包含多個(gè)子圖并且子圖間不相連接的非連通圖：
其中，N 是圖中總的節(jié)點(diǎn)數(shù)量，n 是一個(gè)部件（component）中的節(jié)點(diǎn)數(shù)量。 當(dāng)我們希望關(guān)注網(wǎng)絡(luò)中傳播信息最快的節(jié)點(diǎn)，我們就可以使用緊密性中心性。 Betweenness Centrality 中介中心性（Betweenness Centrality）是一種檢測節(jié)點(diǎn)對圖中信息或資源流的影響程度的方法。它通常用于尋找連接圖的兩個(gè)部分的橋梁節(jié)點(diǎn)。因?yàn)楹芏鄷r(shí)候，一個(gè)系統(tǒng)最重要的 “齒輪” 不是那些狀態(tài)最好的，而是一些看似不起眼的 “媒介”，它們掌握著資源或者信息的流動(dòng)性。 中間中心性算法首先計(jì)算連接圖中每對節(jié)點(diǎn)之間的最短（最小權(quán)重和）路徑。每個(gè)節(jié)點(diǎn)都會(huì)根據(jù)這些通過節(jié)點(diǎn)的最短路徑的數(shù)量得到一個(gè)分?jǐn)?shù)。節(jié)點(diǎn)所在的路徑越短，其得分越高。計(jì)算公式：
其中，p 是節(jié)點(diǎn) s 與 t 之間最短路徑的數(shù)量，p(u) 是其中經(jīng)過節(jié)點(diǎn) u 的數(shù)量。下圖給出了對于節(jié)點(diǎn) D 的計(jì)算過程：
|
|
|
