你肯定沒有讀過這本書，因為這本書的發(fā)布日期是2019年5月。本文會覆蓋該書的大部分內(nèi)容，讀完這篇，你能夠了解圖算法的基本概念。關(guān)于此書，作為市面上為數(shù)不多的面向數(shù)據(jù)科學應(yīng)用的圖算法書籍，寫的比較全面系統(tǒng)和易懂。當然，書在細節(jié)上的提高空間還有很多。今天內(nèi)容很多，坐穩(wěn)~

目錄

圖算法 & 圖分析

圖基礎(chǔ)知識

連通圖與非連通圖
未加權(quán)圖與加權(quán)圖
有向圖與無向圖
非循環(huán)圖和循環(huán)圖

圖算法

路徑搜索算法

DFS & BFS
最短路徑
最小生成樹
隨機游走

中心性算法

DegreeCentrality
ClosenessCentrality
BetweennessCentrality
PageRank

社群發(fā)現(xiàn)算法

MeasuringAlgorithm
ComponentsAlgorithm
LabelPropagation Algorithm
LouvainModularity Algorithm

結(jié)論

圖算法 & 圖分析

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

圖算法是圖分析的工具之一。圖算法提供了一種最有效的分析連接數(shù)據(jù)的方法，它們描述了如何處理圖以發(fā)現(xiàn)一些定性或者定量的結(jié)論。圖算法基于圖論，利用節(jié)點之間的關(guān)系來推斷復雜系統(tǒng)的結(jié)構(gòu)和變化。我們可以使用這些算法來發(fā)現(xiàn)隱藏的信息，驗證業(yè)務(wù)假設(shè)，并對行為進行預測。

圖分析和圖算法具有廣泛的應(yīng)用潛力：從防止欺詐，優(yōu)化呼叫路由，到預測流感的傳播。下圖是 Martin Grandjean 創(chuàng)建的航線網(wǎng)絡(luò)圖，這幅圖清楚地展示了航空運輸集群高度連接的結(jié)構(gòu)，幫助我們了解航空運力如何流動。航線網(wǎng)絡(luò)采用典型的輻射式結(jié)構(gòu)(hub-and-spoke structure)，這樣的結(jié)構(gòu)在有限運力的前提下，增大了航線的網(wǎng)絡(luò)的始發(fā)-到達對(OD Pair)，然而卻也帶來了系統(tǒng)級聯(lián)延遲的可能。

 

 

圖基礎(chǔ)知識

我們已經(jīng)在前一篇博文中介紹了屬性圖的概念。我們已經(jīng)知道了節(jié)點、關(guān)系、屬性(Property)、標簽等概念。

 

 

子圖(Subgraph)是一張圖的一部分。當我們需要對圖中的特定節(jié)點，特定關(guān)系，或者特定標簽或者屬性進行特定分析時，子圖就會很有用。

路徑(Path)是一組節(jié)點及他們的關(guān)系的集合。以上圖為例，“Dan” 開過型號為 “Volvo V70” 的車，這輛車是屬于 “Ann” 的。那么節(jié)點 “Dan” “Ann” “Car”和關(guān)系 “Drives” “Owns” 組成了一個簡單的路徑。

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

連通圖與非連通圖

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

 

 

有些圖算法在非連通圖上可能產(chǎn)生無法預見的錯誤。如果我們發(fā)現(xiàn)了未預見的結(jié)果，可以首先檢查圖的結(jié)構(gòu)是否連通。

未加權(quán)圖與加權(quán)圖

未加權(quán)圖(Unweighted Graphs)的節(jié)點和邊上均沒有權(quán)重。對于加權(quán)圖(Weighted Graphs)，所加權(quán)重可以代表：成本、時間、距離、容量、甚至是指定域的優(yōu)先級。下圖給出了示意圖。

 

 

基本的圖算法可以通過處理權(quán)重來代表關(guān)系的強度。許多算法通過計算指標，用作后續(xù)算法的權(quán)重。也有些算法通過更新權(quán)重值，來查找累計總數(shù)、最小值或最優(yōu)化結(jié)果。

