關(guān)于圖計(jì)算&圖學(xué)習(xí)的基礎(chǔ)知識(shí)概覽：前置知識(shí)點(diǎn)學(xué)習(xí)PGL

2022-11-25 11:36 作者:汀丶人工智能 0人讀過 | 我要投稿

歡迎fork本項(xiàng)目原始鏈接：關(guān)于圖計(jì)算&圖學(xué)習(xí)的基礎(chǔ)知識(shí)概覽：前置知識(shí)點(diǎn)學(xué)習(xí)（Paddle Graph L）https://aistudio.baidu.com/aistudio/projectdetail/4982973?contributionType=1

因?yàn)槠P(guān)系就只放了部分程序在第三章，如有需求可自行fork項(xiàng)目原始鏈接。

0.1圖計(jì)算基本概念

首先看到百度百科定義：

圖計(jì)算（Graph Processing）是將數(shù)據(jù)按照?qǐng)D的方式建?？梢垣@得以往用扁平化的視角很難得到的結(jié)果。

圖（Graph）是用于表示對(duì)象之間關(guān)聯(lián)關(guān)系的一種抽象數(shù)據(jù)結(jié)構(gòu)，使用頂點(diǎn)（Vertex）和邊（Edge）進(jìn)行描述：頂點(diǎn)表示對(duì)象，邊表示對(duì)象之間的關(guān)系?？沙橄蟪捎脠D描述的數(shù)據(jù)即為圖數(shù)據(jù)。圖計(jì)算，便是以圖作為數(shù)據(jù)模型來表達(dá)問題并予以解決的這一過程。以高效解決圖計(jì)算問題為目標(biāo)的系統(tǒng)軟件稱為圖計(jì)算系統(tǒng)。

大數(shù)據(jù)時(shí)代，數(shù)據(jù)之間存在關(guān)聯(lián)關(guān)系。由于圖是表達(dá)事物之間復(fù)雜關(guān)聯(lián)關(guān)系的組織結(jié)構(gòu)，因此現(xiàn)實(shí)生活中的諸多應(yīng)用場(chǎng)景都需要用到圖，例如，淘寶用戶好友關(guān)系圖、道路圖、電路圖、病毒傳播網(wǎng)、國(guó)家電網(wǎng)、文獻(xiàn)網(wǎng)、社交網(wǎng)和知識(shí)圖譜。

為了從這些數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系中獲取有用信息，大量圖算法層出不窮。它們通過對(duì)大型圖數(shù)據(jù)的迭代處理，獲得圖數(shù)據(jù)中隱藏的重要信息。圖計(jì)算作為下一代人工智能的核心技術(shù)，已被廣泛應(yīng)用于醫(yī)療、教育、軍事、金融等多個(gè)領(lǐng)域，并備受各國(guó)政府、全球研發(fā)機(jī)構(gòu)和巨頭公司關(guān)注，目前已成為全球科技競(jìng)爭(zhēng)新的戰(zhàn)略制高點(diǎn)。

0.1.1圖計(jì)算

圖可以將各類數(shù)據(jù)關(guān)聯(lián)起來：將不同來源、不同類型的數(shù)據(jù)融合到同一個(gè)圖里進(jìn)行分析，得到原本獨(dú)立分析難以發(fā)現(xiàn)的結(jié)果；
圖的表示可以讓很多問題處理地更加高效：例如最短路徑、連通分量等等，只有用圖計(jì)算的方式才能予以最高效的解決。然而，圖計(jì)算具有一些區(qū)別于其它類型計(jì)算任務(wù)的挑戰(zhàn)與特點(diǎn)：
隨機(jī)訪問多：圖計(jì)算圍繞圖的拓?fù)浣Y(jié)構(gòu)展開，計(jì)算過程會(huì)訪問邊以及關(guān)聯(lián)的兩個(gè)頂點(diǎn)，但由于實(shí)際圖數(shù)據(jù)的稀疏性（通常只有幾到幾百的平均度數(shù)），不可避免地產(chǎn)生了大量隨機(jī)訪問；
計(jì)算不規(guī)則：實(shí)際圖數(shù)據(jù)具有冪律分布的特性，即絕大多數(shù)頂點(diǎn)的度數(shù)很小，極少部分頂點(diǎn)的度數(shù)卻很大（例如在線社交網(wǎng)絡(luò)中明星用戶的粉絲），這使得計(jì)算任務(wù)的劃分較為困難，十分容易導(dǎo)致負(fù)載不均衡。

0.1.2圖計(jì)算系統(tǒng)

隨著圖數(shù)據(jù)規(guī)模的不斷增長(zhǎng)，對(duì)圖計(jì)算能力的要求越來越高，大量專門面向圖數(shù)據(jù)處理的計(jì)算系統(tǒng)便是誕生在這樣的背景下。

Pregel由Google研發(fā)是專用圖計(jì)算系統(tǒng)的開山之作。Pregel提出了以頂點(diǎn)為中心的編程模型，將圖分析過程分析為若干輪計(jì)算，每一輪各個(gè)頂點(diǎn)獨(dú)立地執(zhí)行各自的頂點(diǎn)程序，通過消息傳遞在頂點(diǎn)之間同步狀態(tài)。Giraph是Pregel的一個(gè)開源實(shí)現(xiàn)，F(xiàn)acebook基于Giraph使用200臺(tái)機(jī)器分析萬億邊級(jí)別的圖數(shù)據(jù)，計(jì)算一輪PageRank的用時(shí)近4分鐘。

GraphLab出自于CMU的實(shí)驗(yàn)室，基于共享內(nèi)存的機(jī)制，允許用戶使用異步的方式計(jì)算以加快某些算法的收斂速度。PowerGraph在GraphLab基礎(chǔ)上做了優(yōu)化，針對(duì)實(shí)際圖數(shù)據(jù)中頂點(diǎn)度數(shù)的冪律分布特性，提出了頂點(diǎn)分割的思想，可以實(shí)現(xiàn)更細(xì)粒度的數(shù)據(jù)劃分，從而實(shí)現(xiàn)更好的負(fù)載均衡。其計(jì)算模型也被用在后續(xù)的圖計(jì)算系統(tǒng)上，例如GraphX。

