MapReduce背景下的復雜網絡鏈路預測分析

常雅文

(西安航空學院， 西安 710077)

0 引言

復雜網絡鏈路預測由于在社交網絡、信息通信等社會方面的廣泛應用，現已成為數據挖掘的主要研究方向，已成為學術界關注的熱點[1]。網絡鏈路預測作為一種預測方式主要是通過已知網絡拓撲結構和網絡節點屬性等信息預測網絡中未產生連邊的節點產生連接的可能性[2]。傳統的鏈路預測算法以節點屬性為特點，譬如馬爾科夫鏈或機械學習等算法，盡管算法預測精度高，但由于計算復雜度高、計算中涉及的非普適性參數應用的限制，導致算法使用受限[3-4]。另一類傳統鏈路算法則以網絡結構為特點進行最大似然估計，文獻[5]中介紹了一種網絡層次結構為基礎的鏈路預測算法，并顯示該類算法在層次結構明顯的網絡中具有較高的預測精度，但該類算法的計算復雜度高。

與傳統的鏈路預測算法相比，以網絡拓撲結構為基礎的鏈路預測算法通用性強，且網絡拓撲結構極易獲得。但在處理大規模復雜網絡鏈路時，由于算法復雜度和單臺計算機內存限制，處理速度慢，且準確性不足。MapReduce[6]作為Google公司2004年提出的可以并行處理海量數據的編程模式和任務調度模式，可以通過屏蔽底層實現細節減少并行編程復雜度，提高編程效率而具有廣泛應用。基于MapReduce編程時，開發人員只要考慮應用程序本身特性，無需考慮集群處理，將其交由平臺處理。因此在MapReduce背景下進行復制網絡鏈路預測分析具有重要的使用價值和意義。……