關(guān)于加權(quán)圖的一個典型用途是路徑尋找算法。這些算法支持我們手機上的地圖應(yīng)用程序，并計算位置之間最短/最便宜/最快的運輸路線。例如，下圖使用了兩種不同的方法來計算最短路線。

 

 

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

有向圖與無向圖

在無向圖(Undirected Graphs)中，節(jié)點的關(guān)系被認為是雙向的(bi-directional)，例如朋友關(guān)系。而在有向圖(Directed Graphs)中，節(jié)點的關(guān)系可以指定方向。邊如果指向了一個節(jié)點，我們稱為 in-link，邊如果從一個節(jié)點出發(fā)，我們稱為 out-link。

邊的方向加入了更多維度的信息，同樣關(guān)系的邊，卻包含不同的方向，則代表了不同的語義信息。如下圖所示，有向圖繪制了一個簡單的同學網(wǎng)絡(luò)，邊的方向代表著 “喜歡”。那么從圖中，我們可以知道，同學中 “最受歡迎的” 的人是 “A” 和 “C”。

 

 

我們還可以用道路網(wǎng)絡(luò)幫我們理解為什么需要有向圖和無向圖。例如，高速公路一般都是雙向的，我們使用無向圖即可。但是，在城市內(nèi)部，經(jīng)常會有單向車道，我們必須使用有向圖。

非循環(huán)圖和循環(huán)圖

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

 

 

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

循環(huán)在圖中非常常見。有時，我們?yōu)榱颂岣咛幚硇�率，會將循環(huán)圖轉(zhuǎn)化為非循環(huán)圖(通過剪除一些關(guān)系)。DAG 在調(diào)度、版本控制等問題中十分常見。實際上，我們在數(shù)學或者計算機科學中經(jīng)常遇見的樹(Tree)就是一個典型的 DAG，只是對于樹來說，只能擁有一個 Parent，而 DAG 沒有這個限制。

圖算法

我們關(guān)注三類核心的圖算法：路徑搜索(Pathfinding and Search)、中心性計算(Centrality Computation)和社群發(fā)現(xiàn)(Community Detection)。

路徑搜索算法

圖搜索算法(Pathfinding and Search Algorithms)探索一個圖，用于一般發(fā)現(xiàn)或顯式搜索。這些算法通過從圖中找到很多路徑，但并不期望這些路徑是計算最優(yōu)的(例如最短的，或者擁有最小的權(quán)重和)。圖搜索算法包括廣度優(yōu)先搜索和深度優(yōu)先搜索，它們是遍歷圖的基礎(chǔ)，并且通常是許多其他類型分析的第一步。

路徑搜索(Pathfinding)算法建立在圖搜索算法的基礎(chǔ)上，并探索節(jié)點之間的路徑。這些路徑從一個節(jié)點開始，遍歷關(guān)系，直到到達目的地。路徑搜索算法識別最優(yōu)路徑，用于物流規(guī)劃，最低成本呼叫或者叫IP路由問題，以及游戲模擬等。

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

 

 

DFS & BFS

圖算法中最基礎(chǔ)的兩個遍歷算法：廣度優(yōu)先搜索(Breadth First Search，簡稱 BFS)和深度優(yōu)先搜索(Depth First Search，簡稱 DFS)。BFS 從選定的節(jié)點出發(fā)，優(yōu)先訪問所有一度關(guān)系的節(jié)點之后再繼續(xù)訪問二度關(guān)系節(jié)點，以此類推。DFS 從選定的節(jié)點出發(fā)，選擇任一鄰居之后，盡可能的沿著邊遍歷下去，知道不能前進之后再回溯。

下面是兩張同樣的圖，分別采用 BFS 和 DFS 進行圖的遍歷，圖上節(jié)點的數(shù)字標識這遍歷順序。

 

BFS

 

 

 

DFS

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

最短路徑

