一種基于GN算法的動態(tài)圖劃分方法*

羅曉霞，王 佳，羅香玉，李嘉楠

(西安科技大學計算機科學與技術(shù)學院，陜西 西安 710054)

1 引言

圖已經(jīng)被廣泛應用于醫(yī)療、食品、環(huán)保、氣象和生物等各個領(lǐng)域[1,2]。在現(xiàn)實世界中，圖在不斷地演化，例如社交網(wǎng)絡中[3]，新成員的加入、新關(guān)系的建立、成員之間聯(lián)系頻率的變化，這些都會引起圖的演化。并且隨著圖數(shù)據(jù)規(guī)模的急劇增長，單臺計算機已無法對其進行處理，因此分布式圖計算平臺日益流行[4,5]。對動態(tài)圖數(shù)據(jù)進行高效的劃分處理，是提高分布式圖計算效率的有效手段。

通過對圖劃分方法的深入研究發(fā)現(xiàn)，目前的一些算法主要是針對靜態(tài)圖劃分的研究[6,7]。Hash劃分、面向BSP(Bulk Synchronous Parallel)模型的負載均衡Hash圖數(shù)據(jù)劃分BHP(Balanced Hash Partition)、Range劃分、基于平衡標簽傳播的圖劃分BLP (Balanced Label propagation for Partitioning)等，這類算法適用于圖結(jié)構(gòu)穩(wěn)定、不發(fā)生變化和不需要實時響應的靜態(tài)圖。當處理隨時間動態(tài)演化的圖時，研究人員大多采用流式劃分方法。Stanton等人[8]考慮了各種啟發(fā)式方法來將圖頂點分配給處理器節(jié)點，并且必須在圖頂點添加到圖分區(qū)系統(tǒng)時進行劃分。Tsourakakis等人[9]提出可擴展的流圖劃分框架FENNEL，通過重新設計目標函數(shù)來考慮傳統(tǒng)平衡圖分區(qū)問題的硬約束以及切邊成本。Nishimura等人[10]將流式劃分的過程變?yōu)榈^程，圖的頂點能夠重新分配給處理器節(jié)點。駱融臻[11]設計并實現(xiàn)了一個能夠可靠使用的分布式流式圖劃分系統(tǒng)，每個子分類器通過全局的共享狀態(tài)進行同步，但存在較高的通信延遲。張夢琳[12]針對動態(tài)圖結(jié)構(gòu)，提出了一種有向性動態(tài)維護策略，通過判斷圖更新操作是否涉及邊界頂點而給出不同的邏輯移動策略。李茜錦[13]提出一種流圖分割方法，解決了有向圖流分割過程中的信息丟失問題。Lü等人[14]基于優(yōu)先級的調(diào)度算法為重要頂點指定較高的優(yōu)先級，以進行有效的處理，可以縮短收斂時間。以上關(guān)于動態(tài)圖劃分的研究，將頂點的當前鄰居信息作為劃分依據(jù)，并沒有考慮將來一段時間內(nèi)頂點鄰居信息的變化。當已劃分的頂點鄰居信息發(fā)生變化時，需要對這些頂點進行轉(zhuǎn)移，這將會帶來較大的頂點轉(zhuǎn)移開銷，降低圖劃分質(zhì)量。

為了解決該問題，本文提出了一種基于GN(Girvan and Newman)算法[15]的動態(tài)圖劃分方法。考慮到未來一段時間內(nèi)頂點鄰居信息的變化，先收集一段時間內(nèi)的若干個頂點鄰居信息變化操作，利用GN算法對新加入的頂點進行預劃分；然后將預劃分產(chǎn)生的社區(qū)結(jié)果插入到當前分區(qū)中，完成動態(tài)圖的劃分。

2 圖劃分的相關(guān)理論

2.1 GN算法

GN算法是一種社區(qū)發(fā)現(xiàn)算法，本質(zhì)是基于聚類的分裂思想，使用邊介數(shù)作為相似度的度量方法,邊介數(shù)是指圖中任意2個頂點通過此邊的最短路徑的數(shù)目。GN算法步驟如下所示：

首先計算圖中所有邊的邊介數(shù)；然后找到邊介數(shù)最大的邊并將它從圖中移除，計算此時的模塊度；接下來重新計算圖中剩下的邊介數(shù)；重復上述步驟，直到圖中所有的邊都被刪除，每個頂點單獨成為一個社區(qū)為止。因為GN算法不能判斷算法的終止位置，所以Newman引入了模塊度的概念，用來衡量社區(qū)的劃分是不是相對比較好的結(jié)果，比較每次劃分之后的模塊度，將模塊度最大的劃分結(jié)果作為最終社區(qū)劃分結(jié)果。模塊度計算公式如(1)所示：