盡管上述的這些圖計(jì)算系統(tǒng)相比MapReduce、Spark等在性能上已經(jīng)有了顯著的性能提升，但是它們的計(jì)算效率依然非常低下，甚至不如精心優(yōu)化的單線程程序。

Gemini由清華大學(xué)計(jì)算機(jī)系的團(tuán)隊(duì)提出，針對(duì)已有系統(tǒng)的局限性，提出了以計(jì)算為中心的設(shè)計(jì)理念，通過降低分布式帶來的開銷并盡可能優(yōu)化本地計(jì)算部分的實(shí)現(xiàn)，使得系統(tǒng)能夠在具備擴(kuò)展性的同時(shí)不失高效性 [5] 。針對(duì)圖計(jì)算的各個(gè)特性，Gemini在數(shù)據(jù)壓縮存儲(chǔ)、圖劃分、任務(wù)調(diào)度、通信模式切換等方面都提出了對(duì)應(yīng)的優(yōu)化措施，比其他知名圖計(jì)算系統(tǒng)的最快性能還要快一個(gè)數(shù)量級(jí)。ShenTu沿用并擴(kuò)展了Gemini的編程和計(jì)算模型，能夠利用神威·太湖之光整機(jī)上千萬核的計(jì)算資源，高效處理70萬億邊的超大規(guī)模圖數(shù)據(jù)，入圍了2018年戈登·貝爾獎(jiǎng)的決賽名單。

除了使用向外擴(kuò)展的分布式圖計(jì)算系統(tǒng)來處理規(guī)模超出單機(jī)內(nèi)存的圖數(shù)據(jù)，也有一些解決方案通過在單臺(tái)機(jī)器上高效地使用外存來完成大規(guī)模圖計(jì)算任務(wù)，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。

0.2 圖關(guān)鍵技術(shù)

0.2.1 圖數(shù)據(jù)的組織

由于實(shí)際圖的稀疏性，圖計(jì)算系統(tǒng)通常使用稀疏矩陣的存儲(chǔ)方法來表示圖數(shù)據(jù)，其中最常用的兩種是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分別按行（列）存儲(chǔ)每行（列）非零元所在列（行），每一行則（列）對(duì)應(yīng)了一個(gè)頂點(diǎn)的出邊（入邊）。

0.2.2圖數(shù)據(jù)的劃分

將一個(gè)大圖劃分為若干較小的子圖，是很多圖計(jì)算系統(tǒng)都會(huì)使用的擴(kuò)展處理規(guī)模的方法；此外，圖劃分還能增強(qiáng)數(shù)據(jù)的局部性，從而降低訪存的隨機(jī)性，提升系統(tǒng)效率。對(duì)于分布式圖計(jì)算系統(tǒng)而言，圖劃分有兩個(gè)目標(biāo)：

每個(gè)子圖的規(guī)模盡可能相近，獲得較為均衡的負(fù)載。
不同子圖之間的依賴（例如跨子圖的邊）盡可能少，降低機(jī)器間的通信開銷。

圖劃分有按照頂點(diǎn)劃分和按照邊劃分兩種方式，它們各有優(yōu)劣：

頂點(diǎn)劃分將每個(gè)頂點(diǎn)鄰接的邊都放在一臺(tái)機(jī)器上，因此計(jì)算的局部性更好，但是可能由于度數(shù)的冪律分布導(dǎo)致負(fù)載不均衡。
邊劃分能夠最大程度地改善負(fù)載不均衡的問題，但是需要將每個(gè)頂點(diǎn)分成若干副本分布于不同機(jī)器上，因此會(huì)引入額外的同步/空間開銷。

所有的類Pregel系統(tǒng)采用的均為頂點(diǎn)劃分的方式，而PowerGraph/GraphX采用的是邊劃分的方式。Gemini采用了基于頂點(diǎn)劃分的方法來避免引入過大的分布式開銷；但是在計(jì)算模式上卻借鑒了邊劃分的思想，將每個(gè)頂點(diǎn)的計(jì)算分布到多臺(tái)機(jī)器上分別進(jìn)行，并盡可能讓每臺(tái)機(jī)器上的計(jì)算量接近，從而消解頂點(diǎn)劃分可能導(dǎo)致的負(fù)載不均衡問題。

0.2.3頂點(diǎn)程序的調(diào)度

在以頂點(diǎn)為中心的圖計(jì)算模型中，每個(gè)頂點(diǎn)程序可以并行地予以調(diào)度。大部分圖計(jì)算系統(tǒng)采用基于BSP模型的同步調(diào)度方式，將計(jì)算過程分為若干超步（每個(gè)超步通常對(duì)應(yīng)一輪迭代），每個(gè)超步內(nèi)所有頂點(diǎn)程序獨(dú)立并行地執(zhí)行，結(jié)束后進(jìn)行全局同步。頂點(diǎn)程序可能產(chǎn)生發(fā)送給其它頂點(diǎn)的消息，而通信過程通常與計(jì)算過程分離。

同步調(diào)度容易產(chǎn)生的問題是：

一旦發(fā)生負(fù)載不均衡，那么最慢的計(jì)算單元會(huì)拖慢整體的進(jìn)度。
某些算法可能在同步調(diào)度模型下不收斂。

為此，部分圖計(jì)算系統(tǒng)提供了異步調(diào)度的選項(xiàng)，讓各個(gè)頂點(diǎn)程序的執(zhí)行可以更自由，例如：每個(gè)頂點(diǎn)程序可以設(shè)定優(yōu)先級(jí)，讓優(yōu)先級(jí)高的頂點(diǎn)程序能以更高的頻率執(zhí)行，從而更快地收斂。然而，異步調(diào)度在系統(tǒng)設(shè)計(jì)上引入了更多的復(fù)雜度，例如數(shù)據(jù)一致性的維護(hù)，消息的聚合等等，很多情況下的效率并不理想。因此，大多數(shù)圖計(jì)算系統(tǒng)采用的還是同步的調(diào)度方式；少數(shù)支持異步計(jì)算的系統(tǒng)也默認(rèn)使用同步方式進(jìn)行調(diào)度。