最短路徑(Shortest Paths)算法計算給定的兩個節(jié)點之間最短(最小權(quán)重和)的路徑。算法能夠?qū)崟r地交互和給出結(jié)果，可以給出關(guān)系傳播的度數(shù)(degree)，可以快速給出兩點之間的最短距離，可以計算兩點之間成本最低的路線等等。例如：

導航：谷歌、百度、高德地圖均提供了導航功能，它們就使用了最短路徑算法(或者非常接近的變種);

社交網(wǎng)絡(luò)關(guān)系：當我們在 LinkedIn、人人(暴露年齡了)等社交平臺上查看某人的簡介時，平臺會展示你們之間有多少共同好友，并列出你們之間的關(guān)系。

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

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

所有節(jié)點對最短路徑(All Pairs Shortest Path)也是一個常用的最短路徑算法，計算所有節(jié)點對的最短路徑。相比較一個一個調(diào)用單個的最短路徑算法，All Pairs Shortest Path 算法會更快。算法并行計算多個節(jié)點的信息，并且這些信息在計算中可以被重用。

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

 

 

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

優(yōu)化城市設(shè)施的位置和貨物的分配：例如確定運輸網(wǎng)格中不同路段上預期的交通負荷，例如快遞線路設(shè)計，從而保證運輸對突發(fā)事件的應(yīng)對;

作為數(shù)據(jù)中心設(shè)計算法的一部分：查找具有最大帶寬和最小延遲的網(wǎng)絡(luò)。

最小生成樹

最小生成樹(Minimum Spanning Tree)算法從一個給定的節(jié)點開始，查找其所有可到達的節(jié)點，以及將節(jié)點與最小可能權(quán)重連接在一起，行成的一組關(guān)系。它以最小的權(quán)重從訪問過的節(jié)點遍歷到下一個未訪問的節(jié)點，避免了循環(huán)。

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

 

 

上圖是最小生成樹算法的步驟分解，算法最終用最小的權(quán)重將圖進行了遍歷，并且在遍歷的過程中，不產(chǎn)生環(huán)。

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

旅行計劃：盡可能降低探索一個國家的旅行成本;

追蹤流感傳播的歷史：有人使用最小生成樹模型對丙型肝炎病毒感染的醫(yī)院暴發(fā)進行分子流行病學調(diào)查

隨機游走

隨機游走(Random Walk)算法從圖上獲得一條隨機的路徑。隨機游走算法從一個節(jié)點開始，隨機沿著一條邊正向或者反向?qū)ふ业剿�的鄰居，以此類推，直到達到設(shè)置的路徑長度。這個過程有點像是一個醉漢在城市閑逛，他可能知道自己大致要去哪兒，但是路徑可能極其“迂回”，畢竟，他也無法控制自己~

隨機游走算法一般用于隨機生成一組相關(guān)的節(jié)點數(shù)據(jù)，作為后續(xù)數(shù)據(jù)處理或者其他算法使用。例如：

作為 node2vec 和 graph2vec 算法的一部分，這些算法可以用于節(jié)點向量的生成，從而作為后續(xù)深度學習模型的輸入;這一點對于了解 NLP (自然語言處理)的朋友來說并不難理解，詞是句子的一部分，我們可以通過詞的組合(語料)來訓練詞向量。那么，我們同樣可以通過節(jié)點的組合(Random Walk)來訓練節(jié)點向量。這些向量可以表征詞或者節(jié)點的含義，并且能夠做數(shù)值計算。這一塊的應(yīng)用很有意思，我們會找機會來詳細介紹;

作為 Walktrap 和 Infomap 算法的一部分，用于社群發(fā)現(xiàn)。如果隨機游走總是返回同一組節(jié)點，表明這些節(jié)點可能在同一個社群;

其他機器學習模型的一部分，用于隨機產(chǎn)生相關(guān)聯(lián)的節(jié)點數(shù)據(jù)。

中心性算法

