《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》是安徽奧里奧克科技股份有限公司於2016年8月29日申請的發明專利，該專利申請號為2016107806874，公布號為CN106330559A，專利公布日為2017年1月11日，發明人是趙衛、王莉莉。
《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》包括：步驟1，產生更新訊息；步驟2，傳遞訊息；步驟3，更新節點內部狀態信息。針對傳統單機算法在計算大規模網路拓撲特徵參數時效率較低的問題，該發明提出了一種網路拓撲特徵參數的單機算法向MapReduce計算框架並行移植的方法，克服了2016年8月之前單機算法並行移植到MapReduce時存在的問題，利用Hadoop計算平台實現了網路拓撲特徵參數的並行計算，提高了網路拓撲特徵參數的計算效率。
2020年7月17日，《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》獲得安徽省第七屆專利獎優秀獎。
（概述圖為《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》的摘要附圖）
基本介紹
- 中文名：基於MapReduce的複雜網路拓撲特徵參數計算方法和系統
- 公布號：CN106330559A
- 公布日：2017年1月11日
- 申請號：2016107806874
- 申請日：2016年8月29日
- 申請人：安徽奧里奧克科技股份有限公司
- 地址：安徽省合肥市高新區習友路與香樟大道交口深港產業園3棟B座B1-B4
- 發明人：趙衛、王莉莉
- 代理機構：上海漢聲智慧財產權代理有限公司
- 代理人：郭國中
- Int.Cl.：H04L12/24(2006.01)I
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
複雜網路：具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網路稱為複雜網路。包括現實中的WWW網路、Internet、社會關係網路、經濟網路、電力網路等。 網路拓撲特徵參數：由於網路結構複雜，研究者在刻畫複雜網路結構的統計特性上提出了許多概念和方法，稱之為網路的拓撲特徵參數。主要包括度、聚類係數、網路直徑、平均路徑長度、最大連通子圖大小、核數和介數等。
度：節點的度是指該節點擁有相鄰節點的數目。
聚類係數：節點的聚類係數定義為它所有相鄰節點之間連的數目占可能的最大連邊數目的比例，網路的聚集係數則是所有節點簇係數的平均值。
平均路徑長度和網路直徑：在網路中，兩點間的距離被定義為連線兩點的最短路所包含的邊的數目，所有節點對的距離的平均值稱作網路的平均路徑長度。所有節點對的距離的最大值稱作網路的直徑。
最大連通子圖大小：網路可能不是完全連通的，通常使用最大連通子圖大小來表示網路的連通性。
核數：描述網路層次性的參數，一個圖的k-核指反覆去掉小於或等於k的節點後所剩餘的子圖。若一個節點存在於k-核，而在（k+1）-核中被移除，那么此節點的核數為k，節點核中的最大值稱為網路的核數。
介數：節點的介數為網路中所有的最短路徑中經過該節點的數量比例。
2016年8月之前的研究中，計算網路的拓撲特徵參數大多是在單機條件下完成的。由於一些網路拓撲特徵參數算法的時間複雜度較高，傳統單機條件下的網路拓撲特徵參數計算方法在處理大規模網路拓撲數據時存在效率低、記憶體受限的問題。所以考慮使用Hadoop分散式計算平台來進行計算。
Hadoop的實現的MapReduce計算框架為設計分散式算法提供了簡單易懂的編程模型。截至2016年8月，利用Hadoop分散式平台計算網路拓撲特徵參數還沒有成熟的技術。由於分散式環境的數據存儲、數據處理和單機系統存在很大差異，導致傳統單機串列圖算法向MapReduce計算框架上移植時存在以下問題：
1.數據存儲和處理方式上不兼容
大量的計算拓撲特徵參數的算法都需要執行查找或修改鄰居節點信息的操作，單機算法中的圖結構以鄰接表或者鄰接矩陣的形式存儲在單機記憶體中，可以在常數時間內查找到鄰居節點的存儲位置並修改其狀態信息。但是在分散式環境中，每個節點信息是以單獨一條文本來存儲的，查找或修改鄰居節點信息都需要遍歷整個圖檔案，效率很低。
2.單機算法缺乏並行特性
單機算法在設計時並沒有考慮到並行特性，所以在單機上串列執行的算法並不一定能在分散式計算平台上高效的運行。例如對網路拓撲圖進行遍歷的過程，在單機算法中深度優先遍歷和寬度優先遍歷都是常用的算法。但是同一時刻，寬度優先遍歷可以並行訪問處於網路同一層的多個節點，而深度優先遍歷只能串列訪問一個節點，在當前節點未完成訪問時不能繼續訪問下一節點。所以寬度優先遍歷算法的並行性要優於深度優先遍歷，更適合運行在MapReduce框架中。
3.單機算法並行移植時會產生額外的開銷
MapReduce運行時需要執行啟動作業、任務調度、讀寫磁碟等操作，會產生額外的時間開銷。特別地，當圖算法中的疊代次數過多時，MapReduce框架需要連續啟動若干作業才可以完成圖的疊代處理，每個作業都會執行啟動作業、任務調度、讀寫磁碟等操作，尤其是相鄰作業之間通過分散式檔案系統交換全部數據，產生大量額外開銷，導致算法計算效率下降。
發明內容
專利目的
針對2016年8月之前技術中的缺陷，《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》的目的是提供一種基於MapReduce的複雜網路拓撲特徵參數計算方法。
技術方案
《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》採用基於訊息傳遞的算法並行化方法；
所述基於訊息傳遞的算法並行化方法，包括：
步驟1，產生更新訊息；
每個節點根據本節點的狀態信息計算生成更新訊息的內容，把鄰居節點作為訊息的目的節點，將更新訊息向目的節點傳送；
步驟2，傳遞訊息；
更新訊息按照目的節點被傳送給指定的節點；
步驟3，更新節點內部狀態信息；
目的節點收到若干條更新訊息，目的節點對這些更新訊息進行解析並更新目的節點內部狀態信息。
優選地，所述步驟1，具體為：
步驟1由MapReduce框架中的Map階段完成，Map階段的處理方法由用戶完成；
該Map階段負責處理每條存儲節點信息的文本記錄，根據需求產生更新訊息鍵/值對；其中，鍵是鄰居節點id，值是更新訊息的內容；
所述步驟2，具體為：
所述步驟2由MapReduce框架中的partitioner組件自動完成，partitioner組件默認根據hash算法把具有相同鍵的訊息鍵/值對和節點鍵/值對劃分到一起，使得更新訊息達到了傳遞的效果；
所述步驟3，具體為：
所述步驟3由MapReduce框架中的Reduce階段完成，Reduce階段負責接收上一階段傳遞的鍵/值對，把所有具有相同鍵的訊息鍵/值對和節點鍵/值對進行聚合，得到更新後的
節點鍵/值對並輸出；
Reduce階段的處理方法由用戶根據需求自定義完成的。
優選地，採用利用所述基於訊息傳遞的算法並行化方法實現的基於MapReduce的介數方法；
所述基於MapReduce的介數方法，包括：
步驟S1，所有節點選取自己做為源節點開始計算節點介數；
步驟S2，從源節點出發進行寬度優先遍歷；
步驟S3，回溯求解點對依賴度；
步驟S4，累加點對依賴度得到介數。
優選地，節點v的介數被定義為：
其中，B（v）表示節點v的介數，σst表示節點s和節點t之間的最短路徑條數，σst（v）表示節點s和節點t之間的最短路徑中經過節點v的條數；V表示網路節點的集合；
所述步驟2包括：
從所有源節點同時出發寬度優先遍歷其餘節點，當訪問到當前節點v時，根據下式：
計算節點v到源節點s的最短路徑的數目，並記錄下節點v的前驅節點Ps（v）；疊代遍歷過程，直到所有節點都被訪問到；
其中，σsv表示節點s到節點v的最短路徑數目，Ps（v）表示節點v以節點s為源的前驅節點，σsu表示節點s到節點u的最短路徑數目；
所述步驟3包括：
從距離源節點最遠一層的節點開始回溯，按照下式：
計算當前層中節點的前驅節點的點對依賴度；不停回溯計算前驅節點的點對依賴度，直到回到源節點，得到源節點對其他所有節點的依賴度；
其中，δs·（v）表示節點s對節點v的依賴度，稱為點對依賴度；
w，v表示網路中的節點；
σsw表示節點s到節點w的最短路徑數目；
δs·（w）表示節點s對節點w的依賴度；
所述步驟4包括：
根據如下公式：
將不同源節點對節點v的依賴度求和得到該節點v的介數。
優選地，所述步驟S2包括：
步驟S21，網路中每個節點維護著一個狀態記錄表，狀態記錄表中每條記錄包含當前已經訪問到的源節點id和相應的距離、最短路徑數目、前驅節點這四個欄位；
步驟S22，在Map階段所有節點都根據當前狀態表中的每條記錄構造更新訊息；更新訊息是以鍵/值對的形式處理，其中鍵是需要接受該更新訊息的目的節點的id，值中包含了目的節點需要的信息，與狀態記錄表中的記錄包含同樣的四個欄位；到源節點的距離等於本節點到源節點的距離加1，所述最短路徑數目即為本節點到源節點的最短路徑數目，前驅節點則為節點本身；
步驟S23，Map階段產生的鍵/值對將通過MapReduce框架進行自動劃分，最終相同鍵的鍵/值對被同一個Reduce函式接收，完成訊息傳遞的過程；
步驟S24，在Reduce階段，所有節點都會收到來自鄰居節點的若干條更新訊息；以訊息中的源節點為準在狀態記錄表中進行匹配，查找該源節點對相應的狀態記錄，並根據更新訊息中包含的信息進行狀態更新；
步驟S25，判斷所有源節點是否完成寬度遍歷，若沒有則跳轉到步驟S23繼續疊代，若完成了則進入步驟S3繼續執行。
根據本年發明提供的一種基於MapReduce的複雜網路拓撲特徵參數計算系統，包括基於訊息傳遞的算法並行化裝置；
所述基於訊息傳遞的算法並行化裝置，包括：
裝置M1，產生更新訊息；
每個節點根據本節點的狀態信息計算生成更新訊息的內容，把鄰居節點作為訊息的目的節點，將更新訊息向目的節點傳送；
裝置M2，傳遞訊息；
更新訊息按照目的節點被傳送給指定的節點；
裝置M3，更新節點內部狀態信息；
目的節點收到若干條更新訊息，目的節點對這些更新訊息進行解析並更新目的節點內部狀態信息。
優選地，所述裝置M1，具體為：
裝置M1在MapReduce框架中的Map階段被觸發執行，Map階段的處理方法由用戶完成；
該Map階段負責處理每條存儲節點信息的文本記錄，根據需求產生更新訊息鍵/值對；其中，鍵是鄰居節點id，值是更新訊息的內容；
所述裝置M2，具體為：
所述裝置M2在MapReduce框架中的partitioner組件被觸發執行，partitioner組件默認根據hash算法把具有相同鍵的訊息鍵/值對和節點鍵/值對劃分到一起，使得更新訊息達到了傳遞的效果；
所述裝置M3，具體為：
所述裝置M3在MapReduce框架中的Reduce階段被觸發執行，Reduce階段負責接收上一階段傳遞的鍵/值對，把所有具有相同鍵的訊息鍵/值對和節點鍵/值對進行聚合，得到更新後的節點鍵/值對並輸出；
Reduce階段的處理方法由用戶根據需求自定義完成的。
優選地，採用利用所述基於訊息傳遞的算法並行化裝置實現的基於MapReduce的介數裝置；
所述基於MapReduce的介數裝置，包括：
裝置MS1，令所有節點選取自己做為源節點開始計算節點介數；
裝置MS2，從源節點出發進行寬度優先遍歷；
裝置MS3，回溯求解點對依賴度；
裝置MS4，累加點對依賴度得到介數。
優選地，節點v的介數被定義為：
其中，B（v）表示節點v的介數，σst表示節點s和節點t之間的最短路徑條數，σst（v）表示節點s和節點t之間的最短路徑中經過節點v的條數；V表示網路節點的集合；
所述裝置M2具體為：
從所有源節點同時出發寬度優先遍歷其餘節點，當訪問到當前節點v時，根據下式：
計算節點v到源節點s的最短路徑的數目，並記錄下節點v的前驅節點Ps（v）；疊代遍歷過程，直到所有節點都被訪問到；
其中，σsv表示節點s到節點v的最短路徑數目，Ps（v）表示節點v以節點s為源的前驅節點，σsu表示節點s到節點u的最短路徑數目；
所述裝置M3具體為：
從距離源節點最遠一層的節點開始回溯，按照下式：
計算當前層中節點的前驅節點的點對依賴度；不停回溯計算前驅節點的點對依賴度，直到回到源節點，得到源節點對其他所有節點的依賴度；
其中，δs·（v）表示節點s對節點v的依賴度，稱為點對依賴度；
w，v表示網路中的節點；
σsw表示節點s到節點w的最短路徑數目；
δs·（w）表示節點s對節點w的依賴度；
所述裝置M4具體為：
根據如下公式：
將不同源節點對節點v的依賴度求和得到該節點v的介數。
優選地，所述裝置MS2包括：
裝置MS21，令網路中每個節點維護著一個狀態記錄表，狀態記錄表中每條記錄包含當前已經訪問到的源節點id和相應的距離、最短路徑數目、前驅節點這四個欄位；
裝置MS22，令在Map階段所有節點都根據當前狀態表中的每條記錄構造更新訊息；更新訊息是以鍵/值對的形式處理，其中鍵是需要接受該更新訊息的目的節點的id，值中包含了目的節點需要的信息，與狀態記錄表中的記錄包含同樣的四個欄位；到源節點的距離等於本節點到源節點的距離加1，所述最短路徑數目即為本節點到源節點的最短路徑數目，前驅節點則為節點本身；
裝置MS23，令Map階段產生的鍵/值對將通過MapReduce框架進行自動劃分，最終相同鍵的鍵/值對被同一個Reduce函式接收，完成訊息傳遞的過程；
裝置MS24，令在Reduce階段，所有節點都會收到來自鄰居節點的若干條更新訊息；以訊息中的源節點為準在狀態記錄表中進行匹配，查找該源節點對相應的狀態記錄，並根據更新訊息中包含的信息進行狀態更新；
裝置MS25，判斷所有源節點是否完成寬度遍歷，若沒有則跳轉觸發裝置MS23繼續疊代，若完成了則觸發裝置MS3繼續執行。
改善效果
針對傳統單機算法在計算大規模網路拓撲特徵參數時效率較低的問題，《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》克服了2016年8月之前的單機算法並行移植到MapReduce時存在的問題，利用Hadoop計算平台實現了網路拓撲特徵參數的並行計算，提高了網路拓撲特徵參數的計算效率。
附圖說明
圖1為基於MapReduce的介數算法。
圖2為算法遍歷階段的訊息傳遞過程。
圖3為並行介數算法消耗時間。
圖4為並行算法的加速比。
src | dis | numSP | pre |
a | 0 | 1 | null |
b | 1 | 1 | b |
c | 1 | 1 | c |
d | 2 | 2 | b,c |
技術領域
《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》涉及複雜網路，具體地，涉及基於MapReduce的複雜網路拓撲特徵參數計算方法和系統。
權利要求
1.《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》採用基於訊息傳遞的算法並行化方法；所述基於訊息傳遞的算法並行化方法，包括：步驟1，產生更新訊息；每個節點根據本節點的狀態信息計算生成更新訊息的內容，把鄰居節點作為訊息的目的節點，將更新訊息向目的節點傳送；步驟2，傳遞訊息；更新訊息按照目的節點被傳送給指定的節點；步驟3，更新節點內部狀態信息；目的節點收到若干條更新訊息，目的節點對這些更新訊息進行解析並更新目的節點內部狀態信息；採用利用所述基於訊息傳遞的算法並行化方法實現的基於MapReduce的介數方法；所述基於MapReduce的介數方法，包括：步驟S1，所有節點選取自己做為源節點開始計算節點介數；步驟S2，從源節點出發進行寬度優先遍歷；步驟S3，回溯求解點對依賴度；步驟S4，累加點對依賴度得到介數。
2.根據權利要求1所述的基於MapReduce的複雜網路拓撲特徵參數計算方法，其特徵在於，所述步驟1，具體為：步驟1由MapReduce框架中的Map階段完成，Map階段的處理方法由用戶完成；該Map階段負責處理每條存儲節點信息的文本記錄，根據需求產生更新訊息鍵/值對；其中，鍵是鄰居節點id，值是更新訊息的內容；所述步驟2，具體為：所述步驟2由MapReduce框架中的partitioner組件自動完成，partitioner組件默認根據hash算法把具有相同鍵的訊息鍵/值對和節點鍵/值對劃分到一起，使得更新訊息達到了傳遞的效果；所述步驟3，具體為：所述步驟3由MapReduce框架中的Reduce階段完成，Reduce階段負責接收上一階段傳遞的鍵/值對，把所有具有相同鍵的訊息鍵/值對和節點鍵/值對進行聚合，得到更新後的節點鍵/值對並輸出；Reduce階段的處理方法由用戶根據需求自定義完成的。
3.根據權利要求1所述的基於MapReduce的複雜網路拓撲特徵參數計算方法，其特徵在於，節點v的介數被定義為：
其中，B（v）表示節點v的介數，σst表示節點s和節點t之間的最短路徑條數，σst（v）表示節點s和節點t之間的最短路徑中經過節點v的條數；V表示網路節點的集合；
所述步驟S2包括：從所有源節點同時出發寬度優先遍歷其餘節點，當訪問到當前節點v時，根據下式：
計算節點v到源節點s的最短路徑的數目，並記錄下節點v的前驅節點Ps（v）；疊代遍歷過程，直到所有節點都被訪問到；其中，σsv表示節點s到節點v的最短路徑數目，Ps（v）表示節點v以節點s為源的前驅節點，σsu表示節點s到節點u的最短路徑數目；所述步驟S3包括：從距離源節點最遠一層的節點開始回溯，按照下式：
計算當前層中節點的前驅節點的點對依賴度；不停回溯計算前驅節點的點對依賴度，直到回到源節點，得到源節點對其他所有節點的依賴度；其中，δs·（v）表示節點s對節點v的依賴度，稱為點對依賴度；w，v表示網路中的節點；σsw表示節點s到節點w的最短路徑數目；δs·（w）表示節點s對節點w的依賴度；所述步驟S4包括：根據如下公式：
將不同源節點對節點v的依賴度求和得到該節點v的介數。
4.根據權利要求1所述的基於MapReduce的複雜網路拓撲特徵參數計算方法，其特徵在於，所述步驟S2包括：步驟S21，網路中每個節點維護著一個狀態記錄表，狀態記錄表中每條記錄包含當前已經訪問到的源節點id和相應的距離、最短路徑數目、前驅節點這四個欄位；步驟S22，在Map階段所有節點都根據當前狀態表中的每條記錄構造更新訊息；更新訊息是以鍵/值對的形式處理，其中鍵是需要接受該更新訊息的目的節點的id，值中包含了目的節點需要的信息，與狀態記錄表中的記錄包含同樣的四個欄位；到源節點的距離等於本節點到源節點的距離加1，所述最短路徑數目即為本節點到源節點的最短路徑數目，前驅節點則為節點本身；
步驟S23，Map階段產生的鍵/值對將通過MapReduce框架進行自動劃分，最終相同鍵的鍵/值對被同一個Reduce函式接收，完成訊息傳遞的過程；
步驟S24，在Reduce階段，所有節點都會收到來自鄰居節點的若干條更新訊息；以訊息中的源節點為準在狀態記錄表中進行匹配，查找該源節點對相應的狀態記錄，並根據更新訊息中包含的信息進行狀態更新；
步驟S25，判斷所有源節點是否完成寬度遍歷，若沒有則跳轉到步驟S23繼續疊代，若完成了則進入步驟S3繼續執行。
5.一種基於MapReduce的複雜網路拓撲特徵參數計算系統，其特徵在於，包括基於訊息傳遞的算法並行化裝置；所述基於訊息傳遞的算法並行化裝置，包括：裝置M1，產生更新訊息；每個節點根據本節點的狀態信息計算生成更新訊息的內容，把鄰居節點作為訊息的目的節點，將更新訊息向目的節點傳送；裝置M2，傳遞訊息；更新訊息按照目的節點被傳送給指定的節點；裝置M3，更新節點內部狀態信息；目的節點收到若干條更新訊息，目的節點對這些更新訊息進行解析並更新目的節點內部狀態信息；採用利用所述基於訊息傳遞的算法並行化裝置實現的基於MapReduce的介數裝置；所述基於MapReduce的介數裝置，包括：裝置MS1，令所有節點選取自己做為源節點開始計算節點介數；裝置MS2，從源節點出發進行寬度優先遍歷；裝置MS3，回溯求解點對依賴度；裝置MS4，累加點對依賴度得到介數。
6.根據權利要求5所述的基於MapReduce的複雜網路拓撲特徵參數計算系統，其特徵在於，所述裝置M1，具體為：裝置M1在MapReduce框架中的Map階段被觸發執行，Map階段的處理方法由用戶完成；該Map階段負責處理每條存儲節點信息的文本記錄，根據需求產生更新訊息鍵/值對；其中，鍵是鄰居節點id，值是更新訊息的內容；所述裝置M2，具體為：所述裝置M2在MapReduce框架中的partitioner組件被觸發執行，partitioner組件默認根據hash算法把具有相同鍵的訊息鍵/值對和節點鍵/值對劃分到一起，使得更新訊息達到了傳遞的效果；所述裝置M3，具體為：所述裝置M3在MapReduce框架中的Reduce階段被觸發執行，Reduce階段負責接收上一階段傳遞的鍵/值對，把所有具有相同鍵的訊息鍵/值對和節點鍵/值對進行聚合，得到更新後的節點鍵/值對並輸出；Reduce階段的處理方法由用戶根據需求自定義完成的。
7.根據權利要求5所述的基於MapReduce的複雜網路拓撲特徵參數計算系統，其特徵在於，節點v的介數被定義為：
其中，B（v）表示節點v的介數，σst表示節點s和節點t之間的最短路徑條數，σst（v）表示節點s和節點t之間的最短路徑中經過節點v的條數；V表示網路節點的集合；所述裝置MS2具體為：從所有源節點同時出發寬度優先遍歷其餘節點，當訪問到當前節點v時，根據下式：
計算節點v到源節點s的最短路徑的數目，並記錄下節點v的前驅節點Ps（v）；疊代遍歷過程，直到所有節點都被訪問到；其中，σsv表示節點s到節點v的最短路徑數目，Ps（v）表示節點v以節點s為源的前驅節點，σsu表示節點s到節點u的最短路徑數目；所述裝置MS3具體為：從距離源節點最遠一層的節點開始回溯，按照下式：
計算當前層中節點的前驅節點的點對依賴度；不停回溯計算前驅節點的點對依賴度，直到回到源節點，得到源節點對其他所有節點的依賴度；其中，δs·（v）表示節點s對節點v的依賴度，稱為點對依賴度；w，v表示網路中的節點；σsw表示節點s到節點w的最短路徑數目；δs·（w）表示節點s對節點w的依賴度；所述裝置MS4具體為：根據如下公式：
將不同源節點對節點v的依賴度求和得到該節點v的介數。8.根據權利要求5所述的基於MapReduce的複雜網路拓撲特徵參數計算系統，其特徵在於，所述裝置MS2包括：裝置MS21，令網路中每個節點維護著一個狀態記錄表，狀態記錄表中每條記錄包含當前已經訪問到的源節點id和相應的距離、最短路徑數目、前驅節點這四個欄位；裝置MS22，令在Map階段所有節點都根據當前狀態表中的每條記錄構造更新訊息；更新訊息是以鍵/值對的形式處理，其中鍵是需要接受該更新訊息的目的節點的id，值中包含了目的節點需要的信息，與狀態記錄表中的記錄包含同樣的四個欄位；到源節點的距離等於本節點到源節點的距離加1，所述最短路徑數目即為本節點到源節點的最短路徑數目，前驅節點則為節點本身；裝置MS23，令Map階段產生的鍵/值對將通過MapReduce框架進行自動劃分，最終相同鍵的鍵/值對被同一個Reduce函式接收，完成訊息傳遞的過程；裝置MS24，令在Reduce階段，所有節點都會收到來自鄰居節點的若干條更新訊息；以訊息中的源節點為準在狀態記錄表中進行匹配，查找該源節點對相應的狀態記錄，並根據更新訊息中包含的信息進行狀態更新；裝置MS25，判斷所有源節點是否完成寬度遍歷，若沒有則跳轉觸發裝置MS23繼續疊代，若完成了則觸發裝置MS3繼續執行。
實施方式
《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》提供的基於MapReduce的複雜網路拓撲特徵參數計算方法，採用基於訊息傳遞的算法並行化方法，包括：
步驟1，產生更新訊息。每個節點根據本節點的狀態信息計算生成更新訊息內容，把鄰居節點作為訊息的目的節點，將訊息傳送出去。在MapReduce框架中，該步驟工作由Map階段完成，Map階段的處理方法由用戶完成。該階段負責處理每條存儲節點信息的文本記錄，根據需求產生更新訊息鍵/值對。其中鍵是鄰居節點id，值是更新訊息的內容。
步驟2，傳遞訊息。更新訊息按照目的節點被傳送給指定的節點。在MapReduce框架中，該步驟工作由框架的partitioner自動完成，它默認根據hash算法把具有相同鍵的訊息鍵/值對和節點鍵/值對劃分到一起，使得訊息達到了傳遞的效果。
步驟3，更新節點內部狀態信息。目的節點收到若干條更新訊息，節點對這些訊息進行解析並更新節點內部狀態信息。該步驟由MapReduce的Reduce階段完成，該階段負責接收上一階段傳遞的鍵/值對，把所有具有相同鍵的訊息鍵/值對和節點鍵/值對進行聚合，得到更新後的節點鍵/值對並輸出。Reduce階段的處理方法也是由用戶根據需求自定義完成的。
下面以介數計算為例，詳細介紹該發明在計算網路拓撲參數中的實現。
網路中不相鄰的節點s和t之間的最短路徑會經過其他若干節點，節點v被其他最短路徑經過次數越多，則表示該節點在網路中越重要。由此，節點v的介數被定義為：
其中σst表示節點s和t之間的最短路徑數目，σst（v）表示這些最短路徑經過節點v的數目。
利用訊息傳遞機制實現的基於MapReduce的介數算法如圖1所示。
步驟S1，所有節點選取自己做為源節點開始計算節點介數。
步驟S2，從源節點出發進行寬度優先遍歷。從所有源節點同時出發寬度優先遍歷其餘節點，當訪問到當前節點v時，根據公式2計算節點v到源節點s的最短路徑的數目，並記錄下節點v的前驅節點Ps（v）。疊代遍歷過程，直到所有節點都被訪問到。
其中σsv表示節點s到節點v的最短路徑數目。Ps（v）表示節點v以節點s為源的前驅節點。
步驟S3，回溯求解點對依賴度。從距離源節點最遠一層的節點開始回溯，按照公式3計算當前層中節點的前驅節點的點對依賴度。不停回溯計算前驅節點的點對依賴度，直到回到源節點。得到源節點對其他所有節點的依賴度。
其中δs·（v）表示節點s對節點v的依賴度，稱為點對依賴度。
步驟S4，累加點對依賴度得到介數。根據公式4，將不同源節點對節點v的依賴度求和得到該節點的介數。
其中B（v）表示節點v的介數。
所述步驟S2和S3都包含多次的MapReduce疊代，原理相似。以S2為例對算法中的訊息傳遞過程進行介紹，所述步驟S2進一步為。
步驟S21，網路中每個節點維護著一個狀態記錄表，表中每條記錄包含當前已經訪問到的源節點id和相應的距離、最短路徑數目、前驅節點，示例中該條記錄表示節點a到本身的距離為0，默認有1條路徑，不需要經過前驅節點。
步驟S22，在Map階段所有節點都根據當前狀態表中的每條記錄構造更新訊息。更新訊息是以鍵/值對的形式處理，其中鍵是需要接受該訊息的目的節點的id，值中包含了目的節點需要的信息，與記錄表中的記錄包含同樣的四個欄位。到源節點的距離等於本節點到源節點的距離加1，最短路徑數目即為本節點到源節點的最短路徑數目，前驅節點則為節點本身。如示例中，節點a向鄰居節點b和c傳送包含同樣值的訊息a|1|1|a，告知鄰居節點可以通過本節點到達a，距離為1，最短路徑數目為1，前驅節點為a。
步驟S23，Map階段產生的鍵/值對（包括節點狀態信息和更新訊息）將會通過MapReduce框架進行自動劃分，最終相同鍵的鍵/值對會被同一個Reduce函式接收，完成訊息傳遞的過程。如示例中的b和c產生的以a為鍵的訊息將會被傳送到節點a。
步驟S24，在Reduce階段，所有節點都會收到來自鄰居節點的若干條更新訊息。以訊息中的源節點為準在狀態記錄表中進行匹配，查找該源節點對相應的狀態記錄，並根據訊息中包含的信息進行狀態更新。如示例中a收到來自b，c的訊息後，因為a節點沒有記錄到達這兩個節點的信息，所以將該信息添加到自身節點的狀態表中，表示節點a已經知道了到達節點b和c的信息，完成了一輪疊代。
步驟S25，判斷所有源節點是否完成寬度遍歷，若沒有則跳轉到步驟S23繼續疊代，若完成了則輸出結果，寬度遍歷階段結束。
該發明在分散式計算框架中實現了網路拓撲特徵參數的計算，解決了單機計算記憶體受限、效率低下的問題，提高了計算網路拓撲參數的效率。
利用實驗說明該發明的性能。實驗對五個不同規模的路由器網路的拓撲特徵參數進行計算，網路規模如表1所示。
編號 | 地區 | N | M | <K> |
G1 | IN | 280759 | 281349 | 2.01 |
G2 | JP | 774619 | 789841 | 2.00 |
G3 | DE | 1847669 | 1863544 | 2.02 |
G4 | KR | 2035168 | 2046123 | 2.01 |
G5 | US | 6198093 | 6322708 | 2.04 |
其中，n，m表示網路的節點數和邊數，<k>表示網路的節點平均度。
使用該發明計算網路中節點介數的效率如圖3所示。可以看出，在同一計算集群中計算不同規模網路的介數，網路規模越大，算法的執行時間越長。對於處理同一網路數據來說，隨著計算集群中計算節點的增加，計算介數的時間在不斷下降。並且隨著實驗網路數據規模的增大，運行時間減少的幅度越大。使用8個計算節點來計算包含百萬級別節點的網路，效率可以提升6倍以上。實驗說明該發明可以通過擴大集群規模來大幅計算提升效率，尤其是在處理大規模拓撲數據時更具優勢。
除並行介數算法外，該發明基於MapReduce計算框架設計還實現了計算的度（Degree）、聚類係數（Cluster）、網路直徑（D）、平均路徑長度（L）、最大連通子圖大小（|gs|）和核數（Core）的並行算法。它們在不同規模集群中運行的加速比平均值如圖4所示。從圖中可以看出，隨著計算集群規模的擴大，七種算法的加速比都得到了明顯的提升。而且算法時間複雜度最高的介數算法提升幅度最大。這說明了該發明所設計實現的算法在Hadoop平台上具有良好的擴展性，尤其是在對時間複雜度較高的算法提升更明顯。
榮譽表彰
2020年7月17日，《基於MapReduce的複雜網路拓撲特徵參數計算方法和系統》獲得安徽省第七屆專利獎優秀獎。
