基于BFS結(jié)果集的可達(dá)性保持圖并行計(jì)算

謝 羿（沈陽黎明航空發(fā)動(dòng)機(jī)（集團(tuán)）有限責(zé)任公司，遼寧 沈陽 110043）

?

基于BFS結(jié)果集的可達(dá)性保持圖并行計(jì)算

謝 羿
（沈陽黎明航空發(fā)動(dòng)機(jī)（集團(tuán)）有限責(zé)任公司，遼寧 沈陽 110043）

摘 要：傳統(tǒng)計(jì)算可達(dá)性保持圖的方法通常基于單機(jī)模式，針對小規(guī)模數(shù)據(jù)集進(jìn)行計(jì)算。在處理大規(guī)模圖數(shù)據(jù)以及大量中間數(shù)據(jù)時(shí)，傳統(tǒng)方法將面臨內(nèi)存容量和計(jì)算速度的瓶頸問題。為了解決上述問題，本文提出了基于BFS結(jié)果集的可達(dá)性保持圖并行計(jì)算方法。

關(guān)鍵詞：圖數(shù)據(jù)；可達(dá)；MapReduce；并行化；保持圖

0 引言

可達(dá)性保持圖實(shí)質(zhì)上是一種在可達(dá)性查詢方面與原始圖等價(jià)的壓縮圖。其目的是獲取可達(dá)性保持圖，以解決直接基于原始圖進(jìn)行可達(dá)性查詢開銷過大的問題。算法首先使用廣度優(yōu)先遍歷（BFS）獲得原始圖中每個(gè)頂點(diǎn)的所有祖先頂點(diǎn)和后代頂點(diǎn)，然后通過基于類似鄰居匹配的方法匹配原始圖中各頂點(diǎn)的祖先頂點(diǎn)集和后代頂點(diǎn)集來尋找等價(jià)類，并對等價(jià)類進(jìn)行壓縮處理。

1 基于BFS結(jié)果集的可達(dá)性保持圖并行計(jì)算

1.1 基于BFS結(jié)果集的SCC并行查找算法

定理1：強(qiáng)連通分量內(nèi)的任意兩頂點(diǎn)相互可達(dá)。

根據(jù)定理1，我們可以推出：對于某一強(qiáng)連通分量SCC內(nèi)的任意一個(gè)頂點(diǎn)v，SCC中除v之外的其他頂點(diǎn)既包含于v的向后BFS結(jié)果集N-，又包含于v的向前BFS結(jié)果集N+。本文不考慮單一頂點(diǎn)作為強(qiáng)連通分量進(jìn)行處理，對于可達(dá)性等價(jià)類的處理同樣也不考慮將單一頂點(diǎn)作為等價(jià)類處理?；贐FS結(jié)果集的SCC查找算法如下：

（1）輸入每個(gè)頂點(diǎn)v的向后BFS結(jié)果集N-和向前BFS結(jié)果集N+；

（2）對同一個(gè)頂點(diǎn)v，求temp=N-（v）∩N+（v）；

（3）如果|temp|＞0，則SCC= temp∪｛v｝，輸出SCC；否則，返回步驟1，計(jì)算下一個(gè)頂點(diǎn)。

（4）對所有輸出的SCC去重，得到最終的全部SCC結(jié)果集。

1.2 基于標(biāo)簽傳遞更新的SCC壓縮算法

壓縮強(qiáng)連通分量后，為不影響圖中各頂點(diǎn)與強(qiáng)連通分量之間的可達(dá)性，我們提出了基于標(biāo)簽傳遞更新的強(qiáng)連通分量壓縮算法。

對于圖1（a），我們選取本體點(diǎn)v5作為傳遞標(biāo)簽，刪除所有自指邊后得到的更新圖為圖1（b）。

圖1標(biāo)簽傳遞更新SCC

需要注意的是，原始圖中的SCC將被表示為超點(diǎn)（本體點(diǎn)），傳遞更新后并不影響圖中其他頂點(diǎn)到超點(diǎn)的可達(dá)性關(guān)系，因此滿足可達(dá)性等價(jià)條件。標(biāo)簽傳遞更新SCC后獲得的壓縮圖為可達(dá)性保持圖?；跇?biāo)簽傳遞更新的SCC壓縮算法描述如下：

（1）選取SCC傳遞標(biāo)簽；因?yàn)镾CC內(nèi)的頂點(diǎn)已經(jīng)排序，所以選擇標(biāo)簽值最小的點(diǎn)（本體點(diǎn)）作為標(biāo)簽傳遞起始點(diǎn)。

（2）對屬于同一個(gè)SCC的其他所有頂點(diǎn)，傳遞更新其標(biāo)簽為本體點(diǎn)標(biāo)簽；同一個(gè)SCC內(nèi)的各頂點(diǎn)之間的相關(guān)邊將轉(zhuǎn)換為自指邊。超點(diǎn)（本體點(diǎn)）將繼承原SCC與外部相關(guān)聯(lián)的邊。