中心性算法(Centrality Algorithms)用于識別圖中特定節(jié)點的角色及其對網(wǎng)絡(luò)的影響。中心性算法能夠幫助我們識別最重要的節(jié)點，幫助我們了解組動態(tài)，例如可信度、可訪問性、事物傳播的速度以及組與組之間的連接。盡管這些算法中有許多是為社會網(wǎng)絡(luò)分析而發(fā)明的，但它們已經(jīng)在許多行業(yè)和領(lǐng)域中得到了應(yīng)用。

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

 

 

Degree Centrality

Degree Centrality (度中心性，以度作為標準的中心性指標)可能是整篇博文最簡單的 “算法” 了。Degree 統(tǒng)計了一個節(jié)點直接相連的邊的數(shù)量，包括出度和入度。Degree 可以簡單理解為一個節(jié)點的訪問機會的大小。例如，在一個社交網(wǎng)絡(luò)中，一個擁有更多 degree 的人(節(jié)點)更容易與人發(fā)生直接接觸，也更容易獲得流感。

一個網(wǎng)絡(luò)的平均度(average degree)，是邊的數(shù)量除以節(jié)點的數(shù)量。當然，平均度很容易被一些具有極大度的節(jié)點 “帶跑偏” (skewed)。所以，度的分布(degree distribution)可能是表征網(wǎng)絡(luò)特征的更好指標。

如果你希望通過出度入度來評價節(jié)點的中心性，就可以使用 degree centrality。度中心性在關(guān)注直接連通時具有很好的效果。應(yīng)用場景例如，區(qū)分在線拍賣的合法用戶和欺詐者，欺詐者由于嘗嘗人為太高拍賣價格，擁有更高的加權(quán)中心性(weighted centrality)。

Closeness Centrality

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

對于一個節(jié)點來說，緊密性中心性是節(jié)點到所有其他節(jié)點的最小距離和的倒數(shù)：

 

 

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

理解公式我們就會發(fā)現(xiàn)，如果圖是一個非連通圖，那么我們將無法計算緊密性中心性。那么針對非連通圖，調(diào)和中心性(Harmonic Centrality)被提了出來(當然它也有歸一化的版本，你猜這次n-1應(yīng)該加在哪里?)：

 

 

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

 

 

其中，N 是圖中總的節(jié)點數(shù)量，n 是一個部件(component)中的節(jié)點數(shù)量。

當我們希望關(guān)注網(wǎng)絡(luò)中傳播信息最快的節(jié)點，我們就可以使用緊密性中心性。

Betweenness Centrality

中介中心性(Betweenness Centrality)是一種檢測節(jié)點對圖中信息或資源流的影響程度的方法。它通常用于尋找連接圖的兩個部分的橋梁節(jié)點。因為很多時候，一個系統(tǒng)最重要的 “齒輪” 不是那些狀態(tài)最好的，而是一些看似不起眼的 “媒介”，它們掌握著資源或者信息的流動性。

中間中心性算法首先計算連接圖中每對節(jié)點之間的最短(最小權(quán)重和)路徑。每個節(jié)點都會根據(jù)這些通過節(jié)點的最短路徑的數(shù)量得到一個分數(shù)。節(jié)點所在的路徑越短，其得分越高。計算公式：

 

 

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

 

 

當然，在一張大圖上計算中介中心性是十分昂貴的。所以我們需要更快的，成本更小的，并且精度大致相同的算法來計算，例如 Randomized-Approximate Brandes。我們不會對這個算法繼續(xù)深入，感興趣的話，可以去了解一下，算法如何通過隨機(Random)和度的篩選(Degree)達到近似的效果。

中介中心性在現(xiàn)實的網(wǎng)絡(luò)中有廣泛的應(yīng)用，我們使用它來發(fā)現(xiàn)瓶頸、控制點和漏洞。例如，識別不同組織的影響者，他們往往是各個組織的媒介，例如尋找電網(wǎng)的關(guān)鍵點，提高整體魯棒性。

PageRank

