基于BFS結果集的可達性保持圖并行計算

謝 羿（沈陽黎明航空發動機（集團）有限責任公司，遼寧 沈陽 110043）

?

基于BFS結果集的可達性保持圖并行計算

謝 羿
（沈陽黎明航空發動機（集團）有限責任公司，遼寧 沈陽 110043）

摘 要：傳統計算可達性保持圖的方法通常基于單機模式，針對小規模數據集進行計算。在處理大規模圖數據以及大量中間數據時，傳統方法將面臨內存容量和計算速度的瓶頸問題。為了解決上述問題，本文提出了基于BFS結果集的可達性保持圖并行計算方法。

關鍵詞：圖數據；可達；MapReduce；并行化；保持圖

0 引言

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

1 基于BFS結果集的可達性保持圖并行計算

1.1 基于BFS結果集的SCC并行查找算法

定理1：強連通分量內的任意兩頂點相互可達。

根據定理1，我們可以推出：對于某一強連通分量SCC內的任意一個頂點v，SCC中除v之外的其他頂點既包含于v的向后BFS結果集N-，又包含于v的向前BFS結果集N+。本文不考慮單一頂點作為強連通分量進行處理，對于可達性等價類的處理同樣也不考慮將單一頂點作為等價類處理。基于BFS結果集的SCC查找算法如下：

（1）輸入每個頂點v的向后BFS結果集N-和向前BFS結果集N+；

（2）對同一個頂點v，求temp=N-（v）∩N+（v）；

（3）如果|temp|＞0，則SCC= temp∪｛v｝，輸出SCC；否則，返回步驟1，計算下一個頂點。

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

1.2 基于標簽傳遞更新的SCC壓縮算法

壓縮強連通分量后，為不影響圖中各頂點與強連通分量之間的可達性，我們提出了基于標簽傳遞更新的強連通分量壓縮算法。

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

圖1標簽傳遞更新SCC

需要注意的是，原始圖中的SCC將被表示為超點（本體點），傳遞更新后并不影響圖中其他頂點到超點的可達性關系，因此滿足可達性等價條件。標簽傳遞更新SCC后獲得的壓縮圖為可達性保持圖。基于標簽傳遞更新的SCC壓縮算法描述如下：

（1）選取SCC傳遞標簽；因為SCC內的頂點已經排序，所以選擇標簽值最小的點（本體點）作為標簽傳遞起始點。

（2）對屬于同一個SCC的其他所有頂點，傳遞更新其標簽為本體點標簽；同一個SCC內的各頂點之間的相關邊將轉換為自指邊。超點（本體點）將繼承原SCC與外部相關聯的邊。

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

（4）輸出更新圖。

2 仿真實驗和分析

實驗使用6臺P C機搭建的基于Hadoop2.4.0版本的計算集群。其中1臺作為Master節點，另外5臺作為Slave節點。

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

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

從表1可以看出，各數據集在標簽傳遞更新SCC后所獲得的可達性保持圖從整體上達到了較好的壓縮效果。在壓縮更新可達性等價類后獲得的可達性保持圖的規模進一步減小。對于同一類型的網絡圖，如p2p網絡，可達性等價類壓縮更新方法可將可達性保持圖的壓縮比平均降低21個百分點。

查詢性能分析：本組實驗通過對原始圖和可達性保持圖中的所有頂點分別進行BFS遍歷來對比在兩種圖數據上的查詢性能。

如圖2所示，在可達性保持圖上的查詢時間明顯少于在原始圖上的查詢時間，進一步證明了本文可達性保持圖的有效性。

加速比實驗分析：加速比可以作為衡量并行計算相對于串行計算性能提升的指標。加速比越大說明并行計算效率越好。

由圖3可以看出，隨著計算節點的增加，測試集的加速比逐漸增大。但由于計算節點數的增加導致節點間的數據傳輸量增加，會產生額外的網絡傳輸時間，因此加速比的增長趨勢逐漸平緩。

圖2查詢性能對比

圖3加速比實驗

結語

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

參考文獻

［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.陸鑫達，譯.并行程序設計［M］. 北京：機械工業出版社，2002.

中圖分類號：TP301

文獻標識碼：A