一種基于GN算法的動態圖劃分方法*

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

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

1 引言

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

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

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

2 圖劃分的相關理論

2.1 GN算法

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

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

(1)

其中，c表示圖中的一個社區；C為所有社區的集合；m表示圖中的總邊數；lc表示社區c中所有內部邊的條數；Dc表示社區c中所有頂點的度之和。

使用GN算法可以較好地發現網絡中存在的社區結構，該算法對存在孤立頂點的網絡、全連接社區、無權圖和高內聚網絡等特殊形式，均表現出良好的魯棒性。

2.2 圖劃分評價指標

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

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

(2)

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

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

3 基于GN算法的動態圖劃分方法

3.1 基本思想

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

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

3.2 相關定義

定義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)：由一段時間內發生的圖更新操作組成，包含多個GUOPT操作，可以表示為：GUOPTS={GUOPT1,GUOPT2,GUOPT3,…,GUOPTy}，其中y表示第y個圖更新操作。

定義3圖更新操作總次數：在動態圖演化過程中，出現的所有圖更新操作次數的總和。

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

(3)

3.3 基本步驟

以給定規模的圖更新操作集GUOPTS為劃分單位，收集若干個連續的圖更新操作之后，做出劃分決策。基于GN算法的動態圖劃分方法基本步驟如下所示：

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

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

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

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

步驟4計算預劃分產生的每個社區與各個當前分區之間的交叉邊數，將各社區分別插入到與之交叉邊數最多的當前分區中。

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

步驟5根據更新頻度M判斷有無未處理的操作，若有，轉到步驟2；否則結束。

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

Figure 1 Basic process of dynamic graph partition圖1 動態圖劃分的基本流程

4 實驗與結果分析

4.1 數據集與實驗環境

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

Table 1 Data sets

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

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

4.2 實驗及結果分析

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

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

Figure 2 Load balance results圖2 負載均衡度結果

Figure 3 Crossed edges results圖3 交叉邊數結果

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

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

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

Figure 5 Comparison of crossed edges(CollegeMsg)圖5 交叉邊數對比圖(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 交叉邊數對比圖(Soc-sign-bitcoin-otc)

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

5 結束語

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