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

【摘要】：最短路徑計算一直以來是復(fù)雜網(wǎng)絡(luò)中重要的研究內(nèi)容,近年來,隨著研究的日益深入,復(fù)雜網(wǎng)絡(luò)中許多特征量的計算及問題的解決越來越多的依賴于最短路徑的計算。經(jīng)典算法無論是在算法復(fù)雜度還是在效率上都已不適用于計算具有大規(guī)模節(jié)點和連邊的復(fù)雜網(wǎng)絡(luò),而目前一些常見近似計算算法也因其適用性受限、算法效率與準(zhǔn)確率不理想等因素而不能滿足復(fù)雜網(wǎng)絡(luò)最短路徑計算的應(yīng)用需求,因此,近似算法要如何在計算延遲、內(nèi)存占用率和準(zhǔn)確性之間做到最好的平衡及其如何增強網(wǎng)絡(luò)適用性已經(jīng)成為算法研究者們追逐的重要目標(biāo)。本文在相關(guān)算法研究的基礎(chǔ)上,提出了基于k-core分區(qū)域的最短路徑近似算法。算法在真實的大規(guī)模社會網(wǎng)絡(luò)、Web社交平臺網(wǎng)絡(luò)及互聯(lián)網(wǎng)絡(luò)中保持了較高的計算效率和準(zhǔn)確率。算法首先基于k-core將網(wǎng)絡(luò)水平劃分成若干個k-shell子網(wǎng)絡(luò),然后根據(jù)節(jié)點k-shell值將包含不同節(jié)點重要性的k-shell子網(wǎng)絡(luò)劃分為高層、邊緣層和中間層三個區(qū)域,最后在計算最短路徑時,對于高層區(qū)域,由于節(jié)點規(guī)模較小且連邊比較密集,故精確計算其所有節(jié)點對的最短路徑;對于邊緣層區(qū)域,節(jié)點度比較小,依據(jù)k-shell作為節(jié)點重要性,每次搜索只搜索k-shell值大于等于當(dāng)前節(jié)點的鄰居節(jié)點,達到限制節(jié)點搜索區(qū)域的目的;對于中間層區(qū)域,由于所包含k-shell子圖之間的連邊密集,故對k-shell子網(wǎng)內(nèi)部節(jié)點進行超點聚合,搜索時只利用超點的中心節(jié)點與其它區(qū)域節(jié)點的連邊關(guān)系已達到提高搜索效率的目的,其搜索過程同邊緣層區(qū)域。算法使用k-core作為網(wǎng)絡(luò)劃分及搜索目標(biāo)引導(dǎo)依據(jù)更具一般性,利用超點聚合處理k-shell子網(wǎng)大幅降低了路徑搜索中遍歷節(jié)點的規(guī)模,并且合理使用預(yù)處理、雙向搜索樹和優(yōu)先隊列技術(shù)對路徑搜索過程進行優(yōu)化和加速,大大提高了算法的計算效率和準(zhǔn)確率。本文使用現(xiàn)實中不同規(guī)模大小的網(wǎng)絡(luò)數(shù)據(jù)集,對所述算法進行了實驗和分析,實驗數(shù)據(jù)表明算法在網(wǎng)絡(luò)適用性、計算效率和準(zhǔn)確率上明顯優(yōu)于CDZ算法。例如,在com-DBLP社區(qū)網(wǎng)絡(luò)中(規(guī)模為約30萬節(jié)點、100萬連邊的無向圖),節(jié)點對最短路徑的平均計算時間只需幾十毫秒,正確率能夠達到99%;在不同冪律指數(shù)的無標(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é)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP301.6;O157.5

【參考文獻】

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

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

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

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

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

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

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

7 楊國正;陸余良;夏陽;胡博;;基于核數(shù)分層的AS級網(wǎng)絡(luò)拓撲可視化布局算法[J];計算機應(yīng)用研究;2009年12期

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

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

10 陸鋒;最短路徑算法:分類體系與研究進展[J];測繪學(xué)報;2001年03期

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

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

，

本文編號：1742962