2.1 圖算法的分類

所有的圖算法在本質(zhì)上都是對(duì)更為基礎(chǔ)的圖上的計(jì)算、分析與查詢操作的高度概括與集成。那么，什么是基礎(chǔ)的圖上的計(jì)算、分析與查詢操作呢？可以簡(jiǎn)單概括為以下兩類操作。

? 面向元數(shù)據(jù)的低維、離散的操作。典型的例如面向頂點(diǎn)或邊的聚合、排序等操作。

? 面向高維數(shù)據(jù)的操作。典型的例如路徑、子圖、網(wǎng)絡(luò)查詢以及圖算法等操作。

從圖計(jì)算的視角，面向元數(shù)據(jù)的操作與之前所有SQL或NoSQL數(shù)據(jù)庫(kù)沒(méi)有本質(zhì)區(qū)別，因此并不是本書(shū)的重點(diǎn)。面向高維數(shù)據(jù)的操作，指的是從關(guān)聯(lián)數(shù)據(jù)的角度，查詢數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系、關(guān)聯(lián)路徑和影響力范圍，例如我們常說(shuō)的根因分析（Root-cause Analysis）、貢獻(xiàn)度分析（Contribution Analysis）、歸因分析（Attribution Analysis）、影響力分析（Impact Analysis）、溯源分析（Backtracing）等。通過(guò)構(gòu)建圖數(shù)據(jù)模型，然后進(jìn)行圖上的查詢與分析，通常會(huì)獲得更高效、更靈活、更白盒化且更具可解釋性的效果。

高維數(shù)據(jù)的查詢有3個(gè)子類。

? 鄰居查詢：如最典型的k鄰查詢。

? 路徑查詢：如最短路徑、環(huán)路、權(quán)重路徑等。

? 展開(kāi)、組網(wǎng)等其他較復(fù)雜查詢：如從某頂點(diǎn)展開(kāi)、多頂點(diǎn)組網(wǎng)等。

當(dāng)然，所有的高維查詢都可以通過(guò)拆解或分而治之的方式降維為低維查詢，因?yàn)樗鼈兌际菑哪硞€(gè)或某類元數(shù)據(jù)（如頂點(diǎn)、邊或其屬性字段）開(kāi)始操作的，而這些高維查詢?cè)龠M(jìn)行組合、聚合、變形，就形成了我們所謂的圖算法。例如度算法中的全圖入度查詢，本質(zhì)上就是計(jì)算所有頂點(diǎn)的入度。顯然，在一張大圖上，這個(gè)看似簡(jiǎn)單的算法的計(jì)算復(fù)雜度可能會(huì)非常高，如何進(jìn)行加速就變成了重要的議題，我們會(huì)在第3章中進(jìn)行詳細(xì)分析。再比如全圖k鄰查詢（k-Hop Neighbors，k跳鄰居），在連通度較高的圖中，即便是查詢1個(gè)頂點(diǎn)的3跳、5跳鄰居都可能會(huì)非常耗時(shí)（假如1個(gè)頂點(diǎn)的1跳鄰居有20個(gè)，2跳鄰居有400個(gè)，3跳鄰居有8000個(gè)，而5跳鄰居已經(jīng)在3200000個(gè)的量級(jí)），如果有10000000個(gè)頂點(diǎn)，那么運(yùn)行完這個(gè)算法的耗時(shí)和復(fù)雜度將是天文量級(jí)的。不經(jīng)優(yōu)化的圖算法很多都是不具備實(shí)用性的，而優(yōu)化可以獲得指數(shù)級(jí)的性能提升與耗時(shí)降低—可能原來(lái)需要運(yùn)行1個(gè)月的算法，如果在不增加硬件投入的前提下能提速1000倍，降低至0.7h（約40min）內(nèi)完成，其意義是不言而喻的！這也是為什么圖算法的性能優(yōu)化如此重要。

