技术原创｜一文读懂图遍历算法以及图计算应用
為解決大規(guī)模計算和海量數(shù)據(jù)處理問題，Google 在 2010 年提出了圖計算模型 Pregel。隨后又陸續(xù)出現(xiàn)了。GraphLab、GraphChi等典型圖計算系統(tǒng)。
圖計算是人工智能的一個使能技術(shù)。
大數(shù)據(jù)時代，越來越多的數(shù)據(jù)采用圖結(jié)構(gòu)進行表示．圖也是一種能夠表達對象之間復(fù)雜關(guān)系的數(shù)據(jù)存儲方式。
那么，什么是圖？
下面是數(shù)據(jù)類型的結(jié)構(gòu)和圖的結(jié)構(gòu)表示對比：
?
可以看出：圖（ｇｒａｐｈ）是一種用于表示對象之間聯(lián)系的抽象數(shù)據(jù)結(jié)構(gòu)。
接下來，小普列舉幾個常見的圖計算模式：（這部分比較偏向于技術(shù)，想看應(yīng)用的小伙伴可以往下滑）
目前的圖計算框架基本上都遵循BSP（Bulk Synchronous Parallell）計算模式。它將計算分成一系列的超步（superstep）的迭代（iteration）。從縱向上看，它是一個串行模型，而從橫向上看，它是一個并行的模型，每兩個superstep之間設(shè)置一個柵欄（barrier），即整體同步點，確定所有并行的計算都完成后再啟動下一輪superstep。
超步可分為三個階段：
01計算
每一個processor利用上一個superstep傳過來的消息和本地的數(shù)據(jù)進行本地計算；
02消息傳遞
每一個processor計算完畢后，將消息傳遞給與之關(guān)聯(lián)的其它processors；
03整體同步
用于整體同步，確定所有的計算和消息傳遞都進行完畢后，進入下一個superstep。
BSP模型架構(gòu)
模型基于一個master協(xié)調(diào)，所有的worker同步(lock-step)執(zhí)行, 數(shù)據(jù)從輸入的隊列中讀取。
Pregel模型
Pregel在概念模型上遵循BSP模式。整個計算過程由若干順序運行的超級步（Super Step）組成，系統(tǒng)從一個“超級步”邁向下一個“超級步”，直到達到算法的終止條件。
超步的組成如下：
01vpro
是節(jié)點上的用戶定義的計算函數(shù)，運行在單個節(jié)點之上，在superstep 0，這個函數(shù)會在每個節(jié)點上以初始的initialMsg為參數(shù)運行并生成新的節(jié)點值。在隨后的超步中只有當節(jié)點收到信息，該函數(shù)才會運行。
02sendMsg
在當前超步中收到信息的節(jié)點用于向相鄰節(jié)點發(fā)送消息，這個消息用于下一個超步的計算。
03mergeMsg
用于聚合發(fā)送到同一節(jié)點的消息，這個函數(shù)的參數(shù)為兩個A類型的消息，返回值為一個A類型的消息。
Pregel模型的缺陷
01單節(jié)點無法并發(fā)處理
對于鄰居數(shù)很多的頂點，它需要處理的消息非常龐大，而且在這個模式下，它們是無法被并發(fā)處理的。所以對于符合冪律分布的自然圖，這種計算模型下很容易發(fā)生假死或者崩潰。
02消息傳遞開銷大
在圖的劃分上，采用的是簡單的hash方式，這樣固然能夠滿足負載均衡，但是hash方式并不能根據(jù)圖的連通特性進行劃分，導(dǎo)致超步之間的消息傳遞開銷可能會是影響性能的最大隱患。
03長時間等待
BSP模型本身有其局限性，整體同步并行對于計算快的worker長期等待的問題無法解決。
04內(nèi)存不足
由于pregel目前的計算狀態(tài)都是常駐內(nèi)存的，對于規(guī)模繼續(xù)增大的圖處理可能會導(dǎo)致內(nèi)存不足。
采用邊分割的存儲方式，重復(fù)存儲大量邊在內(nèi)存中
GAS模型
利用分布式圖計算中的頂點分割方法來對圖數(shù)據(jù)來進行分割，從而使得一個數(shù)據(jù)量巨大的圖，能夠在不同的分布式計算節(jié)點中進行平行計算。
但是當圖數(shù)據(jù)被分割后進入不同計算節(jié)點進行計算的時候，由于在不同節(jié)點中對于同一個節(jié)點有可能有多個副本，這個節(jié)點副本之間如何進行數(shù)據(jù)交換協(xié)同也成為了一個難題，于是GAS模型就被提出來解決這個難題。
GAS模型主要分為3個階段：Gather Apply Scatter
01Gather階段
Gather階段主要功能是規(guī)約（reduce），其上定義了一個sum函數(shù)，用于規(guī)約當前頂點通過邊收集到的信息。用戶通過自定義sum函數(shù)，指定了每個定點上的規(guī)約功能。如挑選出相鄰邊傳遞消息的最小值，或最大值。這里的sum不是一個簡單求和的意思，更確切地說，是將從周圍收集到地一系列信息整合成一個用戶想要地結(jié)果，并輸出給下一個階段。
02Apply階段
Apply階段，主要是針對每個頂點，將Gather階段地結(jié)果應(yīng)用到當前頂點上，即用戶通過自定義策略來根據(jù)Gather的結(jié)果更新當前頂點地值。
03Scatter階段
Scatter階段，根據(jù)Apply階段的結(jié)果，將當前頂點的最新結(jié)果更新到該頂點的邊上。
GAS對比Pregel的優(yōu)勢
相比叫Pregel，GAS將Pregel中的每個SuperStep一分為三，每個SubStep上對應(yīng)一個用戶自定義的操作。
一方面使得用戶的自由度更大，
另一方面能明顯提升個SubStep直接的并行計算性能，特別是當頂點關(guān)聯(lián)的邊非常大的時候。GAS計算模式在圖計算框架PoweGraph和GraphLab中得到了很好的應(yīng)用，并且在大規(guī)模關(guān)系網(wǎng)絡(luò)或復(fù)雜圖上取得了非常不錯的效果。
接下來，小普再介紹幾個常見的圖算法：“圖算法”就是基于圖的算法。
LPA標簽傳播算法
LPA是一種基于標簽傳播的局部社區(qū)劃分。對于網(wǎng)絡(luò)中的每一個節(jié)點，在初始階段，Label Propagation算法對于每一個節(jié)點都會初始化一個唯一的一個標簽。每一次迭代都會根據(jù)與自己相連的節(jié)點所屬的標簽改變自己的標簽，更改的原則是選擇與其相連的節(jié)點中所屬標簽最多的社區(qū)標簽為自己的社區(qū)標簽，這就是標簽傳播的含義了。隨著社區(qū)標簽不斷傳播。最終，連接緊密的節(jié)點將有共同的標簽：
01同步更新
在t輪迭代中，每個節(jié)點依賴的都是鄰居節(jié)點第t-1輪迭代的結(jié)果。
02異步更新
在t輪迭代中，每個節(jié)點依賴的是當前鄰居節(jié)點的社區(qū)標簽，若鄰居已經(jīng)進行了標簽更新，則依賴的是鄰居節(jié)點t時的標簽。
優(yōu)點：
LPA算法的最大的優(yōu)點就是算法的邏輯非常簡單，相對于優(yōu)化模塊度算法的過程是非常快的，不用louvain那樣的多次迭代優(yōu)化過程。
LPA算法利用自身的網(wǎng)絡(luò)的結(jié)構(gòu)指導(dǎo)標簽傳播，這個過程是無需任何的任何的優(yōu)化函數(shù)，而且算法初始化之前是不需要知道社區(qū)的個數(shù)的，隨著算法迭代最后可以自己知道最終有多少個社區(qū)。
缺點：
劃分結(jié)果不穩(wěn)定，隨機性強；
更新順序：節(jié)點標簽更新順序隨機，但是很明顯，越重要的節(jié)點越早更新會加速收斂過程；
隨機選擇：如果一個節(jié)點的出現(xiàn)次數(shù)最大的鄰居標簽不止一個時，隨機選擇一個標簽作為自己標簽。這種隨機性可能會帶來一個雪崩效應(yīng)，即剛開始一個小小的聚類錯誤會不斷被放大。不過，如果相似鄰居節(jié)點出現(xiàn)多個，可能是weight計算的邏輯有問題，需要回過頭去優(yōu)化weight抽象和計算邏輯。
SLPA算法
LPA是一種重疊型社區(qū)發(fā)現(xiàn)算法，其中涉及一個重要閾值參數(shù)r，通過r的適當選取，可將其退化為非重疊型，也就是LPA算法。
計算過程：
* 初始化所有節(jié)點的標簽信息，使得每個節(jié)點擁有唯一的標簽。
* 最為主要的是標簽傳播過程。
* 當前節(jié)點作為一個listener。
* 當前節(jié)點的每一個鄰居節(jié)點根據(jù)一定的speaking策略傳遞標簽信息。
* 當前節(jié)點從鄰居節(jié)點傳播的標簽信息集中根據(jù)一定的listener策略選擇一個標簽作為本次迭代中的新標簽。
* 算法收斂或遍歷達到指定的次數(shù)，算法結(jié)束。否則，標簽在不斷的遍歷過程中傳播。
* 標簽分類過程。后處理階段根據(jù)節(jié)點的標簽信息進行社區(qū)發(fā)現(xiàn)。
優(yōu)點：
算法SLPA 不會像其它算法一樣忘記上一次迭代中節(jié)點所更新的標簽信息，它給每個節(jié)點設(shè)置了一個標簽存儲列表來存儲每次迭代所更新的標簽。最終的節(jié)點社區(qū)從屬關(guān)系將由標簽存儲列表中所觀察到的標簽的概率決定，當一個節(jié)點觀察到有非常多一樣的標簽時，那么，很有可能這個節(jié)點屬于這個社區(qū)，而且在傳播過程中也很有可能將這個標簽傳播給別的節(jié)點。更有益處的是，這種標簽存儲列表的設(shè)計可以使得算法可以支持劃分重疊社區(qū)。
PageRank
PageRank，又稱網(wǎng)頁排名算法，Google用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性，在搜索引擎優(yōu)化操作中是經(jīng)常被用來評估網(wǎng)頁優(yōu)化的成效因素之一。
PR(u): 當前節(jié)點的PR值
PR(v): 邊指向當前節(jié)點的鄰居節(jié)點PR值
L(v): 邊指向當前節(jié)點的鄰居節(jié)點的出度
為了便于計算，我們假設(shè)每個頁面的PR初始值為1
PR(A) = PR(C) = 1
PR(B) = 0.5PR(A) = 0.5
PR(C) = 0.5PR(A) + PR(B) = 1.5
至此，我們模擬了一個簡化的 PageRank 的計算過程，實際情況會比這個復(fù)雜，可能會面臨兩個問題：
01等級泄露（Rank?Leak）
如果一個網(wǎng)頁沒有出鏈，就像是一個黑洞一樣，吸收了其他網(wǎng)頁的影響力而不釋放，最終會導(dǎo)致其他網(wǎng)頁的 PR 值為 0。
02等級沉沒（Rank Sink)
如果一個網(wǎng)頁只有出鏈，沒有入鏈（如下圖所示），計算的過程迭代下來，會導(dǎo)致這個網(wǎng)頁的 PR 值為 0。
針對等級泄露的情況，我們可以把沒有出鏈的節(jié)點，先從圖中去掉，等計算完所有節(jié)點的 PR 值之后，再加上該節(jié)點進行計算。不過這種方法會導(dǎo)致新的等級泄露的節(jié)點的產(chǎn)生，所以工作量還是很大的。
PageRank隨機瀏覽模型
為了解決簡化模型中存在的等級泄露和等級沉沒的問題，拉里·佩奇提出了 PageRank 的隨機瀏覽模型。他假設(shè)了這樣一個場景：用戶并不都是按照跳轉(zhuǎn)鏈接的方式來上網(wǎng)，還有一種可能是不論當前處于哪個頁面，都有概率訪問到其他任意的頁面，比如說用戶就是要直接輸入網(wǎng)址訪問其他頁面，雖然這個概率比較小。
所以他定義了阻尼因子 d，這個因子代表了用戶按照跳轉(zhuǎn)鏈接來上網(wǎng)的概率，通常可以取一個固定值 0.85，而 1-d=0.15 則代表了用戶不是通過跳轉(zhuǎn)鏈接的方式來訪問網(wǎng)頁的，比如直接輸入網(wǎng)址。
其中 N 為網(wǎng)頁總數(shù)，這樣我們又可以重新迭代網(wǎng)頁的權(quán)重計算了，因為加入了阻尼因子 d，一定程度上解決了等級泄露和等級沉沒的問題。
Louvain社區(qū)切分算法
Louvain算法是一種基于多層次（逐輪啟發(fā)式迭代）優(yōu)化模塊度（Modularity）的算法。模塊度函數(shù)最初被用于衡量社區(qū)發(fā)現(xiàn)算法結(jié)果的質(zhì)量，它能夠刻畫發(fā)現(xiàn)的社區(qū)的緊密程度。
同時，模塊度函數(shù)既然能刻畫社區(qū)的緊密程度，也就能夠被用來當作一個優(yōu)化函數(shù)（目標函數(shù)），即將結(jié)點加入它的某個鄰居所在的社區(qū)中，如果能夠提升當前社區(qū)結(jié)構(gòu)的模塊度。則說明這次迭代優(yōu)化是可接受的。
計算過程：
1. 不斷地遍歷網(wǎng)絡(luò)中的結(jié)點，嘗試將單個結(jié)點加入能夠使modularity提升最大的社區(qū)中，直到所有結(jié)點都不再變化
2. 處理第一階段的結(jié)果，將一個個小的社區(qū)歸并為一個超結(jié)點來重新構(gòu)造網(wǎng)絡(luò)，這時邊的權(quán)重為兩個結(jié)點內(nèi)所有原始結(jié)點的邊權(quán)重之和
3. 迭代以上兩個步驟直至算法穩(wěn)定或達到最大迭代次數(shù)
Louvain社區(qū)切分算法---模塊度增益
模塊度增益是針對單個節(jié)點定義的，當某個節(jié)點合并到某個社區(qū)中時，我們計算形成的全圖的modularity，然后和合并之前的全圖的modularity做對比即可得到該次節(jié)點合并時，模塊度的增益。
上式中ki,in是節(jié)點i與i要移入社區(qū)中所有節(jié)點之間邊權(quán)重和,∑tot是節(jié)點i要移入的社區(qū)內(nèi)所有節(jié)點的邊的權(quán)重和，上式可以理解為括號內(nèi)第一項ki,in表示實際節(jié)點i與要移入社區(qū)之間的連接邊的權(quán)重之和, 第二項∑tot/m為其它節(jié)點與該社區(qū)連接一條邊的概率,∑tot/m * ki則為基于平均情況下節(jié)點i在加權(quán)度為k的情況下與該社區(qū)連接的邊的權(quán)重. 第一項若比第二項大則說明節(jié)點i與該社區(qū)連接程度超過平均預(yù)測, 則加入到該社區(qū), 反之保持不變
圖計算應(yīng)用
為了快速處理圖數(shù)據(jù)和應(yīng)對不斷增長的圖數(shù)據(jù)，圖計算應(yīng)用被廣泛部署于各大數(shù)據(jù)中心，成為數(shù)據(jù)中心的典型應(yīng)用。用于表示 人際關(guān)系、分子拓撲結(jié)構(gòu)、大腦神經(jīng)元鏈接等．圖數(shù)據(jù)中蘊含著豐富的信息，圖計算應(yīng)用是一種挖掘圖數(shù)據(jù)中隱含價值的重要應(yīng)用．
接下來小普列舉一些圖計算應(yīng)用在數(shù)據(jù)挖掘中的應(yīng)用案例：
銀行圖計算應(yīng)用：利用關(guān)系的延展提升事后失聯(lián)催收的成功率
傳統(tǒng)催收系統(tǒng)以一度直接關(guān)系尋找逾期違約人員的聯(lián)系方式，往往因為信息失效導(dǎo)致失聯(lián)。
構(gòu)建統(tǒng)一數(shù)據(jù)視圖后的關(guān)系圖譜，可以通過其關(guān)系延展能力以及間接關(guān)系、隱藏關(guān)系的發(fā)現(xiàn)能力，幫助催收人員擴展更多與失信人相關(guān)的重要干系人和聯(lián)系方式，提升催收的效率和覆蓋率。
- 金融行業(yè)精準營銷：通過高AUM客戶的關(guān)系延展喚醒沉睡客戶和挖掘潛在客戶
經(jīng)過大數(shù)據(jù)分析，對低值客戶和潛在客戶推薦理財產(chǎn)品，容易出成效。購買理財產(chǎn)品的客群具有基數(shù)大，人均綜合AUM超過50萬，流失率低于10%，復(fù)購率高等特點，對優(yōu)化資產(chǎn)結(jié)構(gòu)和客戶結(jié)構(gòu)都有很好的優(yōu)化作用。
今天的分享就到這里啦，希望你有所收獲，覺得好記得給小普點個贊。
總結(jié)
以上是生活随笔為你收集整理的技术原创｜一文读懂图遍历算法以及图计算应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android面试专题系列(四)：Act
- 下一篇： 七十