（3）遍歷原始圖中的邊，如果存在自指邊則刪除。

（4）輸出更新圖。

2 仿真實(shí)驗(yàn)和分析

實(shí)驗(yàn)使用6臺P C機(jī)搭建的基于Hadoop2.4.0版本的計(jì)算集群。其中1臺作為Master節(jié)點(diǎn)，另外5臺作為Slave節(jié)點(diǎn)。

算法的有效性：我們通過計(jì)算壓縮比來評估可達(dá)性保持圖壓縮獲取的有效性。壓縮比的計(jì)算公式為CPR=|Gr|/|G|，其中|G|表示原始圖的規(guī)模，|Gr|表示可達(dá)性保持圖（壓縮圖）的規(guī)模。實(shí)驗(yàn)首先基于標(biāo)簽傳遞更新SCC壓縮算法獲得原始圖的可達(dá)性保持圖，并計(jì)算了可達(dá)性保持圖相對于原始圖的壓縮比CPRLS。在標(biāo)簽傳遞更新SCC后的可達(dá)性保持圖基礎(chǔ)上，我們通過壓縮并更新可達(dá)性等價(jià)類來進(jìn)一步獲取可達(dá)性保持圖，并計(jì)算出最終的可達(dá)性保持圖相對于原始圖的壓縮比CPRLSEQ。壓縮比越小，表明壓縮方案的壓縮效果越好，即最終獲得的可達(dá)性保持圖的規(guī)模越小。

表1可達(dá)性保持圖相對于原始圖的壓縮比

從表1可以看出，各數(shù)據(jù)集在標(biāo)簽傳遞更新SCC后所獲得的可達(dá)性保持圖從整體上達(dá)到了較好的壓縮效果。在壓縮更新可達(dá)性等價(jià)類后獲得的可達(dá)性保持圖的規(guī)模進(jìn)一步減小。對于同一類型的網(wǎng)絡(luò)圖，如p2p網(wǎng)絡(luò)，可達(dá)性等價(jià)類壓縮更新方法可將可達(dá)性保持圖的壓縮比平均降低21個(gè)百分點(diǎn)。

查詢性能分析：本組實(shí)驗(yàn)通過對原始圖和可達(dá)性保持圖中的所有頂點(diǎn)分別進(jìn)行BFS遍歷來對比在兩種圖數(shù)據(jù)上的查詢性能。

如圖2所示，在可達(dá)性保持圖上的查詢時(shí)間明顯少于在原始圖上的查詢時(shí)間，進(jìn)一步證明了本文可達(dá)性保持圖的有效性。

加速比實(shí)驗(yàn)分析：加速比可以作為衡量并行計(jì)算相對于串行計(jì)算性能提升的指標(biāo)。加速比越大說明并行計(jì)算效率越好。

由圖3可以看出，隨著計(jì)算節(jié)點(diǎn)的增加，測試集的加速比逐漸增大。但由于計(jì)算節(jié)點(diǎn)數(shù)的增加導(dǎo)致節(jié)點(diǎn)間的數(shù)據(jù)傳輸量增加，會產(chǎn)生額外的網(wǎng)絡(luò)傳輸時(shí)間，因此加速比的增長趨勢逐漸平緩。

圖2查詢性能對比

圖3加速比實(shí)驗(yàn)

結(jié)語

為解決大規(guī)模圖數(shù)據(jù)的存儲和可達(dá)性保持圖在單機(jī)計(jì)算方面產(chǎn)生的瓶頸問題，本文著重研究了基于BFS的結(jié)果集的可達(dá)性保持圖并行計(jì)算方法，并利用Map Reduce模型實(shí)現(xiàn)了分布式、并行計(jì)算可達(dá)性保持圖。實(shí)驗(yàn)表明，本文可達(dá)性保持圖計(jì)算方法是有效的。在保證可達(dá)性查詢等價(jià)的同時(shí)，可達(dá)性保持圖具有更好的壓縮比和查詢性能。在基于分布式的計(jì)算平臺上，本文計(jì)算方案表現(xiàn)出較好的加速比。

參考文獻(xiàn)

［1］ Fan W，Li J，Wang X， et al. Query preserving graph compression［C］.Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM， 2012： 157-168.

［2］ Elberfeld M， Bafna V， Gamzu I， et al. On the approximability of reachability-preserving network orientations［J］. Internet Mathematics， 2011， 7（4）： 209-232.

［3］ Liu X， Wang B， Yang X. Efficiently anonymizing social networks with reachability preservation［C］.Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM，2013： 1613-1618.

［4］ WILKINSON B， ALLEN M.陸鑫達(dá)，譯.并行程序設(shè)計(jì)［M］. 北京：機(jī)械工業(yè)出版社，2002.

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A