在剖析圖算法的具體分類之前，我們先了解一個(gè)設(shè)計(jì)良好的圖算法應(yīng)該具備的特征。通過(guò)梳理過(guò)去一個(gè)半世紀(jì)以來(lái)多位數(shù)學(xué)家和計(jì)算機(jī)學(xué)家對(duì)于算法特征的共性探討，我們總結(jié)了如下5點(diǎn)：

1）無(wú)歧義，即確定的操作邏輯。

2）清晰、明確的操作步驟。

3）具備良好的可行性（如時(shí)間、空間、復(fù)雜度與效率）。

4）定義了明確的輸入、輸出規(guī)則，以及可驗(yàn)證正確性。

5）在有限步驟內(nèi)可以完成。

第一點(diǎn)關(guān)注算法中的每一步操作都應(yīng)該是可以明確定義與執(zhí)行的，即便是某種隨機(jī)化的操作。例如在后面的章節(jié)中介紹的隨機(jī)游走算法：從任意一個(gè)頂點(diǎn)出發(fā)，選中頂點(diǎn)的任意一個(gè)鄰居頂點(diǎn)作為訪問(wèn)的下一個(gè)頂點(diǎn)。算法的每一步操作都需要明確無(wú)歧義。

第二點(diǎn)關(guān)注算法的執(zhí)行步驟（多步）應(yīng)該有明確、清晰的定義。這可以看作對(duì)第一點(diǎn)中每個(gè)步驟的一種融會(huì)貫通。

第三點(diǎn)關(guān)注算法的可計(jì)算性、可行性，包括但不限于對(duì)系統(tǒng)資源的消耗，特別是算法的復(fù)雜度（如時(shí)間復(fù)雜度、空間復(fù)雜度等）。我們?cè)诘?章中會(huì)進(jìn)行詳細(xì)剖析。

第四點(diǎn)中討論的要點(diǎn)可分為兩個(gè)維度，一是對(duì)于輸入、輸出數(shù)據(jù)的定義與預(yù)期，二是數(shù)據(jù)的正確性驗(yàn)證。顯然，錯(cuò)誤的輸入數(shù)據(jù)與錯(cuò)誤的輸出結(jié)果只會(huì)帶來(lái)GIGO（Garbage-In and Garbage-Out，表示進(jìn)去和出來(lái)的都是垃圾）。

最后一點(diǎn)與第三點(diǎn)略有重疊，但是它著重突出的是算法可以在有限步驟內(nèi)得以終結(jié)。在這個(gè)前提下，我們需要關(guān)注算法占用的計(jì)算與存儲(chǔ)資源以及執(zhí)行時(shí)間與效率等。如果一個(gè)算法永遠(yuǎn)不會(huì)終結(jié)，那么它對(duì)于實(shí)際場(chǎng)景應(yīng)用而言會(huì)是災(zāi)難，意味著系統(tǒng)資源會(huì)被耗盡，出現(xiàn)災(zāi)難性的后果。顯然，我們需要盡可能避免這種情況的發(fā)生。

關(guān)于圖算法的分類，業(yè)界并沒(méi)有嚴(yán)格意義上的共識(shí)。有的側(cè)重于學(xué)術(shù)研究的圖計(jì)算框架，甚至?xí)褟V度優(yōu)先搜索（BFS）或深度優(yōu)先搜索（DFS）作為算法單列，盡管它們更適合作為一種圖遍歷模式存在。還有的如最短路徑算法，在20世紀(jì)計(jì)算機(jī)發(fā)展的前30年間（20世紀(jì)40年代至70年代），最短路徑算法不斷推陳出新，對(duì)于計(jì)算機(jī)體系架構(gòu)的發(fā)展有相當(dāng)大的推動(dòng)作用。圖2-2示意了一種典型的在圖上尋路所對(duì)應(yīng)的算法分類情況。