(1)

其中，c表示圖中的一個社區(qū)；C為所有社區(qū)的集合；m表示圖中的總邊數(shù)；lc表示社區(qū)c中所有內(nèi)部邊的條數(shù)；Dc表示社區(qū)c中所有頂點的度之和。

使用GN算法可以較好地發(fā)現(xiàn)網(wǎng)絡中存在的社區(qū)結(jié)構(gòu)，該算法對存在孤立頂點的網(wǎng)絡、全連接社區(qū)、無權(quán)圖和高內(nèi)聚網(wǎng)絡等特殊形式，均表現(xiàn)出良好的魯棒性。

2.2 圖劃分評價指標

圖劃分結(jié)果主要有2個評價指標：負載均衡度和交叉邊數(shù)[16]。其中，負載均衡度是指圖數(shù)據(jù)應該盡可能均衡地被劃分到多臺計算機進行處理，以充分發(fā)揮分布式計算的性能優(yōu)勢。交叉邊是指一條邊的2個頂點被分配在不同的子圖中，交叉邊數(shù)會直接影響分布式計算時網(wǎng)絡的通信開銷[17]。

負載均衡度L是用各分區(qū)所含頂點數(shù)的方差來衡量，其計算公式如(2)所示:

(2)

其中，p表示分區(qū)的總個數(shù)；px表示第x個分區(qū)中的頂點個數(shù)，1≤x≤p；A表示圖中總頂點數(shù)與分區(qū)個數(shù)的比值，即每個分區(qū)中的平均頂點數(shù)。

交叉邊數(shù)是將各個子圖之間的交叉邊相加得到的結(jié)果，減少交叉邊數(shù)可提高各分區(qū)之間的通信效率。

3 基于GN算法的動態(tài)圖劃分方法

3.1 基本思想

動態(tài)圖的劃分問題可以描述如下：假設在t時刻，存在一個動態(tài)圖Gt(Vt，Et)，其中，Vt和Et分別表示圖Gt的頂點集和邊集，P={Pt1,Pt2,Pt3,…,Ptx}表示t時刻的初始劃分。經(jīng)過Δt時間之后，收集給定數(shù)量N的圖更新操作，求取新的劃分P′，同時保持較好的負載均衡度和交叉邊數(shù)。

本文方法的基本思想是：將收集到的N個圖更新操作進行分類處理，對于所有的頂點插入操作，首先用GN算法進行預劃分，之后將預劃分結(jié)果插入當前分區(qū)中；其余的頂點刪除、邊插入/刪除操作，分別根據(jù)收集的信息依次更新。本文方法的核心是基于GN算法，GN算法計算邊介數(shù)需要找到所有最短路徑，其時間復雜度為O(m*n)，總時間復雜度為O(m2*n)，所以本文方法的總時間復雜度在m條邊和n個頂點的圖中為O(m2*n)。

3.2 相關(guān)定義

定義1圖更新操作GUOPT(Graph Update Operation)：給定圖G，對該圖進行的每一次更新叫做一個圖更新操作，可以通過〈type,value〉的形式表示。type∈{1,2,3,4}，1表示插入頂點操作，2表示刪除頂點操作，3表示插入邊操作，4表示刪除邊操作；value表示具體更新的頂點或者邊的信息。

(1) 插入頂點操作：用〈1,value〉表示，value=i，i是圖G中新插入的頂點。

(2) 刪除頂點操作：用〈2,value〉表示，value=j，j是圖G中要刪除的頂點。

(3) 插入邊操作：用〈3,value〉表示，value=(u,v)，u和v都是圖G中的頂點，表示在頂點u和v之間插入一條邊.

(4) 刪除邊操作：用〈4,value〉表示，value=(u,v)，u和v都是圖G中的頂點，表示刪除頂點u和v之間的邊。

例如，〈1,2〉表示插入頂點2；〈2,1〉表示刪除頂點1；〈3,(2,3)〉表示在頂點2和頂點3之間添加一條邊；〈4,(1,3)〉表示刪除頂點1和頂點3之間的邊。

定義2圖更新操作集GUOPTS(Graph Update Operation Set)：由一段時間內(nèi)發(fā)生的圖更新操作組成，包含多個GUOPT操作，可以表示為：GUOPTS={GUOPT1,GUOPT2,GUOPT3,…,GUOPTy}，其中y表示第y個圖更新操作。

定義3圖更新操作總次數(shù)：在動態(tài)圖演化過程中，出現(xiàn)的所有圖更新操作次數(shù)的總和。

