本文選題：動態(tài)圖 + 流式圖　； 參考：《華中科技大學(xué)》2016年碩士論文

【摘要】：隨著應(yīng)用不斷深入,在社交網(wǎng)絡(luò)服務(wù)、科學(xué)計算仿真等場景中,圖數(shù)據(jù)持續(xù)、大量產(chǎn)生,對其進(jìn)行快速、有效分析具有十分重要的意義。在某些對精確度要求不是很高或者只要求反映部分關(guān)鍵圖特性的應(yīng)用中,采取從原圖中抽取具有代表性的子圖進(jìn)行分析的方法,能節(jié)省計算資源和提高處理效率。對動態(tài)圖抽樣時,原圖的持續(xù)變化導(dǎo)致抽樣過程中無法獲取全圖靜態(tài)數(shù)據(jù),故通常采用流式的抽樣算法。不過流式抽樣算法由于累計迭代特性,抽樣過程必須串行,因此當(dāng)抽樣子圖規(guī)模較大時,抽樣過程減速嚴(yán)重,難以保證實時性,而若抽樣子圖偏小,則難以保證其與原圖相似�，F(xiàn)有并行抽樣算法針對的都是靜態(tài)圖,不適用于動態(tài)圖,因此需要提出一種并行的流式抽樣算法。研究分析典型的流式圖抽樣算法PIES(Partial-Induce Edge Sampling)及其改進(jìn)算法PIES-INV,分析PIES并行化方案存在的問題,提出了一種基于協(xié)同邊推導(dǎo)的動態(tài)流式圖并行抽樣算法PaStS(Parallel Streaming Sampling)。PaStS與PIES-INV采取相同的暫存點替換策略,在并行抽樣時,利用全局點信息同步的機制實現(xiàn)動態(tài)調(diào)整各抽樣器的抽樣目標(biāo)大小,以及實現(xiàn)基于全局點集的協(xié)同邊推導(dǎo),從而解決流式抽樣算法并行化時點和邊大量減少的問題。經(jīng)過在真實動態(tài)圖數(shù)據(jù)集和生成圖數(shù)據(jù)集上的測試,PaStS算法相比PIES,在并行度為8時抽樣效率能提高15到49倍。PaStS抽樣得到的子圖在四種圖特性的代表性上與PIES-INV比較接近,在多數(shù)情況下都比PIES好。但是在度分布較為均勻的圖中,PaStS算法在度分布特性和k-core分布特性上不如PIES。另外,PaStS算法在不同數(shù)據(jù)集上的集聚系數(shù)特性上表現(xiàn)比PIES和PIES-INV穩(wěn)定,在有效直徑特性上表現(xiàn)比PIES穩(wěn)定。圖數(shù)據(jù)快速變化時PaStS仍能保持較好的抽樣效果及穩(wěn)定性。
[Abstract]:With the deepening of applications, in the social network services, scientific computing simulation and other scenarios, graph data continue to be generated in large quantities, it is of great significance to analyze them quickly and effectively. In some applications where the accuracy requirement is not very high or only some key graph characteristics are required to be reflected, the method of extracting representative subgraphs from the original image for analysis can save computing resources and improve processing efficiency. When sampling the dynamic graph, the continuous change of the original map makes it impossible to obtain the static data of the whole graph during the sampling process, so the flow sampling algorithm is usually used. However, because of the accumulative iterative characteristic, the sampling process must be serialized, so the sampling process decelerates seriously when the drawing scale is large, and it is difficult to guarantee the real-time performance of the sampling process, but it is difficult to ensure that the sampling process is similar to the original one if the drawing image is small. The existing parallel sampling algorithms are all static graphs, which are not suitable for dynamic graphs, so we need to propose a parallel flow sampling algorithm. This paper studies and analyzes the typical flow diagram sampling algorithm PIES(Partial-Induce Edge sampling and its improved algorithm PIES-INV, and analyzes the problems of PIES parallelization scheme. In this paper, a parallel sampling algorithm for dynamic flow diagram based on co-edge derivation is proposed. PaStS(Parallel Streaming Sampling).PaStS and PIES-INV adopt the same temporary point replacement strategy. The mechanism of global point information synchronization is used to dynamically adjust the sampling target size of each sampler and to realize the cooperative-edge derivation based on the global point set, thus solving the problem of parallelizing the time points and reducing the edge of the flow sampling algorithm. After testing on real dynamic graph data set and generating graph data set, compared with Piesi, the efficiency of sampling with parallel degree of 8 can be improved by 15 to 49 times. PaStS is similar to PIES-INV in the representativeness of four kinds of graph characteristics. In most cases it is better than PIES. However, in the graph with uniform degree distribution, PaStS algorithm is inferior to Piesi in degree distribution and k-core distribution. In addition, PaStS algorithm is more stable than PIES and PIES-INV in the characteristic of aggregation coefficient on different data sets, and more stable than PIES in the characteristic of effective diameter. PaStS can still maintain good sampling effect and stability when the map data changes rapidly.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP391.41

【相似文獻(xiàn)】

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

1 馬安光;;棋子問題的算法分析——2003年第11期題解[J];程序員;2004年01期

2 馮舜璽;;新書推薦:《算法分析導(dǎo)論》[J];計算機教育;2006年05期

3 張力,慕曉冬;計算機算法分析淺談[J];武警工程學(xué)院學(xué)報;2002年04期

4 馬安光;;飛彈問題的算法分析——2003年第10期題解[J];程序員;2003年12期

5 蘇運霖;;《算法分析導(dǎo)論》評介[J];計算機教育;2006年07期

6 朱力強;;培養(yǎng)學(xué)生創(chuàng)新思維與能力的算法分析案例[J];計算機與信息技術(shù);2007年11期

7 汪菊琴;;幾種常見特殊方陣的算法分析與實現(xiàn)[J];無錫職業(yè)技術(shù)學(xué)院學(xué)報;2009年05期

8 李涵;;“算法分析與設(shè)計”課程教學(xué)改革和實踐[J];中國電力教育;2010年16期

9 劉寧;管濤;;淺析案例教學(xué)法在算法分析與設(shè)計課程中的應(yīng)用[J];科技風(fēng);2011年07期

10 胡峰;王國胤;;“算法分析與設(shè)計”教學(xué)模式探索[J];當(dāng)代教育理論與實踐;2011年12期

相關(guān)會議論文 前10條

1 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

2 周顥;劉振華;趙保華;;構(gòu)造型的D~2FA生成算法[A];中國通信學(xué)會通信軟件技術(shù)委員會2009年學(xué)術(shù)會議論文集[C];2009年

3 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（一）[C];2008年

4 劉遠(yuǎn)新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運輸配送系統(tǒng)算法分析[A];第二十六屆中國控制會議論文集[C];2007年

5 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學(xué)生計算語言學(xué)研討會論文集[C];2004年

6 王萬青;張曉輝;;改進(jìn)的A~*算法的高效實現(xiàn)[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎?wù)撐募痆C];2009年

