隨著社會(huì)的發(fā)展和研究的深入,對(duì)復(fù)雜網(wǎng)絡(luò)的研究逐漸從單維網(wǎng)絡(luò)轉(zhuǎn)向多維網(wǎng)絡(luò),多維網(wǎng)絡(luò)節(jié)點(diǎn)之間的連邊包含多個(gè)維度的權(quán)值,多維網(wǎng)絡(luò)最短路徑的計(jì)算需要綜合考慮多個(gè)維度上的權(quán)值,通過給定的評(píng)分函數(shù)計(jì)算得到路徑的具體代價(jià)。單維網(wǎng)絡(luò)最短路徑的計(jì)算方法都基于Dijkstra算法的子路徑性質(zhì),而若多維網(wǎng)絡(luò)的評(píng)分函數(shù)是非線性函數(shù),子路徑性質(zhì)并不適用,因此單維網(wǎng)絡(luò)最短路徑算法并不適用于多維網(wǎng)絡(luò)。目前對(duì)多維網(wǎng)絡(luò)最短路徑的研究依然較少,現(xiàn)有方法的適用性較差,計(jì)算效率和準(zhǔn)確率不能滿足大規(guī)模多維網(wǎng)絡(luò)最短路徑計(jì)算的需求。本文在現(xiàn)有研究的基礎(chǔ)上,提出了一種基于k-shell的多維網(wǎng)絡(luò)最短路徑近似算法。算法根據(jù)節(jié)點(diǎn)k-shell值將網(wǎng)絡(luò)分為高層和低層區(qū)域,搜索過程中使用雙向搜索樹進(jìn)行搜索,利用節(jié)點(diǎn)k-shell值控制搜索方向以及兩棵搜索樹的切換,從低層向著高層方向交替搜索節(jié)點(diǎn)對(duì)之間的最短路徑,當(dāng)搜索隊(duì)列都為空或者都到達(dá)高層區(qū)域時(shí)搜索過程結(jié)束,并選擇一條評(píng)分函數(shù)下代價(jià)最小的路徑作為近似最短路徑。算法向著當(dāng)前節(jié)點(diǎn)的高k-shell值鄰居節(jié)點(diǎn)方向進(jìn)行搜索,同時(shí)綜合考慮節(jié)點(diǎn)k-shell值以及鄰居節(jié)點(diǎn)k-shell值對(duì)節(jié)點(diǎn)的影響,...

【文章頁數(shù)】：67 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖2-12005年互聯(lián)網(wǎng)部分地圖快照

第2章相關(guān)工作征。2.動(dòng)態(tài)變化：復(fù)雜網(wǎng)絡(luò)中隨時(shí)會(huì)增加或刪除節(jié)點(diǎn)或連邊，導(dǎo)致復(fù)雜結(jié)構(gòu)也隨之改變。3.連接多樣：節(jié)點(diǎn)之間的連邊的權(quán)值存在差異，連邊類型可分為有邊。4.節(jié)點(diǎn)多樣：現(xiàn)實(shí)生活中的任何一種實(shí)體都可以抽象為復(fù)雜網(wǎng)絡(luò)中的，表示人際關(guān)系的復(fù)雜網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)代表一個(gè)人，表示....

圖2-2k-shell分解示意圖

絡(luò)節(jié)點(diǎn)重要性指標(biāo)k-shell圖論中的一個(gè)經(jīng)典概念，是一種粗�；墓�(jié)點(diǎn)重要度值為1的節(jié)點(diǎn)開始，首先刪除聯(lián)通圖中度值等于計(jì)算剩余子圖中節(jié)點(diǎn)的度值（剩余子圖可能不是一為0的孤立節(jié)點(diǎn)），若剩余子圖中仍然存在度值等執(zhí)行上述步驟，直到圖中已經(jīng)不再存在度值小于或節(jié)點(diǎn)無論度值是多少....

圖2-3Twitter和YouTube的k-shell分布圖

第2章相關(guān)工作k-shell被廣泛地應(yīng)用到尋找重要節(jié)點(diǎn)的各種研究中[31~34]。如MaksimKi人在文獻(xiàn)[35]中提出了節(jié)點(diǎn)的重要性依賴于其在整個(gè)網(wǎng)絡(luò)中的位置的思想復(fù)雜網(wǎng)絡(luò)的k-shell屬性進(jìn)行研究，證明節(jié)點(diǎn)的k-shell值越大，則該節(jié)點(diǎn)越網(wǎng)絡(luò)的中心，....

圖2-2（a）為例，圖中的節(jié)點(diǎn)3和16的度值都是7，這兩個(gè)節(jié)點(diǎn)是整個(gè)

第2章相關(guān)工作k-shell被廣泛地應(yīng)用到尋找重要節(jié)點(diǎn)的各種研究中[31~34]。如MaksimKi人在文獻(xiàn)[35]中提出了節(jié)點(diǎn)的重要性依賴于其在整個(gè)網(wǎng)絡(luò)中的位置的思想復(fù)雜網(wǎng)絡(luò)的k-shell屬性進(jìn)行研究，證明節(jié)點(diǎn)的k-shell值越大，則該節(jié)點(diǎn)越網(wǎng)絡(luò)的中心，....

本文編號(hào)：3976411