定義4圖更新頻度：使用基于GN算法的動態(tài)圖劃分方法對整個動態(tài)圖進行劃分所需要的劃分次數(shù)。當給定的圖更新操作集大小為N時，更新頻度M的計算公式如(3)所示：

(3)

3.3 基本步驟

以給定規(guī)模的圖更新操作集GUOPTS為劃分單位，收集若干個連續(xù)的圖更新操作之后，做出劃分決策?；贕N算法的動態(tài)圖劃分方法基本步驟如下所示：

步驟1根據(jù)式(3)計算動態(tài)圖劃分所需要的圖更新頻度M。

步驟2收集連續(xù)的N個圖更新操作，組成圖更新操作集GUOPTS。

步驟3對于插入頂點操作，用GN算法對GUOPTS進行處理，將新插入頂點所構(gòu)成的子圖預劃分，產(chǎn)生若干個獨立的社區(qū)，然后按照邊的插入和刪除以及頂點的刪除操作進行更新：

對于插入頂點操作，可以用〈1,i〉表示，使用GN算法對新增頂點進行預劃分，得到多個社區(qū)，社區(qū)內(nèi)部聯(lián)系緊密，社區(qū)之間聯(lián)系稀疏。對于插入邊操作，可以用〈3,(u,v)〉來表示，分為2種情況：當頂點u和頂點v同屬于當前圖或新增圖時，將(u,v)插入當前圖或新增圖中；當2個頂點中一個屬于當前圖，而另一個屬于新增圖時，將該邊記為當前圖與新增圖的交叉邊。對于刪除邊操作，可以用〈4,(u,v)〉來表示，分為2種情況：當頂點u和頂點v同屬于當前圖或新增圖時，將(u,v)從當前圖或新增圖中刪除；當2頂點中一個屬于當前圖，而另一個屬于新增圖時，將該邊從當前圖與新增圖的交叉邊中刪除。對于刪除頂點操作，可以用〈2,j〉來表示，j是圖中任意頂點的編號，無論該頂點屬于當前圖或新增圖，在對應的點集合中刪除該點的信息。

步驟4計算預劃分產(chǎn)生的每個社區(qū)與各個當前分區(qū)之間的交叉邊數(shù)，將各社區(qū)分別插入到與之交叉邊數(shù)最多的當前分區(qū)中。

將預劃分產(chǎn)生的社區(qū)結(jié)果插入到當前分區(qū)的具體步驟如下所示：首先，將預劃分產(chǎn)生的每個社區(qū)結(jié)果與各個當前分區(qū)之間的交叉邊數(shù)置為0；然后，從第一個社區(qū)開始循環(huán)，遍歷每一條連接該社區(qū)某個頂點與當前分區(qū)某個頂點的邊，每次都將對應當前分區(qū)關(guān)聯(lián)的交叉邊計數(shù)值加1，直到所有社區(qū)交叉邊計數(shù)結(jié)束；最后，比較每個社區(qū)與所有當前分區(qū)的交叉邊計數(shù)值，找出最大值，將社區(qū)插入到最大的交叉邊計數(shù)值對應的當前分區(qū)中。

步驟5根據(jù)更新頻度M判斷有無未處理的操作，若有，轉(zhuǎn)到步驟2；否則結(jié)束。

該方法的基本流程如圖1所示。

Figure 1 Basic process of dynamic graph partition圖1 動態(tài)圖劃分的基本流程

4 實驗與結(jié)果分析

4.1 數(shù)據(jù)集與實驗環(huán)境

實驗的數(shù)據(jù)集是來自斯坦福大學SNAP(Stanford Network Analysis Project)項目組公開圖數(shù)據(jù)集中的CollegeMsg和Soc-sign-bitcoin-otc，具如表1所示。

Table 1 Data sets

數(shù)據(jù)集CollegeMsg是由加州大學歐文分校的在線社交網(wǎng)絡上發(fā)送的私人消息組成，用戶可以在網(wǎng)絡中搜索其他人，然后根據(jù)個人資料信息發(fā)起對話，邊(e,f,t)表示用戶e在t時刻向用戶f發(fā)送了一條私人消息。數(shù)據(jù)集Soc-sign-bitcoin-otc是一個在Bitcoin OTC平臺進行比特幣交易的評價網(wǎng)絡，邊(e,f,t)表示用戶e在t時刻對用戶f進行了信用評價。由于圖的演化是一個平穩(wěn)的過程，針對動態(tài)圖的劃分，將上述2個數(shù)據(jù)集分別按1∶5的比例分為2部分，用少量數(shù)據(jù)作為當前圖，用大量數(shù)據(jù)作為圖的更新。