在所有的中心性算法中，PageRank 是最著名的一個。它測量節(jié)點傳遞影響的能力。PageRank 不但節(jié)點的直接影響，也考慮 “鄰居” 的影響力。例如，一個節(jié)點擁有一個有影響力的 “鄰居”，可能比擁有很多不太有影響力的 “鄰居” 更有影響力。PageRank 統(tǒng)計到節(jié)點的傳入關(guān)系的數(shù)量和質(zhì)量，從而決定該節(jié)點的重要性。

PageRank 算法以谷歌聯(lián)合創(chuàng)始人拉里·佩奇的名字命名，他創(chuàng)建了這個算法來對谷歌搜索結(jié)果中的網(wǎng)站進行排名。不同的網(wǎng)頁之間相互引用，網(wǎng)頁作為節(jié)點，引用關(guān)系作為邊，就可以組成一個網(wǎng)絡(luò)。被更多網(wǎng)頁引用的網(wǎng)頁，應(yīng)該擁有更高的權(quán)重;被更高權(quán)重引用的網(wǎng)頁，也應(yīng)該擁有更高權(quán)重。原始公式：

 

 

其中，u 是我們想要計算 PageRank 的網(wǎng)頁，T1 到 Tn 是引用的網(wǎng)頁。d 被稱為阻尼系數(shù)(damping factor)，代表一個用戶繼續(xù)點擊網(wǎng)頁的概率，一般被設(shè)置為 0.85，范圍 0~1。C(T) 是節(jié)點 T 的出度。

從理解上來說，PageRank 算法假設(shè)一個用戶在訪問網(wǎng)頁時，用戶可能隨機輸入一個網(wǎng)址，也可能通過一些網(wǎng)頁的鏈接訪問到別的網(wǎng)頁。那么阻尼系數(shù)代表用戶對當前網(wǎng)頁感到無聊，隨機選擇一個鏈接訪問到新的網(wǎng)頁的概率。那么 PageRank 的數(shù)值代表這個網(wǎng)頁通過其他網(wǎng)頁鏈接過來(入度，in-degree)的可能性。那你能如何解釋 PageRank 方程中的 1-d 呢?實際，1-d 代表不通過鏈接訪問，而是隨機輸入網(wǎng)址訪問到網(wǎng)頁的概率。

PageRank 算法采用迭代方式計算，直到結(jié)果收斂或者達到迭代上限。每次迭代都會分兩步更新節(jié)點權(quán)重和邊的權(quán)重，詳細如下圖：

 

 

當然，上圖的計算并沒有考慮阻尼系數(shù)，那為什么一定要阻尼系數(shù)呢?除了我們定義的鏈接訪問概率，有沒有別的意義呢?從上圖的過程中，我們可能會發(fā)現(xiàn)一個問題，如果一個節(jié)點(或者一組節(jié)點)，只有邊進入，卻沒有邊出去，會怎么樣呢?按照上圖的迭代，節(jié)點會不斷搶占 PageRank 分數(shù)。這個現(xiàn)象被稱為 Rank Sink，如下圖：

 

 

解決 Rank Sink 的方法有兩個。第一個，假設(shè)這些節(jié)點有隱形的邊連向了所有的節(jié)點，遍歷這些隱形的邊的過程稱為 teleportation。第二個，使用阻尼系數(shù)，如果我們設(shè)置 d 等于 0.85，我們?nèi)匀挥?0.15 的概率從這些節(jié)點再跳躍出去。

盡管阻尼系數(shù)的建議值為 0.85，我們?nèi)匀豢梢愿鶕?jù)實際需要進行修改。調(diào)低阻尼系數(shù)，意味著訪問網(wǎng)頁時，更不可能不斷點擊鏈接訪問下去，而是更多地隨機訪問別的網(wǎng)頁。那么一個網(wǎng)頁的 PageRank 分數(shù)會更多地分給他的直接下游網(wǎng)頁，而不是下游的下游網(wǎng)頁。

PageRank 算法已經(jīng)不僅限于網(wǎng)頁排名。例如：

尋找最重要的基因：我們要尋找的基因可能不是與生物功能聯(lián)系最多的基因，而是與最重要功能有緊密聯(lián)系的基因;

