[發明專利]一種圖算法友善的強連通圖劃分方法

有效

• 申請號: 201710323569.5
• 申請日: 2017-05-10
• 公開（公告）號: CN107193899B
• 公開（公告）日: 2019-09-13
• 發明（設計）人: 石宣化;邵志遠;梅珍杰;金海
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 趙偉;李智

本發明公開了一種圖算法友善的強連通圖劃分方法，包括以下步驟：將圖數據分解成若干個集合；利用多源寬度優先搜索算法將大小超過給定閾值的集合進一步劃分成多個搜索樹；利用啟發式算法將搜索樹組裝成多個子圖；本發明提供的強連通圖劃分方法可將強連通圖劃分成多個子圖，而且與其他以割邊即子圖之間的邊最小化、子圖大小均衡為目標的現有hash或METIS劃分方法均不同，在劃分強連通圖時考慮了邊的方向和圖數據的結構使得劃分后的子圖內部連通度較好、子圖大小相對均衡，從而能有效提高圖算法對其處理時的效率，解決在內存大小受限的限定條件下如何將大型強連通圖劃分成多個大小大致相同、連通度較好的子圖的問題。

技術領域

本發明涉及大數據處理技術領域，更具體地，涉及一種圖算法友善的強連通圖劃分方法。

背景技術

隨著大數據時代的來臨，圖數據的規模快速增長并迅速超過了普通計算機的內存容量，為了對大規模圖數據進行處理，研究人員提出了許多圖劃分方法將大規模圖數據首先劃分成若干個子圖，使得每個子圖能夠裝進內存，然后再依次將每個子圖從磁盤載入內存并在其上運行圖算法(這種處理方式稱為核外圖處理方式)。在此背景下，如何劃分子圖使得在核外環境下圖算法能夠在圖數據上高效運行，是一個亟待解決的問題。

現有的圖劃分方法有很多，比如hash劃分方法和基于多層圖粗化的METIS劃分方法等。Hash劃分方法根據需要劃分的子圖數目，按照對每個頂點編號取模的結果將其分配到相應的子圖中，這種方法可使得子圖大小均衡(即每個子圖中頂點的數量相同)，但完全忽略了頂點之間存在的相鄰關系和圖算法的具體特點(比如同一個頂點在某些圖算法執行過程中狀態變化頻繁，而在其他圖算法執行中狀態變化很少)。

METIS劃分方法包括粗化、劃分、細化三個階段。在粗化階段，采用啟發函數通過多輪粗化將多個頂點融合成一個頂點，使得圖規模迅速減小并將縮小后的圖作為第二階段的輸入。在劃分階段，采用經典劃分方法(比如Kernighan-Lin方法)將粗化后的圖進一步劃分成多個子圖。在細化階段，根據第二階段的劃分結果，將粗化圖中的頂點逐步還原為原始圖中的頂點。METIS針對無向圖往往能取得較好的效果(比如子圖之間的割邊數目較小、各個子圖的大小比較均衡)，但缺點也很明顯：(1)在劃分之前需要將圖數據完全載入內存并在運行過程中占用大量內存，當現實世界圖規模越來越大時，這種方式對于有限的內存容量來說是不可接受的；(2)對有向圖進行劃分之前，需要將其轉換成無向圖，這導致有向圖中邊的方向信息丟失。

還有一些劃分方法采用寬度優先搜索來劃分子圖，但這些劃分方法通常從圖數據中隨機選取頂點作為寬度優先搜索的起始點，而且最后僅僅根據搜索樹大小來組裝子圖，這種方法忽視了圖算法的具體特點和圖結構的關系，造成圖算法和圖劃分方法不適應并使得后續圖算法在子圖上運行時遇到消息傳播緩慢、頂點狀態變化頻繁等問題。

總體而言，現有的圖劃分方法存在以下不足：(1)對有向圖劃分時沒有考慮邊的方向信息；(2)劃分時沒有考慮現實世界圖中巨型強連通分量的存在對圖算法性能的影響；(3)劃分時沒有考慮不同類型的圖算法所具有不同特點對圖數據中頂點狀態變化的影響。

弱連通分量是指無向圖中的一個子圖(即頂點和邊的集合)，該子圖中任意一個頂點都可通過無向邊組成的路徑到達子圖中的其他頂點。有向圖可通過忽略邊的方向來找對應的弱連通分量。常用的弱連通分量尋找算法是基于最小標簽傳播實現的，即每個頂點將自己的標簽發送給相鄰頂點，并從收到的標簽中選擇最小的作為自己的標簽，算法多次運行直到圖數據中所有頂點的標簽不再變化為止。

強連通圖(即強連通分量)是指有向圖中的一個子圖，該子圖中任意一個頂點都可以通過有向邊組成的路徑到達其他頂點。在現實世界的圖數據(簡稱為現實世界圖)中往往存在很多的強連通分量，這些強連通分量中常有一個巨型的強連通分量，對于社交網絡圖而言，該巨型強連通分量的大小往往占整個圖數據規模的80％左右，剩下的絕大部分都是小型強連通分量。由強連通分量的定義可知任意兩個強連通分量之間邊的方向都是單向的。

發明內容