1.本發明涉及大數據處理技術領域，具體涉及一種大規模圖數據的均衡劃分方法。
背景技術：
2.圖結構可以描述事物之間的關系，比如網頁鏈接圖，社交網絡圖，城市交通圖等等。圖計算可以挖掘圖中的有用信息，從而在學術界和工業界有著廣泛的研究，比如，，等等。然而隨著互聯網的高速發展，圖規模也越來越大，比如很多網頁鏈接圖包含數十億節點，數千億條邊，原始圖數據可達tb量級，采用單機處理這些圖數據效率非常低。因此，常常采用分布式圖處理系統處理超大規模圖數據。
3.在分布式場景下，首先需要將大圖劃分為多個子圖，并將每個子圖加載到不同的機器上進行計算，并采用塊同步模型(the bulk model，bsp)協調計算任務的執行。塊同步模型將整體任務分為多輪迭代，每一輪每臺機器并行地進行當前子圖相關的計算，然后將計算中間結果發送到對應機器上。當所有機器都完成計算和通信任務時，才會開始下一輪的計算。因此，計算和通信的效率會極大的影響圖應用的處理效率。而圖劃分也極大影響計算和通信的效率。其中圖劃分的均衡性(包括節點均衡性和邊的均衡性)會影響計算的負載均衡；而劃分子圖間跨節點邊數量大小會影響通信量大小。因此為了提高分布式圖計算的效率，需要保證劃分的均衡性，并盡可能地減小跨子圖邊地數量。
4.而當前的劃分算法大多采用-的劃分方式，即每個節點和他相關聯的邊會被劃分到同一個子圖中。這些算法大致可以分為兩類，一類稱為離線劃分算法( )，這類算法需要將整個圖加載到內存中，并多次遍歷整個圖，以完成劃分，比如mgp( graph )、-based graph 、label -based graph 。雖然他們劃分所產生的跨節點邊較少，但是其劃分開銷過大，并且只能保證節點的劃分均衡，因此不適合超大規模圖劃分。
5.另一類稱為基于流的劃分算法，這類算法按照節點流的順序依次決定將該節點加載到某子圖中，比如chunk-based graph 、ldg、、hash等等。這些劃分算法只需按照節點順序加載一遍圖數據，因此劃分開銷很小，并且某些啟發式的算法比如ldg和能夠實現和離線劃分算法相似的劃分性能，但是通常他們也只能實現一個維度的均衡劃分，比如chunk-based graph ，ldg，等；或者劃分時會產生比較多的跨子圖邊，比如hash。
技術實現要素：
6.為解決上述技術問題，本發明提供一種大規模圖數據的均衡劃分方法，保證劃分子圖節點和邊同時達到均衡條件下，盡可能地降低跨子圖邊的數量，以支持高效的分布式圖計算。
7.為解決上述技術問題，本發明采用如下技術方案：
8.一種大規模圖數據的均衡劃分方法，包括以下步驟：
9.第一步：圖數據預處理
10.圖數據的初始化：將原始圖數據中每個節點都指定一個從0開始的節點id，每一個節點id唯一代表一個節點，并將完成后的圖數據存儲成csr格式；
11.劃分的初始化：將圖數據劃分為2p個子圖，并為每個子圖都分配一個集合，用以存放劃分到該子圖中的節點，每個集合初始化為空集。
12.第二步：圖數據的劃分
13.對于預處理后的圖數據，按照節點id的順序，從0開始依次讀取各個節點的信息(也可以不按照順序讀取節點信息)，包括該節點以及該節點對應的出邊；然后對每個子圖計算一個值s(v，gi)，并將節點v劃分到s(v，gi)值最大的子圖中，如果有多個子圖s(v，gi)值相等，且為最大，則從中隨機選擇一個子圖，并將節點v劃分到該子圖中；s(v，gi)的設計會較大地影響劃分均衡性以及跨子圖邊數量，本專利中s(v，gi)定義如下：
14.s(v，gi)＝|vi∩n(v)|-αγ|wi|
γ
；
15.等式右邊的第一項，vi表示已經劃分到子圖i的節點集合，n(v)表示節點v的出邊鄰居集合，|vi∩n(v)|表示節點v與子圖i的公共鄰居數，這個值越大表明將節點v劃分到子圖i中時跨子圖邊的數量越?。坏仁接疫叺牡诙検且粋€懲罰項，其中αγ是兩個常數，通常都設置為1.5，wi表示均衡性指標，其值越大，s(v，gi)越小，越有可能將節點劃分到其他wi更小的子圖，從而保證了劃分過程中各個子圖wi的均衡性。wi定義如下：
[0016][0017]
其中c是一個范圍在0到1之間的常數，用以控制|vi|和|ei|的權重，默認設置為0.5，表示同等地考慮節點均衡和邊均衡，ei表示子圖i的邊的集合，表示圖的平均度。
[0018]
第三步：子圖組合策略
[0019]
對于第二步劃分得到的子圖，通過組合的方式，將2個子圖組合為一個組合子圖，從而增加組合子圖的均衡性。對2p個子圖按照節點數量(或者邊數量)排序，并將具有最大節點數量的子圖與具有最小節點數量子圖組合在一起形成組合子圖(或者將具有最大邊數量子圖與具有最小邊數量子圖組合在一起)，在剩下的子圖中重復以上組合過程，直到所有子圖都組合形成組合子圖。
[0020]
第四步：多層組合策略
[0021]
經過一次組合仍然可能是不均衡的，因此采用多層組合方式，對均衡性較差的組合子圖，在下一輪進行更細粒度的劃分與組合。具體來說，在第一輪的劃分與組合過程與第二步、第三步相同，依次檢查每個組合子圖節點和邊數量是否均達到均衡，這里均衡的標準是：||vi|-|v
avg
||/|v
avg
|＜0.02、||ei|-|e
avg
||/|e
avg
|＜0.02。這里的|v
avg
|和|e
avg
|表示每個組合子圖的平均節點數和平均邊數。如果節點和邊都達到均衡，則將該組合子圖作為最終的劃分子圖，如果節點和邊有一個不均衡，則將該組合子圖所有節點放在下一輪進行更細粒度的劃分。對于第j輪，假設上一輪有n
個組合子圖不滿足均衡性條件，則將這些組合子圖的節點按照第二步的劃分策略劃分為2j×
個子圖，并按照同樣的組合策略，進行j次組合，得到n
個組合子圖，最后對n
個組合子圖進行均衡性檢查，不滿足條件的進入下一輪劃分。按照此過程進行，直到n
的值小于或等于1或者達到一定的迭代次數。
[0022]
與現有技術相比，本發明的有益技術效果是：
[0023]
本發明可以實現節點和邊兩個維度均衡的同時，跨節點邊數量也比較小。因此在分布式圖計算系統中，采用本發明的圖劃分方法能極大提高計算的均衡性的同時減小通信開銷。與現有圖劃分方法想比較，在執行圖算法時，可以減少5％到70％的計算時間。
附圖說明
[0024]
圖1為本發明一種大規模圖數據的均衡劃分方法的操作流程示意圖；
[0025]
圖2為數據集劃分過程中的組合策略示意圖；
[0026]
圖3為多層組合策略示意圖。
具體實施方式
[0027]
下面結合附圖通過一個具體實施例對本發明的大規模圖數據的均衡劃分方法作進一步的詳細說明。此處所描述的具體實施例僅用以解釋本發明，不用于限定本發明。
[0028]
本實施例通過劃分數據集(包含4139萬個節點，14.8億條邊)，用以具體闡述本發明步驟。
[0029]
附圖1是本實施例中大規模圖數據的均衡劃分方法的操作流程示意圖。
[0030]
第一步：圖數據預處理
[0031]
圖數據的初始化：將數據集中每個節點都指定一個從0開始的節點id，每一個節點id唯一代表一個節點，并將完成后的圖數據存儲成csr格式。
[0032]
劃分的初始化：假設需要劃分為4個組合子圖，則p設置為4，并為每個子圖分配一個集合，用以存放劃分到該子圖的節點以及對應的邊，初始時為空集。
[0033]
第二步：圖數據的劃分
[0034]
針對第一步存儲為csr格式的數據集，從節點id為0的節點開始，首先讀取該節點的所有出邊鄰居集合，記為n(v)，然后根據公式(1)和公式(2)對每個子圖計算s(v,gi)：
[0035]
s(v,gi)＝|vi∩n(v)|-αγ|wi|
γ
??
(1)；
[0036][0037]
然后將該節點以及其對應的出邊鄰居劃分到s(v,gi)值最大的子圖中，并加入到該子圖所對應的集合中。如果多個子圖s(v,gi)值相等且為最大，則從中隨機選擇一個子圖，將節點劃分到該子圖中，比如，對于節點id為0的節點，由于vi和ei初始都是空集，因此所有子圖的s(v,gi)值都是0，此時隨機選擇一個子圖，比如子圖1，將節點0加入到子圖1中。重復以上過程，直到所有節點都完成劃分。
[0038]
第三步：子圖的組合
[0039]
根據第二步的結果，可以計算每個子圖的節點數和邊數，然后對這些子圖按照節點數或者邊數排序。然后依次將最大節點數的子圖與最小節點數的子圖組合在一起作為一個組合子圖，將這兩個子圖從排序的子圖中剔除。重復以上過程，直到所有子圖都組合完畢。如附圖2所示，在劃分圖數據為4個組合子圖時，首先按照第二步劃分為8個小的子圖，節點數分別為：497萬、742萬、347萬、414萬、501萬、516萬589萬、532萬，邊數分別為：1.92億、1.05億、2.46億、2.22億、1.91億、1.85億、1.59億、1.79億。此時節點和邊都是不均
衡的。但是如果按照節點數量的順序進行排序，然后按照排序后的子圖順序將節點數最大子圖與節點數最小子圖兩兩組合，即子圖2與子圖1組合；子圖3與子圖6組合；子圖0與子圖7組合；子圖4與子圖5組合。此時得到四個組合子圖節點數分別為1089萬、1003萬、1029萬和1017萬；邊數為3.51億、3.81億、3.71億和3.76億。組合子圖的均衡性大大提高。
[0040]
第四步：多層組合策略
[0041]
只是進行一次組合不足以達到節點和邊同時均衡。本發明采用多層組合策略，對均衡性較差的子圖，在下一輪進行對這些子圖的節點更細粒度的劃分和組合。假設當前在第j輪，此時還剩下n
個均衡性較差的子圖沒有劃分。首先按照第二步劃分為2j×
個小的子圖，然后根據第三步，進行j次組合，得到n
個組合子圖。最后對每個組合子圖進行均衡性檢查大規模圖數據的分布式處理，并將不均衡的組合子圖的節點在下一輪進行更細粒度的劃分。如附圖3所示，在第一輪時，n
的值等于劃分子圖數n，因此劃分為2
×
n個小的子圖，然后經過一次組合得到n個組合子圖，然后對每個組合子圖檢測他們的均衡性，此時只有一個組合子圖滿足條件。于是，剩下的n-1個組合子圖進入第二輪，此時需要劃分為22×
(n-1)個小的子圖，并經過兩次排序組合，得到n-1個組合子圖，并檢查每個組合子圖的均衡性，將不均衡的組合子圖對應的節點放入下一輪劃分，重復以上過程直到所有組合子圖都完成劃分或者達到一定劃分層數。
[0042]
圖3中，第一層代表第一輪劃分和組合，第二層代表第二輪劃分和組合。
[0043]
對于本領域技術人員而言，顯然本發明不限于上述示范性實施例的細節，而且在不背離本發明的精神或基本特征的情況下，能夠以其他的具體形式實現本發明。因此無論從哪一點來看，均應將實施例看作是示范性的，而且是非限制性的，本發明的范圍由所附權利要求而不是上述說明限定，因此旨在將落在權利要求的等同要件的含義和范圍內的所有變化囊括在本發明內，不應將權利要求中的任何附圖標記視為限制所涉及的權利要求。
[0044]
此外，應當理解，雖然本說明書按照實施方式加以描述，但并非每個實施方式僅包含一個獨立技術方案，說明書的這種敘述方式僅僅是為了清楚起見，本領域技術人員應當將說明書作為一個整體，各實施例中的技術方案也可以經適當組合，形成本領域技術人員可以理解的其他實施方式。
技術特征：
1.一種大規模圖數據的均衡劃分方法，包括以下步驟：步驟一，將圖數據劃分為2p個子圖；步驟二：劃分每個節點時，對各子圖計算一個值s(v,g
i
)：s(v，g
i
)＝|v
i
∩n(v)|-αγ|w
i
|
γ
；將節點v劃分到s(v,g
i
)值最大的子圖中；其中g
i
表示子圖i，v
i
表示已經劃分到子圖i的節點集合，n(v)表示節點v的出邊鄰居集合，|v
i
∩n(v)|表示節點v與子圖i的公共鄰居數，αγ是兩個常數，w
i
表示均衡性指標；步驟三：對各子圖按照子圖內的節點數或者邊數進行排序，按照節點數排序時，實施過程a，在剩下的子圖中重復過程a直至所有子圖完成組合；按照邊數排序時，實施過程b，在剩下的子圖中重復過程b直至所有子圖完成組合；得到p個組合子圖；過程a：將具有最大節點數的子圖和具有最小節點數的子圖組合為組合子圖；過程b：將具有最大邊數的子圖和具有最小邊數的子圖組合為組合子圖；步驟四：計算每個組合子圖的均衡性，對均衡性未達到均衡性判斷標準的組合子圖的節點，進行多輪劃分和組合：第j(j≥1)輪中，剩余n
個均衡性未達到均衡性判斷標準的組合子圖大規模圖數據的分布式處理，則通過步驟二將未達到均衡性判斷標準的組合子圖的節點劃分為2
j
×
n
個子圖，然后通過步驟三，進行j次組合得到n
個組合子圖；直至每個組合子圖的均衡性達到均衡性判斷標準。2.根據權利要求1所述的大規模圖數據的均衡劃分方法，其特征在于：步驟二中，如果有多個子圖s(v,g
i
)值相等，且為最大，則從中隨機選擇一個子圖，并將節點v劃分到該子圖中。3.根據權利要求1所述的大規模圖數據的均衡劃分方法，其特征在于：均衡性指標其中c是一個范圍在0到1之間的常數，用以控制|v
i
|和|e
i
|的權重，e
i
表示子圖u邊的集合，表示子圖的平均度。4.根據權利要求1所述的大規模圖數據的均衡劃分方法，其特征在于：步驟四中，步驟四中，停止劃分和組合的判斷標準還有：j＝5或者n
≤1。5.根據權利要求1所述的大規模圖數據的均衡劃分方法，其特征在于：組合子圖均衡性判斷標準包括節點數均衡性判斷標準：||v
i
|-|v
avg
||/|v
avg
|<0.02，以及邊數均衡性判斷標準：||e
i
|-|e
avg
||/|e
avg
|＜0.02；其中|v
avg
|表示每個組合子圖的平均節點數，e
i
表示組合子圖i的邊的集合，|e
avg
|表示每個組合子圖的平均節點數；均衡性達到均衡性判斷標準是指，組合子圖的節點和邊均達到均衡。
技術總結
本發明涉及大數據處理技術領域，公開了一種大規模圖數據的均衡劃分方法，通過多層劃分和組合的方式，能夠實現節點和邊兩個維度均衡，同時跨節點邊數量也比較小，因此在分布式圖計算系統中，采用本發明的圖劃分方法能提高計算的均衡性，并減小通信開銷。并減小通信開銷。并減小通信開銷。
技術研發人員：李永坤 林帥 許胤龍
受保護的技術使用者：中國科學技術大學
技術研發日：2022.09.26
技術公布日：2023/1/11