如圖2-2所示，DFS算法實(shí)現(xiàn)的是一種隨機(jī)游走式的尋路，且不關(guān)心路徑是否最短。BFS算法實(shí)現(xiàn)的是無(wú)權(quán)重最短尋路，而Dijkstra算法則實(shí)現(xiàn)的是有權(quán)重最短尋路。

我們?cè)谘芯繄D算法的分類時(shí)，一般都把圖算法歸類為組合數(shù)學(xué)算法的一部分，因?yàn)榻M合數(shù)學(xué)涉及的領(lǐng)域相當(dāng)廣泛，而圖論是其中相當(dāng)重要且有代表性的一部分。在組合數(shù)學(xué)中，幾乎所有的著名問(wèn)題，如旅行商問(wèn)題、地圖著色、任務(wù)分配、線性規(guī)劃（過(guò)河問(wèn)題）等，都與圖論或離散數(shù)學(xué)相關(guān)。按照在組合數(shù)學(xué)中的圖論類算法，可以簡(jiǎn)單地把算法作如下分類。

? 圖路由類算法：最小生成樹(shù)類算法、最短路徑問(wèn)題、最長(zhǎng)路徑問(wèn)題、旅行商問(wèn)題等。

? 網(wǎng)絡(luò)分析與網(wǎng)絡(luò)流算法：鏈接分析、網(wǎng)頁(yè)排序算法、網(wǎng)絡(luò)最大流問(wèn)題等。

? 圖搜索類算法：A*、B*、暴力搜索、回溯問(wèn)題、雙向搜索算法等。

? 子圖類算法：強(qiáng)鏈接子圖、團(tuán)（Clique）、同態(tài)子圖等。

? 圖可視化類算法：力導(dǎo)向圖、頻譜布局、分層渲染、弧式圖等。

? 其他圖算法：染色類算法、拓?fù)渑判蛩惴āD匹配算法、最大勢(shì)問(wèn)題等。

我們還可以按照如下五大維度分別對(duì)圖算法進(jìn)行分類，每個(gè)分類下又有一些典型子類算法。

1）按設(shè)計(jì)模式分類，可分為以下6類：

? 遍歷式（列舉式）。在圖算法以及圖查詢模式中，遍歷式是最為常見(jiàn)的。像廣度優(yōu)先算法與深度優(yōu)先算法是最常用的圖遍歷模式，很多現(xiàn)實(shí)世界的問(wèn)題就是通過(guò)這些遍歷模式解決的，如象棋、圍棋對(duì)弈問(wèn)題。下面的回溯式算法也可以看作遍歷式的一種特例。

? 窮舉式（暴力計(jì)算）。在海量數(shù)據(jù)集上，窮舉式計(jì)算并不一定是可行的，但很多情況下帶有過(guò)濾（圖上剪枝）規(guī)則的窮舉式計(jì)算又是必要的。例如在工商數(shù)據(jù)集中，搜索一個(gè)自然人與一個(gè)發(fā)行人（上市公司）之間的全部最短關(guān)聯(lián)路徑是完全可行的，即便兩者之間存在成千上萬(wàn)條路徑。

? 分而治之。分而治之是算法設(shè)計(jì)中最經(jīng)典的思路，把大的問(wèn)題縮小，把大的數(shù)據(jù)集縮小，通過(guò)遞歸、并發(fā)、分布式等方法來(lái)分塊處理，最后再匯總來(lái)解決全量的問(wèn)題。二進(jìn)制搜索、全圖k鄰算法等都是典型的采用分而治之的模式來(lái)解決問(wèn)題的算法。

? 回溯式、回溯式算法通常用于解決約束滿足問(wèn)題，如各種迷宮或字謎類的益智游戲（如經(jīng)典的國(guó)際象棋八皇后問(wèn)題、數(shù)獨(dú)問(wèn)題、背包問(wèn)題等）、地圖著色問(wèn)題、最大割問(wèn)題等。因?yàn)橛屑s束條件限定，算法在進(jìn)行某種隨機(jī)遍歷的過(guò)程中可能會(huì)通過(guò)回退（即回溯或剪枝）來(lái)優(yōu)化遍歷以找到正確的結(jié)果。

