本文選題：復(fù)雜網(wǎng)絡(luò) + 最短路徑　； 參考：《遼寧大學(xué)》2017年碩士論文

【摘要】：最短路徑計(jì)算一直以來(lái)是復(fù)雜網(wǎng)絡(luò)中重要的研究?jī)?nèi)容,近年來(lái),隨著研究的日益深入,復(fù)雜網(wǎng)絡(luò)中許多特征量的計(jì)算及問(wèn)題的解決越來(lái)越多的依賴(lài)于最短路徑的計(jì)算。經(jīng)典算法無(wú)論是在算法復(fù)雜度還是在效率上都已不適用于計(jì)算具有大規(guī)模節(jié)點(diǎn)和連邊的復(fù)雜網(wǎng)絡(luò),而目前一些常見(jiàn)近似計(jì)算算法也因其適用性受限、算法效率與準(zhǔn)確率不理想等因素而不能滿足復(fù)雜網(wǎng)絡(luò)最短路徑計(jì)算的應(yīng)用需求,因此,近似算法要如何在計(jì)算延遲、內(nèi)存占用率和準(zhǔn)確性之間做到最好的平衡及其如何增強(qiáng)網(wǎng)絡(luò)適用性已經(jīng)成為算法研究者們追逐的重要目標(biāo)。本文在相關(guān)算法研究的基礎(chǔ)上,提出了基于k-core分區(qū)域的最短路徑近似算法。算法在真實(shí)的大規(guī)模社會(huì)網(wǎng)絡(luò)、Web社交平臺(tái)網(wǎng)絡(luò)及互聯(lián)網(wǎng)絡(luò)中保持了較高的計(jì)算效率和準(zhǔn)確率。算法首先基于k-core將網(wǎng)絡(luò)水平劃分成若干個(gè)k-shell子網(wǎng)絡(luò),然后根據(jù)節(jié)點(diǎn)k-shell值將包含不同節(jié)點(diǎn)重要性的k-shell子網(wǎng)絡(luò)劃分為高層、邊緣層和中間層三個(gè)區(qū)域,最后在計(jì)算最短路徑時(shí),對(duì)于高層區(qū)域,由于節(jié)點(diǎn)規(guī)模較小且連邊比較密集,故精確計(jì)算其所有節(jié)點(diǎn)對(duì)的最短路徑;對(duì)于邊緣層區(qū)域,節(jié)點(diǎn)度比較小,依據(jù)k-shell作為節(jié)點(diǎn)重要性,每次搜索只搜索k-shell值大于等于當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn),達(dá)到限制節(jié)點(diǎn)搜索區(qū)域的目的;對(duì)于中間層區(qū)域,由于所包含k-shell子圖之間的連邊密集,故對(duì)k-shell子網(wǎng)內(nèi)部節(jié)點(diǎn)進(jìn)行超點(diǎn)聚合,搜索時(shí)只利用超點(diǎn)的中心節(jié)點(diǎn)與其它區(qū)域節(jié)點(diǎn)的連邊關(guān)系已達(dá)到提高搜索效率的目的,其搜索過(guò)程同邊緣層區(qū)域。算法使用k-core作為網(wǎng)絡(luò)劃分及搜索目標(biāo)引導(dǎo)依據(jù)更具一般性,利用超點(diǎn)聚合處理k-shell子網(wǎng)大幅降低了路徑搜索中遍歷節(jié)點(diǎn)的規(guī)模,并且合理使用預(yù)處理、雙向搜索樹(shù)和優(yōu)先隊(duì)列技術(shù)對(duì)路徑搜索過(guò)程進(jìn)行優(yōu)化和加速,大大提高了算法的計(jì)算效率和準(zhǔn)確率。本文使用現(xiàn)實(shí)中不同規(guī)模大小的網(wǎng)絡(luò)數(shù)據(jù)集,對(duì)所述算法進(jìn)行了實(shí)驗(yàn)和分析,實(shí)驗(yàn)數(shù)據(jù)表明算法在網(wǎng)絡(luò)適用性、計(jì)算效率和準(zhǔn)確率上明顯優(yōu)于CDZ算法。例如,在com-DBLP社區(qū)網(wǎng)絡(luò)中(規(guī)模為約30萬(wàn)節(jié)點(diǎn)、100萬(wàn)連邊的無(wú)向圖),節(jié)點(diǎn)對(duì)最短路徑的平均計(jì)算時(shí)間只需幾十毫秒,正確率能夠達(dá)到99%;在不同冪律指數(shù)的無(wú)標(biāo)度網(wǎng)絡(luò)仿真模型中,算法也表現(xiàn)出了非常好的適用性和效率。
[Abstract]:The calculation of the shortest path has always been an important research content in the complex network. In recent years, with the deepening of the research, the calculation of many characteristic variables and the solution of the problem in the complex network are more and more dependent on the calculation of the shortest path.The classical algorithms are no longer suitable for the computation of complex networks with large nodes and connected edges in terms of complexity and efficiency. However, some common approximate algorithms are limited by their applicability.The efficiency and accuracy of the algorithm are not ideal and can not meet the needs of the application of the shortest path calculation in complex networks. Therefore, how to calculate the delay of the approximate algorithm,How to achieve the best balance between memory occupancy and accuracy and how to enhance the applicability of the network has become an important goal pursued by algorithmic researchers.In this paper, the shortest path approximation algorithm based on k-core sub-region is proposed based on the research of relevant algorithms.The algorithm maintains high computational efficiency and accuracy in real large-scale social networks such as Web social platform networks and Internet networks.The algorithm first divides the network level into several k-shell subnetworks based on k-core, and then divides the k-shell subnetwork which contains different node importance into three regions: high layer, edge layer and middle layer according to the node k-shell value. Finally, when calculating the shortest path, the algorithm divides the k-shell subnetwork into three regions: the upper layer, the edge layer and the middle layer.For the high level region, because the node size is small and the connected edges are dense, the shortest path of all the node pairs is calculated accurately, and for the edge layer area, the node degree is relatively small, according to the importance of k-shell as the node,Each search only searches neighbor nodes whose k-shell value is greater than or equal to the current node, so as to limit the search area of the nodes. For the middle layer region, because of the dense edges between the included k-shell subgraphs, the nodes in the k-shell subnet are hyper-aggregated.The search efficiency can be improved by using only the connection between the center node of the superpoint and the nodes of other regions, and the search process is the same as that of the edge layer region.Using k-core as the basis of network partition and search target guidance is more general. Using hyper-point aggregation to deal with k-shell subnet greatly reduces the scale of traversal nodes in path search and uses preprocessing reasonably.The bidirectional search tree and priority queue technology optimize and accelerate the path search process, which greatly improves the computational efficiency and accuracy of the algorithm.In this paper, the experimental results show that the proposed algorithm is superior to the CDZ algorithm in network applicability, computational efficiency and accuracy using the network datasets of different sizes in reality.For example, in a com-DBLP community network (an undirected graph with about 300000 nodes in scale and 1 million connected edges), the average computing time for the shortest path is only several tens of milliseconds, and the accuracy can reach 99. In the scaleless network simulation model with different power law exponents, the mean computing time of the node is only several tens of milliseconds.The algorithm also shows very good applicability and efficiency.
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：TP301.6;O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 朱愷騁;程華;;基于重疊節(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò)最短路徑算法[J];華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期