實驗運行環(huán)境是Windows 10，CPU配置是Intel(R) Core(TM) i5-4460，內(nèi)存配置是8 GB。基于Python 3.7實現(xiàn)本文提出的方法與傳統(tǒng)的流式劃分方法。

4.2 實驗及結(jié)果分析

本實驗分為圖更新操作集大小N的確定與圖劃分質(zhì)量對比2個階段。

第1階段：為了分析圖更新操作集的大小N對劃分質(zhì)量的影響，N分別取1 000,2 000,3 000,4 000,5 000和6 000進行實驗，使用第3節(jié)方法完成對整個CollegeMsg的劃分。實驗結(jié)果如圖2和圖3所示。

Figure 2 Load balance results圖2 負載均衡度結(jié)果

Figure 3 Crossed edges results圖3 交叉邊數(shù)結(jié)果

由圖2和圖3可得，隨著圖更新操作集大小N取值的增大，各分區(qū)所含頂點數(shù)方差和交叉邊數(shù)的值越來越小，曲線斜率也越來越小，由此說明，圖劃分質(zhì)量越來越好，但圖更新的實時性不斷地在損失。當N=4000時，圖劃分質(zhì)量和實時性最佳。在實際應用中，應該權(quán)衡劃分質(zhì)量和更新實時性2個方面來確定合適的圖更新操作集大小N。

第2階段：分別使用傳統(tǒng)流式劃分方法和本文方法對動態(tài)圖進行劃分，比較劃分之后的負載均衡度和交叉邊數(shù)的大小。根據(jù)第1階段的實驗結(jié)果，給定圖更新操作集的大小N=4000，由式(3)計算可得，完成數(shù)據(jù)集CollegeMsg的劃分所需要的更新頻度為13，完成數(shù)據(jù)集Soc-sign-bitcoin-otc的劃分需要的更新頻度為8。對數(shù)據(jù)集CollegeMsg的劃分負載均衡度對比和交叉邊數(shù)對比分別如圖4和圖5所示，對數(shù)據(jù)集Soc-sign-bitcoin-otc的劃分負載均衡度對比和交叉邊數(shù)對比分別如圖6和圖7所示。

Figure 4 Comparison of load balance (CollegeMsg)圖4 負載均衡度對比圖(CollegeMsg)

Figure 5 Comparison of crossed edges(CollegeMsg)圖5 交叉邊數(shù)對比圖(CollegeMsg)

Figure 6 Comparison of load balance (Soc-sign-bitcoin-otc)圖6 負載均衡度對比圖(Soc-sign-bitcoin-otc)

Figure 7 Comparison of crossed edges(Soc-sign-bitcoin-otc)圖7 交叉邊數(shù)對比圖(Soc-sign-bitcoin-otc)

由圖4和圖6可知，當經(jīng)過相同的圖更新頻度M時，本文方法的負載均衡度曲線明顯低于傳統(tǒng)的流式劃分方法的；由圖5和圖7可知，當經(jīng)過相同的圖更新頻度M時，本文方法的交叉邊數(shù)曲線明顯低于傳統(tǒng)的流式劃分方法的。由此可見，本文方法的劃分結(jié)果質(zhì)量明顯優(yōu)于流式劃分方法的，各分區(qū)負載更加均衡，且產(chǎn)生的交叉邊數(shù)更少。此外，隨著圖更新頻度M的增加，本文方法的優(yōu)越性更加明顯，最終在完成整個圖劃分時，相比流式劃分方法，本文方法對數(shù)據(jù)集CollegeMsg的劃分結(jié)果中交叉邊數(shù)減小了13%，負載均衡度減少了42.3%，本文方法對數(shù)據(jù)集Soc-sign-bitcoin-otc的劃分結(jié)果中交叉邊數(shù)減少了25.4%，負載均衡度減少了6%。

5 結(jié)束語

對圖數(shù)據(jù)進行合理劃分，是進行分布式圖計算和分析的基礎和前提。目前針對靜態(tài)圖的劃分研究已經(jīng)比較成熟，為了進一步提高動態(tài)圖的劃分質(zhì)量，本文提出了基于GN算法的動態(tài)圖劃分方法，對圖更新操作集內(nèi)的新增圖進行社區(qū)劃分，再將新增圖以社區(qū)為單位劃分至與之聯(lián)系緊密的當前分區(qū)中。實驗結(jié)果表明，相較于傳統(tǒng)流式劃分方法，該方法可顯著地提高動態(tài)圖的劃分質(zhì)量。未來還需要進一步研究圖更新操作集大小N的取值對劃分結(jié)果的影響。