0.2.4 計(jì)算與通信模式

圖計(jì)算系統(tǒng)使用的通信模式主要分為兩種，推動(dòng)（Push）和拉?。≒ull）：

推動(dòng)模式下每個(gè)頂點(diǎn)沿著邊向鄰居頂點(diǎn)傳遞消息，鄰居頂點(diǎn)根據(jù)收到的消息更新自身的狀態(tài)。所有的類Pregel系統(tǒng)采用的幾乎都是這種計(jì)算和通信模式。
拉取模式通常將頂點(diǎn)分為主副本和鏡像副本，通信發(fā)生在每個(gè)頂點(diǎn)的兩類副本之間而非每條邊連接的兩個(gè)頂點(diǎn)之間。GraphLab、PowerGraph、GraphX等采用的均為這種模式。

除了通信的模式有所區(qū)別，推動(dòng)和拉取在計(jì)算上也有不同的權(quán)衡：

推動(dòng)模式可能產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)，需要使用鎖或原子操作來保證狀態(tài)的更新是正確的。
拉取模式盡管沒有競(jìng)爭(zhēng)的問題，但是可能產(chǎn)生額外的數(shù)據(jù)訪問。

Gemini則將兩種模式融合起來，根據(jù)每一輪迭代參與計(jì)算的具體情況，自適應(yīng)地選擇更適合的模式。

0.3 圖計(jì)算應(yīng)用

0.3.1 網(wǎng)頁排序

將網(wǎng)頁作為頂點(diǎn)，網(wǎng)頁之間的超鏈接作為邊，整個(gè)互聯(lián)網(wǎng)可以建模成一個(gè)非常巨大的圖（十萬億級(jí)邊）。搜索引擎在返回結(jié)果時(shí)，除了需要考慮網(wǎng)頁內(nèi)容與關(guān)鍵詞的相關(guān)程度，還需要考慮網(wǎng)頁本身的質(zhì)量。

PageRank是最早Google用于對(duì)網(wǎng)頁進(jìn)行排序的算法，通過將鏈接看成投票來指示網(wǎng)頁的重要程度。PageRank的計(jì)算過程并不復(fù)雜：在首輪迭代開始前，所有頂點(diǎn)將自己的PageRank值設(shè)為1；每輪迭代中，每個(gè)頂點(diǎn)向所有鄰居貢獻(xiàn)自己當(dāng)前PageRank值除以出邊數(shù)作為投票，然后將收到的所有來自鄰居的投票累加起來作為新的PageRank值；如此往復(fù)，直到所有頂點(diǎn)的PageRank值在相鄰兩輪之間的變化達(dá)到某個(gè)閾值為止。

0.3.2 社區(qū)發(fā)現(xiàn)

社交網(wǎng)絡(luò)也是一種典型的圖數(shù)據(jù)：頂點(diǎn)表示人，邊表示人際關(guān)系；更廣義的社交網(wǎng)絡(luò)可以將與人有關(guān)的實(shí)體也納入進(jìn)來，例如手機(jī)、地址、公司等。社區(qū)發(fā)現(xiàn)是社交網(wǎng)絡(luò)分析的一個(gè)經(jīng)典應(yīng)用：將圖分成若干社區(qū)，每個(gè)社區(qū)內(nèi)部的頂點(diǎn)之間具有相比社區(qū)外部更緊密的連接關(guān)系。社區(qū)發(fā)現(xiàn)有非常廣泛的用途，在金融風(fēng)控、國(guó)家安全、公共衛(wèi)生等大量場(chǎng)景都有相關(guān)的應(yīng)用。

標(biāo)簽傳播是一種常用的社區(qū)發(fā)現(xiàn)算法：每個(gè)頂點(diǎn)的標(biāo)簽即為自己的社區(qū)，初始化時(shí)設(shè)置自己的頂點(diǎn)編號(hào)；在隨后的每一輪迭代中，每個(gè)頂點(diǎn)將鄰居中出現(xiàn)最頻繁的標(biāo)簽設(shè)置為自己新的標(biāo)簽；當(dāng)所有頂點(diǎn)相鄰兩輪之間的標(biāo)簽變化少于某個(gè)閾值時(shí)則停止迭代。

0.3.3最短路徑

在圖上發(fā)現(xiàn)頂點(diǎn)與頂點(diǎn)之間的最短路徑是一類很常見的圖計(jì)算任務(wù)，根據(jù)起始頂點(diǎn)與目標(biāo)頂點(diǎn)集合的大小，又可分為單對(duì)單（一個(gè)頂點(diǎn)到一個(gè)頂點(diǎn)）、多對(duì)多（多個(gè)頂點(diǎn)到多個(gè)頂點(diǎn)）、單源（一個(gè)頂點(diǎn)到所有其它頂點(diǎn)）、多源（多個(gè)頂點(diǎn)到所有其它頂點(diǎn)）、所有點(diǎn)對(duì)（所有頂點(diǎn)到其它所有頂點(diǎn)）等。對(duì)于無權(quán)圖，通常使用基于BFS的算法；對(duì)于有權(quán)圖，比較常見的有SPFA算法、Bellman-Ford算法等。

最短路徑的用途十分廣泛：在知識(shí)圖譜中經(jīng)常需要尋找兩個(gè)實(shí)體之間的最短關(guān)聯(lián)路徑；基于黑名單和實(shí)體之間的關(guān)聯(lián)可以發(fā)現(xiàn)其它頂點(diǎn)與黑名單之間的距離；而所有點(diǎn)對(duì)的最短路徑可以幫助衡量各個(gè)頂點(diǎn)在整個(gè)圖的拓?fù)浣Y(jié)構(gòu)所處的位置（中心程度）。