2 朱恒超;邢海磊;陳新一;;基于無(wú)標(biāo)度網(wǎng)絡(luò)的最大度二分度搜索策略[J];西北民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

3 宋青;汪小帆;;最短路徑算法加速技術(shù)研究綜述[J];電子科技大學(xué)學(xué)報(bào);2012年02期

4 唐晉韜;王挺;王戟;;適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J];軟件學(xué)報(bào);2011年10期

5 李輝;趙海;徐久強(qiáng);李博;李鵬;王家亮;;基于k-核的大規(guī)模軟件宏觀拓?fù)浣Y(jié)構(gòu)層次性研究[J];電子學(xué)報(bào);2010年11期

6 溫巧林;司守奎;任東彥;謝宇鵬;;基于最大度和隨機(jī)游走的混合搜索算法[J];海軍航空工程學(xué)院學(xué)報(bào);2010年05期

7 楊國(guó)正;陸余良;夏陽(yáng);胡博;;基于核數(shù)分層的AS級(jí)網(wǎng)絡(luò)拓?fù)淇梢暬季炙惴╗J];計(jì)算機(jī)應(yīng)用研究;2009年12期

8 劉建香;;復(fù)雜網(wǎng)絡(luò)及其在國(guó)內(nèi)研究進(jìn)展的綜述[J];系統(tǒng)科學(xué)學(xué)報(bào);2009年04期

9 王天驕;汪小帆;李翔;;無(wú)標(biāo)度網(wǎng)絡(luò)的最大—最小度搜索算法[J];計(jì)算機(jī)仿真;2007年09期

10 陸鋒;最短路徑算法:分類(lèi)體系與研究進(jìn)展[J];測(cè)繪學(xué)報(bào);2001年03期

相關(guān)博士學(xué)位論文 前1條

1 宋青;大規(guī)模網(wǎng)絡(luò)最短路徑的分層優(yōu)化算法研究[D];上海交通大學(xué);2012年

，

本文編號(hào)：1742962