超大規(guī)模圖的最短路徑距離近似算法.pdf

1、最短路徑算法是算法中的經(jīng)典算法之一。最短路徑算法不僅可以用來解決計算機方面的問題，還可以用來解決優(yōu)化道路規(guī)劃、傳感器部署等很多現(xiàn)實問題。節(jié)點邊介數(shù)的計算，中心點的尋找，社區(qū)的發(fā)現(xiàn)、商品的推薦等一系列復雜網(wǎng)絡相關問題的分析與研究都需要用到最短路徑算法。隨著社會發(fā)展，應用最短路徑算法的圖的規(guī)模越來越大，經(jīng)典的Dijkstra和Floyd最短路徑算法早已經(jīng)不適用于相關的計算。經(jīng)典算法的復雜度太高，計算量較大，需要空間大，在大數(shù)據(jù)的處理方面能力

2、不足。因此為克服這些難點，超大規(guī)模圖的最短路徑近似算法應運而生，其中基于區(qū)域劃分的中心距離的最短路徑長度近似算法（簡稱CDZ算法）和基于坐標的Orin算法（簡稱Orin算法）最有代表性。CDZ算法在復雜網(wǎng)絡的計算中運算效率較高，Orin算法的準確率較高但在預處理方面運算量較大。根據(jù)對社交網(wǎng)絡這類復雜網(wǎng)絡的研究，統(tǒng)計領域的研究者們發(fā)現(xiàn)超大規(guī)模網(wǎng)絡中存在許多特性。這些網(wǎng)絡特性的發(fā)現(xiàn)有利于超大規(guī)模圖的最短路徑算法的優(yōu)化。因此我們在已有算法的基

3、礎上提出了新的算法，主要研究工作及成果如下:
　　1)通過研究分析復雜網(wǎng)絡，一些基本的網(wǎng)絡模型和復雜網(wǎng)絡的特征統(tǒng)計量找到能夠急遽收縮超大規(guī)模網(wǎng)絡的方法。通過研究分析經(jīng)典最短路徑算法和已有的大規(guī)模圖的最短路徑近似算法，找出其算法的優(yōu)點和不足，尋找改進的突破口。
　　2)根據(jù)超大規(guī)模圖的自相似特性提出基于縮略網(wǎng)絡的最短路徑近似算法。通過構造縮略網(wǎng)絡高效地降低網(wǎng)絡規(guī)模，縮短預處理時間。算法充分利用復雜網(wǎng)絡的自相似特性對節(jié)點收縮，在

4、粗粒度下的網(wǎng)絡和細粒度的網(wǎng)絡具有相似性，收縮后的網(wǎng)絡性質(zhì)與原網(wǎng)絡一致。在對網(wǎng)絡進行預處理之后，運用公式計算節(jié)點間最短路徑長度的近似值。
　　3)在構建縮略網(wǎng)絡計算出最短路徑近似長度的基礎上，通過最短路徑上landmark規(guī)模來近似經(jīng)過該節(jié)點的最短路徑數(shù)目，再根據(jù)公式計算出被收縮及節(jié)點的介數(shù)值。計算出圖中所有介數(shù)值之后再通過公式計算出各節(jié)點對應的介數(shù)中心性。
　　4)通過不同規(guī)模的數(shù)據(jù)集將算法與其他算法進行對比分析，驗證算法的

5、優(yōu)劣。
　　5)用WindowBuilder Pro插件實現(xiàn)最短路徑近似距離Oracle，程序包含預處理、最短路徑近似距離查詢和介數(shù)計算三個部分。
　　由實驗結果得出，本文提出的算法在超大規(guī)模網(wǎng)絡中相較于其他算法，運算效率有所提高且準確率仍保持較高水平。在超大規(guī)模圖中，處理百萬節(jié)點和千萬條邊本文算法只需要幾十毫秒，這一運算效率是CDZ算法的數(shù)十倍，遠高于Orin算法。在介數(shù)中心性的計算方面，本文算法也優(yōu)于UB算法和CDZ中心