節(jié)點(diǎn)級(jí)別任務(wù)：金融詐騙檢測(cè)中，節(jié)點(diǎn)是用戶和商家，邊是用戶和商家之間的交互，利用圖模型預(yù)測(cè)潛在的金融詐騙分子。在目標(biāo)檢測(cè)案例中，將3D點(diǎn)云數(shù)據(jù)中點(diǎn)與點(diǎn)之間距離作為邊，通過圖結(jié)構(gòu)可以進(jìn)行3D目標(biāo)檢測(cè)

邊級(jí)別任務(wù)：推薦系統(tǒng)中，通過已有的用戶-商品數(shù)據(jù)建立用戶圖行為關(guān)系，得到節(jié)點(diǎn)的向量表示，進(jìn)而進(jìn)行推薦任務(wù)

圖級(jí)別任務(wù)：氣味識(shí)別，利用圖神經(jīng)網(wǎng)絡(luò)識(shí)別分子結(jié)構(gòu)進(jìn)而識(shí)別氣味

1.圖與圖學(xué)習(xí)

1.1 圖的基本表示方法

先簡(jiǎn)單學(xué)習(xí)一下圖論的基本概念，圖論的經(jīng)典算法，以及近些年來圖學(xué)習(xí)的發(fā)展

舉個(gè)例子，一個(gè)簡(jiǎn)單的圖可能是這樣：

節(jié)點(diǎn)（node）用紅色標(biāo)出，通過黑色的邊（edge）連接。

圖可用于表示:

社交網(wǎng)絡(luò)
網(wǎng)頁
生物網(wǎng)絡(luò)
…
我們可以在圖上執(zhí)行怎樣的分析？
研究拓?fù)浣Y(jié)構(gòu)和連接性
群體檢測(cè)
識(shí)別中心節(jié)點(diǎn)
預(yù)測(cè)缺失的節(jié)點(diǎn)
預(yù)測(cè)缺失的邊
…
圖 G=(V, E) 由下列要素構(gòu)成：
一組節(jié)點(diǎn)（也稱為 verticle）V=1,…,n
一組邊 E?V×V
邊 (i,j) ∈ E 連接了節(jié)點(diǎn) i 和 j
i 和 j 被稱為相鄰節(jié)點(diǎn)（neighbor）
節(jié)點(diǎn)的度（degree）是指相鄰節(jié)點(diǎn)的數(shù)量

節(jié)點(diǎn)、邊和度的示意圖

如果一個(gè)圖的所有節(jié)點(diǎn)都有 n-1 個(gè)相鄰節(jié)點(diǎn)，則該圖是完備的（complete）。也就是說所有節(jié)點(diǎn)都具備所有可能的連接方式。
從 i 到 j 的路徑（path）是指從 i 到達(dá) j 的邊的序列。該路徑的長(zhǎng)度（length）等于所經(jīng)過的邊的數(shù)量。
圖的直徑（diameter）是指連接任意兩個(gè)節(jié)點(diǎn)的所有最短路徑中最長(zhǎng)路徑的長(zhǎng)度。

舉個(gè)例子，在這個(gè)案例中，我們可以計(jì)算出一些連接任意兩個(gè)節(jié)點(diǎn)的最短路徑。該圖的直徑為 3，因?yàn)闆]有任意兩個(gè)節(jié)點(diǎn)之間的最短路徑的長(zhǎng)度超過 3。

一個(gè)直徑為 3 的圖

測(cè)地路徑（geodesic path）是指兩個(gè)節(jié)點(diǎn)之間的最短路徑。
如果所有節(jié)點(diǎn)都可通過某個(gè)路徑連接到彼此，則它們構(gòu)成一個(gè)連通分支（connected component）。如果一個(gè)圖僅有一個(gè)連通分支，則該圖是連通的（connected）

舉個(gè)例子，下面是一個(gè)有兩個(gè)不同連通分支的圖：

一個(gè)有兩個(gè)連通分支的圖

如果一個(gè)圖的邊是有順序的配對(duì)，則該圖是有向的（directed）。i 的入度（in-degree）是指向 i 的邊的數(shù)量，出度（out-degree）是遠(yuǎn)離 i 的邊的數(shù)量

有向圖

如果可以回到一個(gè)給定節(jié)點(diǎn)，則該圖是有環(huán)的（cyclic）。相對(duì)地，如果至少有一個(gè)節(jié)點(diǎn)無法回到，則該圖就是無環(huán)的（acyclic）。
圖可以被加權(quán)（weighted），即在節(jié)點(diǎn)或關(guān)系上施加權(quán)重。
如果一個(gè)圖的邊數(shù)量相比于節(jié)點(diǎn)數(shù)量較小，則該圖是稀疏的（sparse）。相對(duì)地，如果節(jié)點(diǎn)之間的邊非常多，則該圖是密集的（dense）

Neo4J 的關(guān)于圖算法的書給出了清晰明了的總結(jié)：

總結(jié)（來自 Neo4J Graph Book & 自尊心3大佬的貢獻(xiàn)）

1.2 圖的存儲(chǔ)

存儲(chǔ)圖的方式有三種：相鄰矩陣，鄰接表，十字鏈表

1.2.1 相鄰矩陣

有向圖的相鄰矩陣

無向圖的相鄰矩陣

使用鄰接矩陣，這通常是在內(nèi)存中加載的方式：

對(duì)于圖中的每一個(gè)可能的配對(duì)，如果兩個(gè)節(jié)點(diǎn)有邊相連，則設(shè)為 1。如果該圖是無向圖，則 A 是對(duì)稱的。

1.2.2 鄰接表

對(duì)于稀疏圖，可以采用鄰接表存儲(chǔ)法：

邊較少，相鄰矩陣就會(huì)出現(xiàn)大量的零元素相鄰矩陣的零元素將耗費(fèi)大量的存儲(chǔ)空間和時(shí)間