? 隨機(jī)化。通過(guò)隨機(jī)操作的方式來(lái)求解的算法在學(xué)術(shù)界與工業(yè)界都很常見(jiàn)，例如蒙特卡羅類算法在連通圖中計(jì)算最小割問(wèn)題的Karger算法，就是通過(guò)隨機(jī)刪除圖中的邊并合并刪前相連頂點(diǎn)的方式來(lái)實(shí)現(xiàn)以多項(xiàng)式時(shí)間復(fù)雜度（參見(jiàn)下文中的按復(fù)雜度分類）求解問(wèn)題。

? 歸約式。歸約式算法通過(guò)把一個(gè)問(wèn)題轉(zhuǎn)換（如映射）成另一個(gè)問(wèn)題，進(jìn)而尋求一種更簡(jiǎn)約的解決問(wèn)題的方式。例如廣度優(yōu)先搜索求某個(gè)（群）頂點(diǎn)的k跳鄰居中年齡最大者（或最小，或任意可度量維度或?qū)傩裕┑倪^(guò)程中，需要對(duì)結(jié)果集進(jìn)行排序（轉(zhuǎn)換），然后選取最大結(jié)果值返回，這就是一種典型的先轉(zhuǎn)換再求解的歸約式算法。

2）按優(yōu)化問(wèn)題模式分類，可分為以下3類：

? 線性規(guī)劃（LP）。在最優(yōu)化問(wèn)題求解的過(guò)程中，經(jīng)常會(huì)遇到線性規(guī)劃問(wèn)題，如商業(yè)管理中的降本增效問(wèn)題、交通能源與通信領(lǐng)域的最大網(wǎng)絡(luò)流問(wèn)題等。

? 動(dòng)態(tài)規(guī)劃（DP）。在經(jīng)濟(jì)學(xué)與航空工程學(xué)領(lǐng)域經(jīng)常會(huì)遇到動(dòng)態(tài)規(guī)劃問(wèn)題。簡(jiǎn)而言之，動(dòng)態(tài)規(guī)劃問(wèn)題一般通過(guò)把復(fù)雜的問(wèn)題以遞歸的方式分解為更小的問(wèn)題并找到最優(yōu)解來(lái)說(shuō)明該問(wèn)題具備最優(yōu)子結(jié)構(gòu)（Optimal Substructure）。例如，只要能證明貪心算法中的每一步都是最優(yōu)的，就可以用它來(lái)解決具有最優(yōu)子結(jié)構(gòu)的問(wèn)題。貪心算法通常可以被看作動(dòng)態(tài)規(guī)劃類算法的一個(gè)特例，最小生成樹(shù)（MST）類算法就是典型的通過(guò)分解子結(jié)構(gòu)來(lái)實(shí)現(xiàn)的貪心算法。

? 啟發(fā)式算法。啟發(fā)式算法是在常規(guī)方式無(wú)法找到最優(yōu)解的情況下（太慢或效果太差），通過(guò)在精度、準(zhǔn)確性、完整性、最優(yōu)性等維度之間進(jìn)行協(xié)調(diào)取舍，進(jìn)而實(shí)現(xiàn)一種近似最優(yōu)解的算法方案。

3）按復(fù)雜度分類。可分為以下5類：

? 恒定時(shí)間。復(fù)雜度O（1）就是典型的恒定時(shí)間。比如，無(wú)論數(shù)據(jù)集大小，通過(guò)數(shù)組或向量數(shù)據(jù)結(jié)構(gòu)訪問(wèn)任一頂點(diǎn)所需的時(shí)間恒定為O（1）。

