一種網絡圖分割方法及系統與流程
2023-05-04 21:54:31 2
本發明涉及分布式計算機領域，特別是涉及一種網絡圖分割方法及系統。
背景技術：
海量社交網絡數據中蘊含著豐富的信息，圖論是挖掘這些信息的重要方法之一。面對日益增多的圖數據，分布式計算成為處理大規模網絡圖數據的有效手段。在分布式圖計算中，通信所消耗的時間佔有很大的比例，通過圖分割方法的設計可以有效地降低通信量並實現負載均衡，從而提高分布式圖計算的效率。
現有的網絡圖分割方法主要考慮如何降低全圖通信量的問題。目前主要的圖分割方法有多層圖劃分方法，該方法的基本原理是先將圖粗化為多個較小的子圖，再分別將每個子圖分割成k個部分，最後將每一小塊映射到全圖得到較為優化的k個分割圖。
以上圖分割方法相比於全圖通信雖然可以在一定程度上提高分布式圖方法執行效率，但是大多數實驗中發現通信負載過重的節點會導致在該節點運行的程序因網絡擁堵而被阻塞，最終通信負載過重的節點會嚴重拖延整個任務的執行時間。
技術實現要素：
本發明的目的是提供一種網絡圖分割方法及系統，以解決由於通信負載不均衡導致運行程序因網絡擁堵被阻塞，嚴重拖延整個任務的執行時間的問題，提高整個任務的執行效率。
為實現上述目的，本發明提供了如下方案：
一種網絡圖分割方法，所述方法包括：
隨機將n類標籤均勻分配給初始網絡圖中的所有頂點，其中n為大於2的整數；對於所述初始網絡圖中的任意頂點o、頂點o的鄰接點p，當所述頂點o與所述鄰接點p的標籤不同時，所述頂點o與所述鄰接點p之間通過通信邊通信；
隨機選取m個頂點作為起始頂點，其中m為大於0的整數；
對於m個頂點中的任一頂點q，判斷是否存在滿足交換條件的頂點q的鄰接點，得到第一判斷結果；所述滿足交換條件為兩個頂點的標籤交換後，形成的網絡圖的全圖通信量降低；
當所述第一判斷結果表示存在滿足交換條件的所述頂點q的鄰接點時，確定與所述頂點q進行標籤交換的一個鄰接點r；
將所述頂點q的標籤與所述鄰接點r的標籤交換，得到第一網絡圖；所述第一網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
完成一次迭代，判斷是否有滿足交換條件的所述頂點q的鄰接點的鄰接點，進入下一次迭代；
當所述第一判斷結果表示不存在滿足交換條件的所述頂點q的鄰接點時，在所述初始網絡圖全圖範圍內隨機選取一個頂點s，判斷所述頂點q與所述頂點s是否滿足交換條件，得到第二判斷結果；
當所述第二判斷結果表示所述頂點q與所述頂點s滿足交換條件時，將所述頂點q的標籤與所述頂點s的標籤交換，得到第二網絡圖；所述第二網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
完成一次迭代，判斷是否存在滿足交換條件的所述頂點s的鄰接點，進入下一次迭代；
當所述第二判斷結果表示所述頂點q與所述頂點s不滿足交換條件時，完成一次迭代，返回「在所述初始網絡圖全圖範圍內隨機選取一個頂點」步驟，進入下一次迭代；
判斷是否滿足連續t次迭代的全圖通信量變化小於設定閾值，得到第三判斷結果；所述t為大於1的整數；
當所述第三判斷結果表示連續t次迭代的全圖通信量變化小於設定閾值時，迭代停止，獲得分割後的子圖；所述子圖中每一子圖由標籤相同的全部頂點組成。
可選的，所述隨機將n類標籤均勻分配給初始網絡圖中的所有頂點，具體包括：
使用哈希方法隨機將n類標籤均勻分配給初始網絡圖中的所有頂點。
可選的，所述判斷是否存在滿足交換條件的頂點q的鄰接點，得到第一判斷結果，具體包括：
計算所述初始網絡圖的全圖通信量；
獲得所述頂點q的所有鄰接點；
對於任一所述頂點q的鄰接點u，將所述鄰接點u的標籤與所述頂點q的標籤交換，形成新的網絡圖；
計算所述新的網絡圖的全圖通信量；
判斷所述新的網絡圖的全圖通信量是否小於所述初始網絡圖的全圖通信量，得到第四判斷結果；
當所述第四判斷結果表示所述新的網絡圖的全圖通信量小於所述初始網絡圖的全圖通信量時，確定所述鄰接點u為滿足條件的所述頂點q的鄰接點。
可選的，所述當所述第一判斷結果表示存在滿足交換條件的所述頂點q的鄰接點時，確定與所述頂點q進行標籤交換的鄰接點r，具體包括：
獲取所有滿足交換條件的所述頂點q的鄰接點；
計算所有的所述頂點q的鄰接點的標籤與所述頂點q的標籤交換後的第一通信量下降值；所述第一通信量為與所述頂點q相連的通信邊和與所述頂點q的鄰接點相連的通信邊之和；
將所述第一通信量下降值按從大到小的順序排序；
將前k個第一通信量下降值對應的鄰接點確定為待定交換點；
計算所述待定交換點中每個鄰接點的標籤與所述頂點q的標籤交換前後的第二通信量差異值；所述第二通信量為所述頂點q所在的子圖與所述鄰接點所在的子圖之間的通信量；
將所述第二通信量差異值中最小差異值對應的鄰接點確定為與所述頂點q進行標籤交換的鄰接點r。
可選的，所述計算所有的所述頂點q的鄰接點的標籤與所述頂點q的標籤交換後的第一通信量下降值，具體包括：
利用公式delte＝|nq′(lq)|+|nq(lq′)|-(|nq′(lq′)|+|nq(lq)|)計算所述第一通信量下降值delte，其中|nq′(lq)|為頂點q′的鄰接點中標籤為lq的頂點的數量，|nq(lq′)|為頂點q的鄰接點中標籤為lq′的頂點的數量，|nq′(lq′)|為頂點q′的鄰接點中標籤為lq′的頂點的數量，|nq(lq)|為頂點q的鄰接點中標籤為lq的頂點的數量。
可選的，所述計算所述待定交換點中每個鄰接點的標籤與所述頂點q的標籤交換前後的第二通信量差異值，具體包括：
利用deltc＝|2(|nq|-|nq′|)-|nq(lq′)|+|nq′(lq′)|-|nq(lq)|+|nq′(lq)||公式計算所述第二通信量差異值，其中|nq|為頂點q的所有鄰接點的數量，|nq′|為頂點q′的所有鄰接點的數量，|nq′(lq)|為頂點q′的鄰接點中標籤為lq的頂點的數量，|nq(lq′)|為頂點q的鄰接點中標籤為lq′的頂點的數量，|nq′(lq′)|為頂點q′的鄰接點中標籤為lq′的頂點的數量，|nq(lq)|為頂點q的鄰接點中標籤為lq的頂點的數量。
可選的，所述n為4和/或t為1000。
一種網絡圖分割系統，所述系統包括：
標籤分配模塊，用於隨機將n類標籤均勻分配給初始網絡圖中的所有頂點，其中n為大於2的整數；對於所述初始網絡圖中的任意頂點o、頂點o的鄰接點p，當所述頂點o與所述鄰接點p的標籤不同時，所述頂點o與所述鄰接點p之間通過通信邊通信；
起始頂點選取模塊，用於隨機選取m個頂點作為起始頂點，其中m為大於0的整數；
第一判斷模塊，用於對於m個頂點中的任一頂點q，判斷是否存在滿足交換條件的頂點q的鄰接點，得到第一判斷結果；所述滿足交換條件為兩個頂點的標籤交換後，形成的網絡圖的全圖通信量降低；
鄰接點確定模塊，用於當所述第一判斷結果表示存在滿足交換條件的所述頂點q的鄰接點時，確定與所述頂點q進行標籤交換的一個鄰接點r；
標籤交換模塊，用於將所述頂點q的標籤與所述鄰接點r的標籤交換，得到第一網絡圖；所述第一網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
第二判斷模塊，用於當所述第一判斷結果表示不存在滿足交換條件的所述頂點q的鄰接點時，在所述初始網絡圖全圖範圍內隨機選取一個頂點s，判斷所述頂點q與所述頂點s是否滿足交換條件，得到第二判斷結果；
所述標籤交換模塊，還用於當所述第二判斷結果表示所述頂點q與所述頂點s滿足交換條件時，將所述頂點q的標籤與所述頂點s的標籤交換，得到第二網絡圖；所述第二網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
第三判斷模塊，用於判斷是否滿足連續t次迭代的全圖通信量變化小於設定閾值，得到第三判斷結果；所述t為大於1的整數；
分割後的子圖獲取模塊，用於當所述第三判斷結果表示連續t次迭代的全圖通信量變化小於設定閾值時，迭代停止，獲得分割後的子圖；所述子圖中每一子圖由標籤相同的頂點組成。
可選的，所述第一判斷模塊，具體包括：
全圖通信量計算單元，用於計算所述初始網絡圖的全圖通信量；
鄰接點第一獲取單元，用於獲得所述頂點q的所有鄰接點；
標籤交換單元，用於對於任一所述頂點q的鄰接點u，將所述鄰接點u的標籤與所述頂點q的標籤交換，形成新的網絡圖；
所述全圖通信量計算單元，還用於計算所述新的網絡圖的全圖通信量；
第四判斷單元，用於判斷所述新的網絡圖的全圖通信量是否小於所述初始網絡圖的全圖通信量，得到第四判斷結果；
鄰接點第一確定單元，用於當所述第四判斷結果表示所述新的網絡圖的全圖通信量小於所述初始網絡圖的全圖通信量時，確定所述鄰接點u為滿足條件的所述頂點q的鄰接點。
可選的，鄰接點確定模塊，具體包括：
鄰接點第二獲取單元，用於獲取所有滿足交換條件的所述頂點q的鄰接點；
第一通信量下降值計算單元，用於計算所有的所述頂點q的鄰接點的標籤與所述頂點q的標籤交換後的第一通信量下降值；所述第一通信量為與所述頂點q相連的通信邊和與所述頂點q的鄰接點相連的通信邊之和；
排序單元，用於將所述第一通信量下降值按從大到小的順序排序；
待定交換點確定單元，用於將前k個第一通信量下降值對應的鄰接點確定為待定交換點；
第二通信量差異值計算單元，用於計算所述待定交換點中每個鄰接點的標籤與所述頂點q的標籤交換前後的第二通信量差異值；所述第二通信量為所述頂點q所在的子圖與所述鄰接點所在的子圖之間的通信量；
鄰接點第二確定單元，用於將所述第二通信量差異值中最小差異值對應的鄰接點確定為與所述頂點q進行標籤交換的鄰接點r。
根據本發明提供的具體實施例，本發明公開了以下技術效果：
從通信負載均衡角度對社交網絡圖數據進行劃分，使用通信均衡標籤交換的方法，降低子圖與子圖之間的通信量，並且進行多次迭代，最終使得子圖與子圖之間的通信量達到較低的狀態，全圖通信量到達相對穩定的狀態，實現各個節點的通信負載均衡，即子圖與子圖之間通信均衡，從而提高計算系統資源利用率，減少計算消耗時間。
附圖說明
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。
圖1為本發明網絡圖分割方法的流程圖；
圖2為本發明網絡圖分割方法中圖分割示意圖，其中(a)為分割前全圖示意圖，(b)為分割後子圖示意圖，(c)為標籤交換後子圖示意圖；
圖3為本發明網絡圖分割系統的結構圖；
圖4為本發明的網絡圖分割方法與已有hash方法、metis方法進行網絡圖分割所得通信邊數量對比圖；
圖5本發明的網絡圖分割方法與已有hash方法、metis方法進行網絡圖分割所得通信邊分布情況對比圖；
圖6本發明的網絡圖分割方法與已有hash方法、metis方法運行pagerank算法的時間對比圖。
具體實施方式
下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面結合附圖和具體實施方式對本發明作進一步詳細的說明。
圖1為本發明網絡圖分割方法的流程圖。如圖1所示，所述方法包括：
步驟101：將多個標籤均勻分配給網絡圖中的所有頂點，標籤的類別大於2，例如可以為4類標籤，利用哈希方法隨機將標籤均勻的分配給所有頂點，，這可以保證整個圖中頂點的標籤是均勻分布的。首先對頂點的標籤數據進行初始化。利用隨機函數隨機產生四類標籤，對頂點的標籤數據賦值，使得各類標籤的頂點數量分布均衡。
用l表示每個頂點所隨機分配的一個標籤。lp為頂點p的標籤，具有相同標籤的頂點組成一個子圖。用np表示頂點p的鄰接點集合，並且np(l)表示頂點p的鄰接點中標籤為l的頂點集合，則np(l)＝{q|q∈np∧lp＝l}。當頂點p與其鄰接點的標籤不同時，則形成通信邊。
步驟102：確定起始頂點。隨機選取m個頂點作為起始頂點，其中m為大於0的整數；隨機選取多個起始頂點的目的是實現並行，提高方法的運行速度，如果只選擇一個起始頂點，即m＝1時，相當於一條線執行，當選擇多個起始頂點，即m＝2,3,4，……時，相當於多線並行執行，此時執行速度較快。具體實施時，可以根據實際情況，選取合適的m值。
步驟103：判斷是否存在滿足交換條件的鄰接點，如果是，執行步驟104，如果否，執行步驟106。對於多個起始頂點中的任一頂點q，判斷是否存在滿足交換條件的頂點q的鄰接點，得到第一判斷結果；所述滿足交換條件為兩個頂點的標籤交換後，形成的網絡圖的全圖通信量降低。默認每條邊所傳輸的數據量相同，那麼通信邊的數量可以近似的作為通信量大小。因此定義一個頂點的通信量就是與該頂點的標籤不同的鄰接點的數量，則全圖的通信量表示為各個頂點通信量的和：
具體的判斷過程為：
計算初始網絡圖的全圖通信量；
獲得所述頂點q的所有鄰接點；
對於任一所述頂點q的鄰接點u，將所述鄰接點u的標籤與所述頂點q的標籤交換，形成新的網絡圖；
計算所述新的網絡圖的全圖通信量；
判斷所述新的網絡圖的全圖通信量是否小於所述初始網絡圖的全圖通信量；
當所述新的網絡圖的全圖通信量小於所述初始網絡圖的全圖通信量時，確定所述鄰接點u為滿足條件的所述頂點q的鄰接點。
步驟104：確定與起始頂點交換的鄰接點。
獲取所有滿足交換條件的所述起始頂點的鄰接點；
計算所有鄰接點的標籤與所述起始點的標籤交換後的第一通信量下降值；所述第一通信量為與所述起始點相連的通信邊和與所述鄰接點相連的通信邊之和。當選取一系列頂點作為交換標籤候選對象之後，再從中選取一個最合適的頂點交換標籤。判斷哪些頂點需要交換標籤，需要比較兩個頂點交換標籤前後是否能夠降低它們的通信量，並且滿足限制條件。減小通信邊的數量，也就是最大化具有相同標籤的鄰接點的數量|nq(lq)|。假設頂點q′和q各自的標籤分別是lq′和lq,因此，第一通信量下降值為：
delte＝|nq′(lq)|+|nq(lq′)|-(|nq′(lq′)|+|nq(lq)|)，其中|nq′(lq)|為頂點q′的鄰接點中標籤為lq的頂點的數量，|nq(lq′)|為頂點q的鄰接點中標籤為lq′的頂點的數量，|nq′(lq′)|為頂點q′的鄰接點中標籤為lq′的頂點的數量，|nq(lq)|為頂點q的鄰接點中標籤為lq的頂點的數量；當delte的值大於零，則說明交換標籤後與頂點標籤相同的鄰接點數量增加了，也就是通信邊數量減少了，交換標籤會使通信邊邊的分布發生變化；
將所述第一通信量下降值按從大到小的順序排序；
將前k個第一通信量下降值對應的鄰接點確定為待定交換點；例如，k可以為10，則此時選取通信量下降的前10個頂點作為備選的交換頂點；
計算所述待定交換點中每個鄰接點的標籤與所述起始頂點的標籤交換前後的第二通信量差異值；所述第二通信量為所述起始頂點所在的子圖與所述鄰接點所在的子圖之間的通信量；定義任意兩個子圖分別為x和y，則子圖x中的任意一個頂點對子圖y的通信量表示為：|np|-|np(y)|,p∈x∧x,y∈l，因此，兩子圖之間通信量為：第二通信量差異值deltc＝|2(|nq|-|nq′|)-|nq(lq′)|+|nq′(lq′)|-|nq(lq)|+|nq′(lq)||，其中|nq|為頂點q的所有鄰接點的數量，|nq′|為頂點q′的所有鄰接點的數量，|nq′(lq)|為頂點q′的鄰接點中標籤為lq的頂點的數量，|nq(lq′)|為頂點q的鄰接點中標籤為lq′的頂點的數量，|nq′(lq′)|為頂點q′的鄰接點中標籤為lq′的頂點的數量，|nq(lq)|為頂點q的鄰接點中標籤為lq的頂點的數量；deltc的大小表示了兩頂點交換標籤後，各自子圖通信邊之間該變量的差異；
將所述第二通信量差異值中最小差異值對應的鄰接點確定為與所述起始點進行標籤交換的鄰接點。
步驟105：將鄰接點的標籤與起始頂點的標籤進行交換。得到新的網絡圖；新的網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信。此時完成一次迭代。
步驟106：全圖範圍內隨機選取一個頂點。本發明中，為了充分利用本地數據進行計算，提高算法的拓展性，在選擇標籤交換對象的時候，優先考慮頂點的鄰接頂點進行交換。但是經過實驗發現，僅僅把鄰接點作為交換的候選對象是不夠的，這種策略下執行出來的結果常常在達到滿意結果之前就結束計算了。針對這個問題，在尋找不到合適的鄰接點作為交換對象時，利用隨機函數在頂點id範圍內隨機產生id號，將該id號對應的頂點作為選取的頂點。
步驟107：判斷選取的頂點是否滿足標籤的交換條件。如果是，執行步驟108，如果否，完成一次迭代，返回步驟106，重新選取頂點，進入下一次迭代。
步驟108：選取的頂點的標籤與起始頂點的標籤進行交換。完成一次迭代。
步驟109：判斷是否滿足連續t次迭代的全圖通信量變化小於設定閾值，如果是，結束迭代，執行步驟1010，如果否，返回步驟102，繼續進行迭代。t為大於1的整數，例如t可以為500，可以為1000，設定閾值可以為70，可以為50。設定t與設定閾值的作用是限制迭代的條件，避免陷入無限次迭代。其中每一次迭代都會計算全圖通信量的變化，可以通過計算標籤交換前後的全圖通信量，進而求得全圖通信量變化；也可以只針對標籤交換的頂點，通過結合計算標籤交換頂點的通信量變換和兩子圖之間的通信量變化，進而求得全圖通信量變化；對於沒有發生標籤交換的迭代過程，可以直接設置此種情況的全圖通信量變化為0。
步驟1010：獲得分割後的子圖。
根據分割後的子圖結果將頂點標籤相同的頂點發送到指定的計算節點上。四類標籤代表有四個計算節點，將頂點按照各自標籤發送到指定的節點上參與計算。
本發明通過優化使全圖通信量e(g)最小，則能夠得到通信量最少的子圖分割結果。將通信邊均勻的分布於各個節點上，能有效的避免過快達到單節點的性能瓶頸，從而充分利用集群資源，提高方法的效率。為使全圖的通信量均勻的分布在各個子圖，則任意兩個子圖之間通信量應滿足如下關係：
為獲得通信量最少且各子圖通信均衡和子圖規模相同的分割結果，需要求得在上述公式的限制條件下，使得e(g)達到最小值得解：
圖2為本發明網絡圖分割方法中圖分割示意圖，其中(a)為分割前全圖示意圖，(b)為分割後子圖示意圖，(c)為標籤交換後子圖示意圖。如圖2所示，初始的網絡圖如(a)所示，將三類標籤(l1、l2、l3)隨機分配給所有頂點。具有相同標籤的頂點組成一個子圖，因此，全圖形成的子圖如圖(b)所示，分為3個子圖，其中標籤不同的兩個頂點之間通過通信邊通信，因此，圖(b)中包括5條通信邊。以頂點b的標籤與頂點d的標籤交換為例，圖(c)為標籤交換後形成的子圖，此時包括4條通信邊，顯然，降低了通信量。
圖3為本發明網絡圖分割系統的結構圖。如圖3所示，所述結構包括：
標籤分配模塊301，用於隨機將n類標籤均勻分配給初始網絡圖中的所有頂點，其中n為大於2的整數；對於所述初始網絡圖中的任意頂點o、頂點o的鄰接點p，當所述頂點o與所述鄰接點p的標籤不同時，所述頂點o與所述鄰接點p之間通過通信邊通信；
起始頂點選取模塊302，用於隨機選取m個頂點作為起始頂點，其中m為大於0的整數；
第一判斷模塊303，用於對於m個頂點中的任一頂點q，判斷是否存在滿足交換條件的頂點q的鄰接點，得到第一判斷結果；所述滿足交換條件為兩個頂點的標籤交換後，形成的網絡圖的全圖通信量降低；
鄰接點確定模塊304，用於當所述第一判斷結果表示存在滿足交換條件的所述頂點q的鄰接點時，確定與所述頂點q進行標籤交換的一個鄰接點r；
標籤交換模塊305，用於將所述頂點q的標籤與所述鄰接點r的標籤交換，得到第一網絡圖；所述第一網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
第二判斷模塊306，用於當所述第一判斷結果表示不存在滿足交換條件的所述頂點q的鄰接點時，在所述初始網絡圖全圖範圍內隨機選取一個頂點s，判斷所述頂點q與所述頂點s是否滿足交換條件，得到第二判斷結果；
所述標籤交換模塊305，還用於當所述第二判斷結果表示所述頂點q與所述頂點s滿足交換條件時，將所述頂點q的標籤與所述頂點s的標籤交換，得到第二網絡圖；所述第二網絡圖中任一頂點與鄰接點的標籤不同時，兩者之間通過通信邊通信；
第三判斷模塊307，用於判斷是否滿足連續t次迭代的全圖通信量變化小於設定閾值，得到第三判斷結果；所述t為大於1的整數；
分割後的子圖獲取模塊308，用於當所述第三判斷結果表示連續t次迭代的全圖通信量變化小於設定閾值時，迭代停止，獲得分割後的子圖；所述子圖中每一子圖由標籤相同的頂點組成。
採用本發明方法及系統的具體實驗過程：
1.數據說明：採用的數據集是史丹福大學開放的三個社交網絡數據集，這三個數據集具有明顯的冪律分布特徵，並且數據集大小依次增加。表1給出了數據集各項指標的詳細說明。如表1所示：
表1實驗數據信息
2.實施環境：使用的分布式圖計算框架是hadoop項目中的子項目hama，一個基於bsp大同步模型的大規模圖計算框架。將該框架部署於由5個伺服器組成的集群，其中單個伺服器的配置為6核英特爾xeon處理器，16g內存，2t存儲和千兆乙太網卡，作業系統為centos7，使用hadoop2.6版本搭建分布式環境，並配置一個hdfs的namenode和4個datanode，資源管理器設置為yarn。
3.操作步驟：
1)首先通過客戶端向hdfs中上傳社交網絡數據集，其中對數據集的分割方法分別設置為hash方法，metis方法和本發明分割方法；
2)將本發明的網絡圖分割方法的結果將頂點標籤相同的頂點發送到指定的計算節點上。四類標籤代表有四個計算節點，將頂點按照各自標籤發送到指定的節點上參與計算。
3)啟動hama的pagerank計算程序，運行10次pagerank程序，並統計pagerank程序使用各個方法分割結果運行的平均時間，其中運行時間越短，效率越高。
4.本發明性能分析：
圖4為本發明與已有hash方法、metis方法進行網絡圖分割所得通信邊數量對比圖；圖5本發明與已有hash方法、metis方法進行網絡圖分割所得通信邊分布情況對比圖；
在通信邊數量方面，圖4中可看出，本發明的社交網絡圖分割方法雖然通信邊數量比metis方法多，但是各節點通信邊數量差異小於metis方法，其在通信負載均衡性上的優勢遠遠高於metis方法。hash方法通信邊分布雖然均衡，但通信總量遠遠大於本文方法。圖5給出了三種方法通信邊分布情況對比圖。
為驗證結果對分布式圖方法的影響，最後進一步使用分割的結果進行pagerank算法計算。圖6本發明與已有hash方法、metis方法運行pagerank算法的時間對比圖。
從圖6可知，使用hash方法，pagerank執行時間最長。metis方法的結果能平均縮短15％到20％的運行時間，因為通信邊數量大大減少，所需數據大多從內存讀取，大大提高了計算效率。pagerank算法使用本發明網絡圖分割方法分割的小數據集結果進行運算，時間略長於metis的結果，但是仍在可接受範圍。但隨著數據集規模的增加，本發明社交網絡圖分割方法對比hash及metis方法，其結果分別縮短了29％和6％的pagerank運算時間，說明本發明方法在分割大規模社交網絡數據，提高分布式圖計算效率方面具有優勢。
本說明書中各個實施例採用遞進的方式描述，每個實施例重點說明的都是與其他實施例的不同之處，各個實施例之間相同相似部分互相參見即可。對於實施例公開的系統而言，由於其與實施例公開的方法相對應，所以描述的比較簡單，相關之處參見方法部分說明即可。
本文中應用了具體個例對本發明的原理及實施方式進行了闡述，以上實施例的說明只是用於幫助理解本發明的方法及其核心思想；同時，對於本領域的一般技術人員，依據本發明的思想，在具體實施方式及應用範圍上均會有改變之處。綜上所述，本說明書內容不應理解為對本發明的限制。