無向圖的鄰接表表示

無向圖同一條邊在鄰接表中出現(xiàn)兩次

上面的圖用鄰接表可表示為：

帶權(quán)圖的鄰接表表示

有向圖的鄰接表（出邊表）

有向圖的逆鄰接表（入邊表）

1.2.3 十字鏈表 (Orthogonal List)

可以看成是鄰接表和逆鄰接表的結(jié)合

對(duì)應(yīng)于有向圖的每一條弧有一個(gè)表目，共有5個(gè)域：

頭 headvex
尾 tailvex
下一條共尾弧 tailnextarc
下一條共頭弧 headnextarc
弧權(quán)值等 info 域

頂點(diǎn)表目由3個(gè)域組成：

data 域
firstinarc 第一條以該頂點(diǎn)為終點(diǎn)的弧
firstoutarc 第一條以該頂點(diǎn)為始點(diǎn)的弧

十字鏈表有兩組鏈表組成：

行和列的指針序列每個(gè)結(jié)點(diǎn)都包含兩個(gè)指針：
同一行的后繼
同一列的后繼

這三種表示方式都是等價(jià)的，我們可以根據(jù)使用場(chǎng)景來選擇圖的存儲(chǔ)方式。

1.3 圖的類型和性質(zhì)簡(jiǎn)單說明

圖可以根據(jù)不同標(biāo)準(zhǔn)進(jìn)行分類，我們?cè)谶@里主要講一種分類方法，同構(gòu)圖與異構(gòu)圖。

同構(gòu)圖與異構(gòu)圖

同構(gòu)圖：節(jié)點(diǎn)類型和邊的類型只有一種的圖。
異構(gòu)圖：節(jié)點(diǎn)類型+邊類型＞2 的圖。

兩個(gè)圖G和H是同構(gòu)圖（isomorphic graphs），能夠通過重新標(biāo)記圖G的頂點(diǎn)而產(chǎn)生圖H。

如果G和H同構(gòu)，那么它們的階是相同的，它們大小是相同的，它們個(gè)頂點(diǎn)的度數(shù)也對(duì)應(yīng)相同。

異構(gòu)圖是一個(gè)與同構(gòu)圖相對(duì)應(yīng)的新概念。

傳統(tǒng)同構(gòu)圖（Homogeneous Graph）數(shù)據(jù)中只存在一種節(jié)點(diǎn)和邊，因此在構(gòu)建圖神經(jīng)網(wǎng)絡(luò)時(shí)所有節(jié)點(diǎn)共享同樣的模型參數(shù)并且擁有同樣維度的特征空間。

而異構(gòu)圖（Heterogeneous Graph）中可以存在不只一種節(jié)點(diǎn)和邊，因此允許不同類型的節(jié)點(diǎn)擁有不同維度的特征或?qū)傩浴?/p>

2.圖算法與圖分析

圖分析使用基于圖的方法來分析連接的數(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è)，并對(duì)行為進(jìn)行預(yù)測(cè)

2.1 路徑搜索算法（Pathfinding and Search）

圖搜索算法（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路由問題，以及游戲模擬等。

圖的遍歷 (graph traversal)即給出一個(gè)圖G和其中任意一個(gè)頂點(diǎn)V0，從V0出發(fā)系統(tǒng)地訪問G中所有的頂點(diǎn)，每個(gè)頂點(diǎn)訪問而且只訪問一次

從一個(gè)頂點(diǎn)出發(fā)，試探性訪問其余頂點(diǎn)，同時(shí)必須考慮到下列情況

從一頂點(diǎn)出發(fā)，可能不能到達(dá)所有其它的頂點(diǎn)，如：非連通圖；
也有可能會(huì)陷入死循環(huán)，如：存在回路的圖

一般情況下，可以為每個(gè)頂點(diǎn)保留一個(gè) 標(biāo)志位 (mark bit)：

算法開始時(shí)，所有頂點(diǎn)的標(biāo)志位置零
在遍歷的過程中，當(dāng)某個(gè)頂點(diǎn)被訪問時(shí)，其標(biāo)志位就被標(biāo)記為已訪問

2.1.1深度優(yōu)先遍歷&廣度優(yōu)先遍歷|DFS & BFS

圖算法中最基礎(chǔ)的兩個(gè)遍歷算法：廣度優(yōu)先搜索（Breadth First Search，簡(jiǎn)稱 BFS）和深度優(yōu)先搜索（Depth First Search，簡(jiǎn)稱 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)之后再回溯。

深度優(yōu)先搜索（簡(jiǎn)稱DFS) 類似于樹的先根次序遍歷，盡可能先對(duì)縱深方向進(jìn)行搜索：

選取一個(gè)未訪問的點(diǎn) v0 作為源點(diǎn)
訪問頂點(diǎn) v0
遞歸地深搜遍歷 v0 鄰接到的其他頂點(diǎn)
重復(fù)上述過程直至從 v0 有路徑可達(dá)的頂點(diǎn)都已被訪問過
再選取其他未訪問頂點(diǎn)作為源點(diǎn)做深搜，直到圖的所有頂點(diǎn)都被訪問過

深度優(yōu)先搜索的順序是： a->b->c->f->d->e->g

廣度優(yōu)先遍歷（breadth-first search）

廣度優(yōu)先搜索 (breadth-first search，簡(jiǎn)稱 BFS)。其遍歷的過程是：

從圖中的某個(gè)頂點(diǎn) v0 出發(fā)
訪問并標(biāo)記了頂點(diǎn) v0 之后
一層層橫向搜索 v0 的所有鄰接點(diǎn)
對(duì)這些鄰接點(diǎn)一層層橫向搜索，直至所有由 v0 有路徑可達(dá)的頂點(diǎn)都已被訪問過
再選取其他未訪問頂點(diǎn)作為源點(diǎn)做廣搜，直到所有點(diǎn)都被訪問過

