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

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

(西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710054)

1 引言

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

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

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

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

2.1 GN算法

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

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

(1)

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

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

2.2 圖劃分評(píng)價(jià)指標(biāo)

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

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

(2)

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

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

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

3.1 基本思想

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

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

3.2 相關(guān)定義

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

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

(2) 刪除頂點(diǎn)操作：用〈2,value〉表示，value=j，j是圖G中要?jiǎng)h除的頂點(diǎn)。

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

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

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

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

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

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

(3)

3.3 基本步驟

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

實(shí)驗(yàn)的數(shù)據(jù)集是來(lái)自斯坦福大學(xué)SNAP(Stanford Network Analysis Project)項(xiàng)目組公開(kāi)圖數(shù)據(jù)集中的CollegeMsg和Soc-sign-bitcoin-otc，具如表1所示。

Table 1 Data sets

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

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

4.2 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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