? 線性時(shí)間。訪問(wèn)時(shí)間與輸入數(shù)據(jù)集大小成正比，例如遍歷全部頂點(diǎn)所需時(shí)間與數(shù)據(jù)集大小呈線性。

? 對(duì)數(shù)時(shí)間。典型的是二叉樹(shù)（或多叉樹(shù)）搜索類算法，比如在常見(jiàn)的數(shù)據(jù)庫(kù)索引數(shù)據(jù)結(jié)構(gòu)中，定位任一葉子節(jié)點(diǎn)所需的時(shí)間與數(shù)據(jù)集大小呈對(duì)數(shù)關(guān)系。顯然，在數(shù)據(jù)集相同的情況下，對(duì)數(shù)時(shí)間要比線性時(shí)間更短。

? 多項(xiàng)式時(shí)間。從時(shí)間復(fù)雜度上比較，指數(shù)時(shí)間要比多項(xiàng)式時(shí)間更長(zhǎng)。兩者量化的區(qū)別用一個(gè)具體的例子來(lái)說(shuō)明，如果數(shù)據(jù)量為N，多項(xiàng)式時(shí)間可能是aN3+bN2+1，而指數(shù)時(shí)間是N100，后者比前者復(fù)雜度更高。

? 指數(shù)時(shí)間。通常我們認(rèn)為，在大數(shù)據(jù)集上，如果一個(gè)算法是指數(shù)時(shí)間復(fù)雜度，則不具備真正意義上的可實(shí)施性。因?yàn)橛?jì)算復(fù)雜度可以理解為無(wú)窮大，問(wèn)題無(wú)法在有限時(shí)間內(nèi)得到解決。例如窮舉式暴力搜索算法，其算法復(fù)雜度與輸入數(shù)據(jù)集大小呈指數(shù)關(guān)系，窮舉全部可能的結(jié)果并不現(xiàn)實(shí)，這時(shí)通常會(huì)采用近似算法把時(shí)間復(fù)雜度至少降低到多項(xiàng)式時(shí)間。

4）按實(shí)現(xiàn)方法分類，可分為以下5類：

? 遞歸與非遞歸。每一個(gè)算法都可以以遞歸或非遞歸的方式實(shí)現(xiàn)，區(qū)別在于實(shí)現(xiàn)算法的邏輯步驟以及具體使用的數(shù)據(jù)結(jié)構(gòu)，進(jìn)而導(dǎo)致具體的算法實(shí)現(xiàn)方式的效率有所不同。

? 串行與并行。幾乎所有的圖算法初始都是以串行的思路設(shè)計(jì)的，但是很多都可以通過(guò)并行（并發(fā)）來(lái)得到性能的大幅提升。

? 集中式與分布式。同上，分布式要求對(duì)算法的數(shù)據(jù)結(jié)構(gòu)及系統(tǒng)架構(gòu)進(jìn)行大幅改造，有的算法進(jìn)行簡(jiǎn)單改造就可以獲得很好的分布式條件下的效率提升，但有些算法采用分布式可能會(huì)出現(xiàn)指數(shù)級(jí)的性能下降。因此，改造與否、如何改造是研究算法與系統(tǒng)架構(gòu)設(shè)計(jì)的專業(yè)人士需要格外注意的地方。

? 確定性與非確定性。所謂啟發(fā)式算法指的就是后者。

? 精確式與近似式。有一部分圖算法可以采用近似求解的方式來(lái)使之前極高的算法復(fù)雜度得到指數(shù)級(jí)降低，從而達(dá)到資源消耗可控的目的。

5）按研究領(lǐng)域分類。領(lǐng)域劃分通常沒(méi)有明確的邊界，且多個(gè)領(lǐng)域之間會(huì)有大量的重疊，因此這種劃分方式并不固定。

? 搜索。搜索又可以細(xì)分為路徑搜索、元數(shù)據(jù)搜索、子圖（網(wǎng)絡(luò)）搜索等。