廣度優(yōu)先搜索的順序是： a->b->d->e->f->c->g

2.1.2 最短路徑

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

導(dǎo)航：谷歌、百度、高德地圖均提供了導(dǎo)航功能，它們就使用了最短路徑算法（或者非常接近的變種）；
社交網(wǎng)絡(luò)關(guān)系：當(dāng)我們?cè)?LinkedIn、人人（暴露年齡了）等社交平臺(tái)上查看某人的簡(jiǎn)介時(shí)，平臺(tái)會(huì)展示你們之間有多少共同好友，并列出你們之間的關(guān)系。

2.1.2.1 單源最短路徑(single-source shortest paths)-------迪杰斯特拉(Dijkstra)算法

單源最短路徑是給定帶權(quán)圖 G = ，其中每條邊 (vi，vj) 上的權(quán)W[vi，vj] 是一個(gè) 非負(fù)實(shí)數(shù) 。計(jì)算從任給的一個(gè)源點(diǎn) s 到所有其他各結(jié)點(diǎn)的最短路徑

迪杰斯特拉(Dijkstra)算法

最常見的最短路徑算法來自于 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)。

基本思想

把所有結(jié)點(diǎn)分成兩組:

第一組 U 包括已確定最短路徑的結(jié)點(diǎn)
第二組 V–U 包括尚未確定最短路徑的結(jié)點(diǎn)

按最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的結(jié)點(diǎn)加到第一組中:

直至從 s 出發(fā)可達(dá)結(jié)點(diǎn)都包括進(jìn)第一組中

看懂上面的再看一下這個(gè)判斷自己有沒有徹底理解：

Dijkstra 算法是貪心法，不適用于負(fù)權(quán)值的情況。因?yàn)闄?quán)值當(dāng)作最小取進(jìn)來后，不會(huì)返回去重新計(jì)算，即使不存在負(fù)的回路，也可能有在后面出現(xiàn)的負(fù)權(quán)值，從而導(dǎo)致整體計(jì)算錯(cuò)誤

2.1.2.2 每對(duì)結(jié)點(diǎn)間的最短路徑

Floyd算法求每對(duì)結(jié)點(diǎn)之間的最短路徑

用相鄰矩陣 adj 來表示帶權(quán)有向圖

基本思想

初始化 adj(0) 為相鄰矩陣 adj
在矩陣 adj(0)上做 n 次迭代，遞歸地產(chǎn)生一個(gè)矩陣序列adj(1)，…，adj(k)，…，adj(n)
其中經(jīng)過第k次迭代，adj(k)[i，j] 的值等于從結(jié)點(diǎn)vi 到結(jié)點(diǎn) vj 路徑上所經(jīng)過的結(jié)點(diǎn)序號(hào)不大于 k 的最短路徑長(zhǎng)度

其根本思想是動(dòng)態(tài)規(guī)劃法

最短路徑算法有兩個(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)對(duì)最短路徑（All Pairs Shortest Path）也是一個(gè)常用的最短路徑算法，計(jì)算所有節(jié)點(diǎn)對(duì)的最短路徑。相比較一個(gè)一個(gè)調(diào)用單個(gè)的最短路徑算法，All Pairs Shortest Path 算法會(huì)更快。算法并行計(jì)算多個(gè)節(jié)點(diǎn)的信息，并且這些信息在計(jì)算中可以被重用。

2.1.3 最小生成樹

最小生成樹（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í)間未知的問題，如旅行商問題。雖然該算法不一定總能找到絕對(duì)最優(yōu)解，但它使得復(fù)雜度極高和計(jì)算密集度極大的分析變得更加可能。例如：

旅行計(jì)劃：盡可能降低探索一個(gè)國(guó)家的旅行成本；
追蹤流感傳播的歷史：有人使用最小生成樹模型對(duì)丙型肝炎病毒感染的醫(yī)院暴發(fā)進(jìn)行分子流行病學(xué)調(diào)查

2.1.4 隨機(jī)游走

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

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

作為 node2vec 和 graph2vec 算法的一部分，這些算法可以用于節(jié)點(diǎn)向量的生成，從而作為后續(xù)深度學(xué)習(xí)模型的輸入；這一點(diǎn)對(duì)于了解 NLP （自然語言處理）的朋友來說并不難理解，詞是句子的一部分，我們可以通過詞的組合（語料）來訓(xùn)練詞向量。那么，我們同樣可以通過節(jié)點(diǎn)的組合（Random Walk）來訓(xùn)練節(jié)點(diǎn)向量。這些向量可以表征詞或者節(jié)點(diǎn)的含義，并且能夠做數(shù)值計(jì)算。這一塊的應(yīng)用很有意思，我們會(huì)找機(jī)會(huì)來詳細(xì)介紹；
作為 Walktrap 和 Infomap 算法的一部分，用于社群發(fā)現(xiàn)。如果隨機(jī)游走總是返回同一組節(jié)點(diǎn)，表明這些節(jié)點(diǎn)可能在同一個(gè)社群；
其他機(jī)器學(xué)習(xí)模型的一部分，用于隨機(jī)產(chǎn)生相關(guān)聯(lián)的節(jié)點(diǎn)數(shù)據(jù)。

2.2 中心性算法（Centrality Computation）

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

2.2.1 DegreeCentrality

Degree Centrality （度中心性，以度作為標(biāo)準(zhǔn)的中心性指標(biāo)）可能是整篇博文最簡(jiǎn)單的 “算法” 了。Degree 統(tǒng)計(jì)了一個(gè)節(jié)點(diǎn)直接相連的邊的數(shù)量，包括出度和入度。Degree 可以簡(jiǎn)單理解為一個(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)用場(chǎng)景例如，區(qū)分在線拍賣的合法用戶和欺詐者，欺詐者由于嘗嘗人為太高拍賣價(jià)格，擁有更高的加權(quán)中心性（weighted centrality）。

2.2.2 ClosenessCentrality

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

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

$C(u)=\frac{1}{\sum_{v=1}^{n-1} d(u, v)}$