who to follow service at twitter：Twitter使用個性化的 PageRank 算法(Personalized PageRank，簡稱 PPR)向用戶推薦他們可能希望關(guān)注的其他帳戶。該算法通過興趣和其他的關(guān)系連接，為用戶展示感興趣的其他用戶;

交通流量預測：使用 PageRank 算法計算人們在每條街道上停車或結(jié)束行程的可能性;

反欺詐：醫(yī)療或者保險行業(yè)存在異�；蛘咂墼p行為，PageRank 可以作為后續(xù)機器學習算法的輸入。

社群發(fā)現(xiàn)算法

社群的形成在各種類型的網(wǎng)絡(luò)中都很常見。識別社群對于評估群體行為或突發(fā)事件至關(guān)重要。對于一個社群來說，內(nèi)部節(jié)點與內(nèi)部節(jié)點的關(guān)系(邊)比社群外部節(jié)點的關(guān)系更多。識別這些社群可以揭示節(jié)點的分群，找到孤立的社群，發(fā)現(xiàn)整體網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系。社群發(fā)現(xiàn)算法(Community Detection Algorithms)有助于發(fā)現(xiàn)社群中群體行為或者偏好，尋找嵌套關(guān)系，或者成為其他分析的前序步驟。社群發(fā)現(xiàn)算法也常用于網(wǎng)絡(luò)可視化。

下圖是社群發(fā)現(xiàn)算法的分類。

 

 

Measuring Algorithm

三角計數(shù)(Triangle Count)和聚類系數(shù)(Clustering Coefficient)經(jīng)常被一起使用。三角計數(shù)計算圖中由節(jié)點組成的三角形的數(shù)量，要求任意兩個節(jié)點間有邊(關(guān)系)連接。聚類系數(shù)算法的目標是測量一個組的聚類緊密程度。該算法計算網(wǎng)絡(luò)中三角形的數(shù)量，與可能的關(guān)系的比率。聚類系數(shù)為 1 表示這個組內(nèi)任意兩個節(jié)點之間有邊相連。

有兩種聚類系數(shù)：局部聚類系數(shù)(Local Clustering Coefficient)和全局聚類系數(shù)(Global Clustering Coefficient)。

局部聚類系數(shù)計算一個節(jié)點的鄰居之間的緊密程度，計算時需要三角計數(shù)。計算公式：

 

 

其中，u 代表我們需要計算聚類系數(shù)的節(jié)點，R(u) 代表經(jīng)過節(jié)點 u 和它的鄰居的三角形個數(shù)，k(u) 代表節(jié)點 u的度。下圖是三三角計數(shù)聚類系數(shù)計算示意圖：

 

 

全局聚類系數(shù)是局部聚類系數(shù)的歸一化求和。

當需要計算一個組的穩(wěn)定性或者聚類系數(shù)時，我們可以使用三角計數(shù)。三角計數(shù)在社交網(wǎng)絡(luò)分析中有廣泛的應(yīng)用，通航被用來檢測社區(qū)。聚類系數(shù)可以快速評估特定組或整個網(wǎng)絡(luò)的內(nèi)聚性。這些算法可以共同用于特定網(wǎng)絡(luò)結(jié)構(gòu)的尋找。例如，探索網(wǎng)頁的主題結(jié)構(gòu)，基于網(wǎng)頁之間的相互聯(lián)系，檢測擁有共同主題的 “網(wǎng)頁社群”。

Components Algorithm

強關(guān)聯(lián)部件(Strongly Connected Components，簡稱 SCC)算法尋找有向圖內(nèi)的一組一組節(jié)點，每組節(jié)點可以通過關(guān)系 互相 訪問。在 “Community Detection Algorithms” 的圖中，我們可以發(fā)現(xiàn)，每組節(jié)點內(nèi)部不需要直接相連，只要通過路徑訪問即可。

關(guān)聯(lián)部件(Connected Components)算法，不同于 SCC，組內(nèi)的節(jié)點對只需通過一個方向訪問即可。