7 孫煥良;邱菲;劉俊嶺;朱葉麗;;IncSNN——一種基于密度的增量聚類算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2006年

8 韓建民;岑婷婷;于娟;;實現(xiàn)敏感屬性l-多樣性的l-MDAV算法[A];第二十七屆中國控制會議論文集[C];2008年

9 張悅;尤楓;趙瑞蓮;;利用蟻群算法實現(xiàn)基于程序結(jié)構(gòu)的主變元分析[A];第五屆中國測試學(xué)術(shù)會議論文集[C];2008年

10 王旭東;劉渝;鄧振淼;;正弦波頻率估計的修正Rife算法及其FPGA實現(xiàn)[A];全國第十屆信號與信息處理、第四屆DSP應(yīng)用技術(shù)聯(lián)合學(xué)術(shù)會議論文集[C];2006年

相關(guān)重要報紙文章 前1條

1 科文;VIXD算法分析Web異常[N];中國計算機報;2008年

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

1 魏哲學(xué);樣本斷點距離問題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

2 劉春明;基于增強學(xué)習(xí)和車輛動力學(xué)的高速公路自主駕駛研究[D];國防科學(xué)技術(shù)大學(xué);2014年

3 張敏霞;生物地理學(xué)優(yōu)化算法及其在應(yīng)急交通規(guī)劃中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2015年

4 李紅;流程挖掘算法研究[D];云南大學(xué);2015年

5 卜晨陽;演化約束優(yōu)化及演化動態(tài)優(yōu)化求解算法研究[D];中國科學(xué)技術(shù)大學(xué);2017年

6 陳拉明;基于非凸優(yōu)化的稀疏重建理論與算法[D];清華大學(xué);2016年

7 劉新旺;多核學(xué)習(xí)算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

8 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學(xué);2006年

9 曾國強;改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

10 肖永豪;蜂群算法及在圖像處理中的應(yīng)用研究[D];華南理工大學(xué);2011年

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

1 黃廈;基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題研究[D];昆明理工大學(xué);2015年

2 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學(xué);2015年

3 趙官寶;基于位表的關(guān)聯(lián)規(guī)則挖掘算法研究[D];昆明理工大學(xué);2015年

4 殷文華;移動容遲網(wǎng)絡(luò)中基于社會感知的多播分發(fā)算法研究[D];內(nèi)蒙古大學(xué);2015年

5 徐翔燕;人工魚群優(yōu)化算法及其應(yīng)用研究[D];西南交通大學(xué);2015年

6 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學(xué);2015年

7 鄭海彬;一種面向MAPREDUCE的DATASHUFFLE的優(yōu)化方法[D];蘇州大學(xué);2015年

8 趙曉寒;輪換步長PSO算法及SMVSC參數(shù)優(yōu)化[D];沈陽理工大學(xué);2015年

9 安豐洋;基于無線網(wǎng)絡(luò)的廣播算法研究[D];曲阜師范大學(xué);2015年

10 李智明;基于改進(jìn)FastICA算法的混合語音盲分離[D];上海交通大學(xué);2015年

，

本文編號：1846950