其中 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ù)，你知道如何修改上面的公式嗎？對(duì)了，將分子的 1 變成 n-1 即可。

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

$H(u)=\frac{1}{\sum_{v=1}^{n-1} d(u, v)}$

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

$C{W F}(u)=\frac{n-1}{N-1}\left(\frac{n-1}{\sum{v=1}^{n-1} d(u, v)}\right)$

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

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

2.2.3 BetweennessCentrality

中介中心性（Betweenness Centrality）是一種檢測(cè)節(jié)點(diǎn)對(duì)圖中信息或資源流的影響程度的方法。它通常用于尋找連接圖的兩個(gè)部分的橋梁節(jié)點(diǎn)。因?yàn)楹芏鄷r(shí)候，一個(gè)系統(tǒng)最重要的 “齒輪” 不是那些狀態(tài)最好的，而是一些看似不起眼的 “媒介”，它們掌握著資源或者信息的流動(dòng)性。

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

$B(u)=\sum_{s \neq u \neq t} \frac{p(u)}{p}$

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

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

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

2.2.4 PageRank

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

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

$P R(u)=(1-d)+d\left(\frac{P R(T 1)}{C(T 1)}+\ldots+\frac{P R(T n)}{C(T n)}\right)$

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

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

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

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

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

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

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

尋找最重要的基因：我們要尋找的基因可能不是與生物功能聯(lián)系最多的基因，而是與最重要功能有緊密聯(lián)系的基因；
who to follow service at twitter：Twitter使用個(gè)性化的 PageRank 算法（Personalized PageRank，簡(jiǎn)稱 PPR）向用戶推薦他們可能希望關(guān)注的其他帳戶。該算法通過興趣和其他的關(guān)系連接，為用戶展示感興趣的其他用戶；
交通流量預(yù)測(cè)：使用 PageRank 算法計(jì)算人們?cè)诿織l街道上停車或結(jié)束行程的可能性；
反欺詐：醫(yī)療或者保險(xiǎn)行業(yè)存在異常或者欺詐行為，PageRank 可以作為后續(xù)機(jī)器學(xué)習(xí)算法的輸入。

2.3 社群發(fā)現(xiàn)算法（Community Detection）

社群的形成在各種類型的網(wǎng)絡(luò)中都很常見。識(shí)別社群對(duì)于評(píng)估群體行為或突發(fā)事件至關(guān)重要。對(duì)于一個(gè)社群來說，內(nèi)部節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)的關(guān)系（邊）比社群外部節(jié)點(diǎn)的關(guān)系更多。識(shí)別這些社群可以揭示節(jié)點(diǎn)的分群，找到孤立的社群，發(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ò)可視化。

2.3.1 MeasuringAlgorithm

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

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

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

$C C(u)=\frac{2 Ru}{ku\left(k_u-1\right)}$

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

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

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

2.3.2 ComponentsAlgorithm

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

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

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

2.3.3 LabelPropagation Algorithm

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

LPA 是一個(gè)較新的算法，由 Raghavan 等人于 2007 年提出。我們可以很形象地理解算法的傳播過程，當(dāng)標(biāo)簽在緊密聯(lián)系的區(qū)域，傳播非?？欤搅讼∈柽B接的區(qū)域，傳播速度就會(huì)下降。當(dāng)出現(xiàn)一個(gè)節(jié)點(diǎn)屬于多個(gè)社群時(shí)，算法會(huì)使用該節(jié)點(diǎn)鄰居的標(biāo)簽與權(quán)重，決定最終的標(biāo)簽。傳播結(jié)束后，擁有同樣標(biāo)簽的節(jié)點(diǎn)被視為在同一群組中。

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

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

2.3.4 LouvainModularity Algorithm

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

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

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

檢測(cè)網(wǎng)絡(luò)攻擊:該算可以應(yīng)用于大規(guī)模網(wǎng)絡(luò)安全領(lǐng)域中的快速社群發(fā)現(xiàn)。一旦這些社群被發(fā)現(xiàn)，就可以用來預(yù)防網(wǎng)絡(luò)攻擊；
主題建模：從 Twitter 和 YouTube 等在線社交平臺(tái)中提取主題，基于文檔中共同出現(xiàn)的術(shù)語，作為主題建模過程的一部分。

3.算法實(shí)踐（圖分析、圖計(jì)算）

有了前面的前置知識(shí)，來一起程序操作一下了

3.1創(chuàng)建一個(gè)圖進(jìn)行簡(jiǎn)單分析

import numpy as np import random import networkx as nx from IPython.display import Image import matplotlib.pyplot as plt # Load the graph G_karate = nx.karate_club_graph() # Find key-values for the graph pos = nx.spring_layout(G_karate) # Plot the graph nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

空手道俱樂部圖

這個(gè)「空手道」圖表示什么？Wayne W. Zachary 在 1970 到 1972 年這三年中研究的一個(gè)空手道俱樂部的社交網(wǎng)絡(luò)。該網(wǎng)絡(luò)包含了這個(gè)空手道俱樂部的 34 個(gè)成員，成員對(duì)之間的連接表示他們?cè)诰銟凡恐庖灿新?lián)系。在研究期間，管理員 JohnA 與教練 Mr.Hi（化名）之間出現(xiàn)了沖突，導(dǎo)致俱樂部一分為二。一半成員圍繞 Mr.Hi 形成了一個(gè)新的俱樂部，另一半則找了一個(gè)新教練或放棄了空手道。基于收集到的數(shù)據(jù)，除了其中一個(gè)成員，Zachary 正確分配了所有成員在分裂之后所進(jìn)入的分組。

