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

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

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

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

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

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