關(guān)聯(lián)類算法作為圖分析的早期算法，用以了解圖的結(jié)構(gòu)，或確定可能需要獨立調(diào)查的緊密集群十分有效。對于推薦引擎等應(yīng)用程序，也可以用來描述組中的類似行為等等。許多時候，算法被用于查找集群并將其折疊成單個節(jié)點，以便進一步進行集群間分析。對于我們來說，先運行以下關(guān)聯(lián)類算法查看圖是否連通，是一個很好的習慣。

Label Propagation Algorithm

標簽傳播算法(Label Propagation Algorithm，簡稱 LPA)是一個在圖中快速發(fā)現(xiàn)社群的算法。在 LPA 算法中，節(jié)點的標簽完全由它的直接鄰居決定。算法非常適合于半監(jiān)督學習，你可以使用已有標簽的節(jié)點來種子化傳播進程。

LPA 是一個較新的算法，由 Raghavan 等人于 2007 年提出。我們可以很形象地理解算法的傳播過程，當標簽在緊密聯(lián)系的區(qū)域，傳播非常快，但到了稀疏連接的區(qū)域，傳播速度就會下降。當出現(xiàn)一個節(jié)點屬于多個社群時，算法會使用該節(jié)點鄰居的標簽與權(quán)重，決定最終的標簽。傳播結(jié)束后，擁有同樣標簽的節(jié)點被視為在同一群組中。

下圖展示了算法的兩個變種：Push 和 Pull。其中 Pull 算法更為典型，并且可以很好地并行計算：

 

 

我們不再繼續(xù)深入，看完上圖，你應(yīng)該已經(jīng)理解了算法的大概過程。其實，做過圖像處理的人很容易明白，所謂的標簽傳播算法，不過是圖像分割算法的變種，Push 算法是區(qū)域生長法(Region Growing)的簡化版，而 Pull 更像是分割和合并(divide-and-merge，也有人稱 split-merge)算法。確實，圖像(image)的像素和圖(graph)的節(jié)點是十分類似的。

Louvain Modularity Algorithm

Louvain Modularity 算法在給節(jié)點分配社群是，會比較社群的密度，而不僅僅是比較節(jié)點與社群的緊密程度。算法通過查看節(jié)點與社群內(nèi)關(guān)系的密度與平均關(guān)系密度的比較，來量化地決定一個節(jié)點是否屬于社群。算法不但可以發(fā)現(xiàn)社群，更可以給出不同尺度不同規(guī)模的社群層次，對于理解不同粒度界別的網(wǎng)絡(luò)結(jié)構(gòu)有極大的幫助。

算法在 2008 年被提出以后，迅速成為了最快的模塊化算法之一。算法的細節(jié)很多，我們無法一一覆蓋，下圖給出了一個粗略的步驟，幫助我們理解算法如何能夠多尺度地構(gòu)建社群：

 

 

Louvain Modularity 算法非常適合龐大網(wǎng)絡(luò)的社群發(fā)現(xiàn)，算法采用啟發(fā)式方式從而能夠克服傳統(tǒng) Modularity 類算法的局限。算法應(yīng)用：

檢測網(wǎng)絡(luò)攻擊:該算可以應(yīng)用于大規(guī)模網(wǎng)絡(luò)安全領(lǐng)域中的快速社群發(fā)現(xiàn)。一旦這些社群被發(fā)現(xiàn)，就可以用來預防網(wǎng)絡(luò)攻擊;

主題建模：從 Twitter 和 YouTube 等在線社交平臺中提取主題，基于文檔中共同出現(xiàn)的術(shù)語，作為主題建模過程的一部分。

結(jié)論

本文更像是一篇綜述，算法很干，我們會在后續(xù)繼續(xù)分享圖分析相關(guān)內(nèi)容，敬請期待。

網(wǎng)址：https://learning.oreilly.com/library/view/graph-algorithms-/9781492060116/
 

標簽： [db:TAGG]

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。