? 排序。排序又可細(xì)分為元數(shù)據(jù)排序、路徑長(zhǎng)短排序、圖規(guī)模排序等。

? 合并。在圖查詢與算法的計(jì)算過(guò)程中，合并是個(gè)極為常見(jiàn)的操作，具體的邏輯類似于合并排序（Merge Sort）算法，特別是在多線程并發(fā)情況下的算法實(shí)現(xiàn)。

? 數(shù)值分析。數(shù)值分析在本質(zhì)上是一種數(shù)值化近似方式的算法，通過(guò)量化的方式來(lái)加速求解，比如，保險(xiǎn)行業(yè)精算師的主要工作就是進(jìn)行數(shù)值分析，以及金融業(yè)中的存貸款定價(jià)、風(fēng)險(xiǎn)量化分析等操作，都可以通過(guò)數(shù)值分析類算法來(lái)實(shí)現(xiàn)。而通過(guò)巧妙設(shè)計(jì)的圖算法，可以讓這些數(shù)值分析的準(zhǔn)確度、效率與可解釋性都遠(yuǎn)超之前基于機(jī)器學(xué)習(xí)、深度學(xué)習(xí)的方法。

工業(yè)界的圖數(shù)據(jù)庫(kù)廠商可能還會(huì)有不同的分類方法，圖2-3所示也是一種算法分類（5類）。

本書(shū)在后面的章節(jié)中綜合了學(xué)術(shù)界和工業(yè)界圖計(jì)算領(lǐng)域目前最新的發(fā)展情況，把圖算法劃分為了以下六大類，并分別對(duì)應(yīng)第4～9章的內(nèi)容：

? 中心性（Centrality）算法：如節(jié)點(diǎn)出入度、全圖出入度、接近中心性、中介中心性、圖中心性、調(diào)和中心性等。

? 相似度（Similarity）算法：如杰卡德（Jaccard）相似度、余弦相似度、歐幾里得距離等。

? 連通性和緊密度（Connectivity）算法：如強(qiáng)弱連通分量、三角形計(jì)算、二分圖、MST、全圖k鄰等。

? 拓?fù)滏溄宇A(yù)測(cè)（Topology&Connectivity）算法：共同鄰居、AA指標(biāo)、優(yōu)先連接等。

? 傳播與分類（Propagation & Categorization）算法：如LPA、HANP算法、k均值、魯汶識(shí)別等。

? 圖嵌入（Graph Embedding）算法：如隨機(jī)游走、FastRP、Node2Vec、Struc2Vec、GraphSAGE等。

需要指出的是，分類有助于我們梳理知識(shí)，但也并非一成不變。有一些算法可能會(huì)橫跨在多個(gè)分類中，例如MST既屬于連通性和緊密度算法又屬于拓?fù)滏溄宇A(yù)測(cè)算法。算法本身也會(huì)不斷演進(jìn)，推陳出新。有一些算法在發(fā)明之時(shí)做了一些假設(shè)，但是隨著時(shí)代的變化，那些假設(shè)已不再適合了。仍以MST算法為例，它的最初目標(biāo)是從一個(gè)頂點(diǎn)出發(fā)，使用權(quán)重最小的邊連通與之關(guān)聯(lián)的所有節(jié)點(diǎn)，該算法假設(shè)全圖是連通的（即只有一個(gè)連通分量）。而很多真實(shí)的場(chǎng)景中存在大量的孤點(diǎn)以及多個(gè)連通分量，此時(shí)算法就需要去適配這些情況，在算法調(diào)用接口及參數(shù)上就需要支持多頂點(diǎn)ID、允許指定權(quán)重對(duì)應(yīng)的屬性字段，以及支持限定返回結(jié)果集數(shù)量等。

最后，我們用一張腦圖來(lái)總結(jié)圖算法的分類，如圖2-4所示。