# .degree() 屬性會(huì)返回該圖的每個(gè)節(jié)點(diǎn)的度（相鄰節(jié)點(diǎn)的數(shù)量）的列表： n=34 print(G_karate.degree()) degree_sequence = list(G_karate.degree())# 計(jì)算邊的數(shù)量，但也計(jì)算度序列的度量： nb_nodes = n nb_arr = len(G_karate.edges()) avg_degree = np.mean(np.array(degree_sequence)[:,1]) med_degree = np.median(np.array(degree_sequence)[:,1]) max_degree = max(np.array(degree_sequence)[:,1]) min_degree = np.min(np.array(degree_sequence)[:,1]) # 最后，打印所有信息： print("Number of nodes : " + str(nb_nodes)) print("Number of edges : " + str(nb_arr)) print("Maximum degree : " + str(max_degree)) print("Minimum degree : " + str(min_degree)) print("Average degree : " + str(avg_degree)) print("Median degree : " + str(med_degree))# 平均而言，該圖中的每個(gè)人都連接了 4.6 個(gè)人。 # 我們可以繪出這些度的直方圖： degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float') plt.figure(figsize=(12, 8)) plt.stem(degree_freq) plt.ylabel("Frequence") plt.xlabel("Degree") plt.show()

3.2圖類型

3.2.1 Erdos-Rényi 模型

在 Erdos-Rényi 模型中，我們構(gòu)建一個(gè)帶有 n 個(gè)節(jié)點(diǎn)的隨機(jī)圖模型。這個(gè)圖是通過以概率 p 獨(dú)立地在節(jié)點(diǎn) (i,j) 對(duì)之間畫邊來生成的。因此，我們有兩個(gè)參數(shù)：節(jié)點(diǎn)數(shù)量 n 和概率 p。

Erdos-Rényi 圖

在 Python 中，networkx 軟件包有用于生成 Erdos-Rényi 圖的內(nèi)置函數(shù)。

3.3主要圖算法

3.3.1路徑搜索算法

仍以空手道俱樂部圖舉例

# 1.最短路徑 # 最短路徑計(jì)算的是一對(duì)節(jié)點(diǎn)之間的最短的加權(quán)（如果圖有加權(quán)的話）路徑。 # 這可用于確定最優(yōu)的駕駛方向或社交網(wǎng)絡(luò)上兩個(gè)人之間的分離程度。 nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos) # 這會(huì)返回圖中每個(gè)節(jié)點(diǎn)之間的最小路徑的列表： all_shortest_path = nx.shortest_path(G_karate) # 這里打印了節(jié)點(diǎn)0與其余節(jié)點(diǎn)的最短路徑 print(all_shortest_path[0]) # 例如節(jié)點(diǎn)0與節(jié)點(diǎn)26的最短路徑是[0, 8, 33, 26]{0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5], 6: [0, 6], 7: [0, 7], 8: [0, 8], 10: [0, 10], 11: [0, 11], 12: [0, 12], 13: [0, 13], 17: [0, 17], 19: [0, 19], 21: [0, 21], 31: [0, 31], 30: [0, 1, 30], 9: [0, 2, 9], 27: [0, 2, 27], 28: [0, 2, 28], 32: [0, 2, 32], 16: [0, 5, 16], 33: [0, 8, 33], 24: [0, 31, 24], 25: [0, 31, 25], 23: [0, 2, 27, 23], 14: [0, 2, 32, 14], 15: [0, 2, 32, 15], 18: [0, 2, 32, 18], 20: [0, 2, 32, 20], 22: [0, 2, 32, 22], 29: [0, 2, 32, 29], 26: [0, 8, 33, 26]}

3.3.2社群檢測(cè)

社群檢測(cè)是根據(jù)給定的質(zhì)量指標(biāo)將節(jié)點(diǎn)劃分為多個(gè)分組。

這通常可用于識(shí)別社交社群、客戶行為或網(wǎng)頁主題。社區(qū)是指一組相連節(jié)點(diǎn)的集合。但是，目前關(guān)于社群還沒有廣泛公認(rèn)的定義，只是社群內(nèi)的節(jié)點(diǎn)應(yīng)該要密集地相連。

Girvan Newman 算法是一個(gè)用于發(fā)現(xiàn)社群的常用算法。其通過逐步移除網(wǎng)絡(luò)內(nèi)的邊來定義社區(qū)。我們將居間性稱為「邊居間性（edge betweenness）」。這是一個(gè)正比于穿過該邊的節(jié)點(diǎn)對(duì)之間最短路徑的數(shù)量的值。

該算法的步驟如下：

計(jì)算網(wǎng)絡(luò)中所有已有邊的居間性。
移除居間性最高的邊。
移除該邊后，重新計(jì)算所有邊的居間性。
重復(fù)步驟 2 和 3，直到不再剩余邊。

from networkx.algorithms import community import itertools k = 1 comp = community.girvan_newman(G_karate) for communities in itertools.islice(comp, k): ? ?print(tuple(sorted(c) for c in communities))

([0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21], [2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])

import community partition = community.best_partition(G_karate) pos = nx.spring_layout(G_karate) plt.figure(figsize=(8, 8)) plt.axis('off') nx.draw_networkx_nodes(G_karate, pos, node_size=600, cmap=plt.cm.RdYlBu, node_color=list(partition.values())) nx.draw_networkx_edges(G_karate, pos, alpha=0.3) plt.show(G_karate)

3.3.4 中心性算法

# Plot the centrality of the nodes plt.figure(figsize=(18, 12)) f, axarr = plt.subplots(2, 2, num=1) plt.sca(axarr[0,0]) nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_degree, node_size=300, pos=pos, with_labels=True) axarr[0,0].set_title('Degree Centrality', size=16) plt.sca(axarr[0,1]) nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_eigenvector, node_size=300, pos=pos, with_labels=True) axarr[0,1].set_title('Eigenvalue Centrality', size=16) plt.sca(axarr[1,0]) nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_closeness, node_size=300, pos=pos, with_labels=True) axarr[1,0].set_title('Proximity Centrality', size=16) plt.sca(axarr[1,1]) nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_betweenness, node_size=300, pos=pos, with_labels=True) axarr[1,1].set_title('Betweenness Centrality', size=16)

4.總結(jié)