大規(guī)模網(wǎng)絡(luò)零模型的高效量化評估策略研究
發(fā)布時間：2018-07-25 09:25
【摘要】：在復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域,為了觀察網(wǎng)絡(luò)各方面所具備的拓?fù)涮匦?人們通常需要生成相應(yīng)的零模型將二者進行比較,零模型在確定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中扮演著非常重要的角色。大規(guī)模網(wǎng)絡(luò)背景下采用隨機置亂算法構(gòu)建零模型將耗費大量的時間,目前尚未有學(xué)者對該算法實現(xiàn)優(yōu)化加速。另外,對于隨機置亂的次數(shù)到底應(yīng)該達(dá)到怎樣的規(guī)模才恰到好處,其與網(wǎng)絡(luò)的規(guī)模及拓?fù)涮匦灾g的關(guān)系如何,進而如何評估零模型是否足夠好,人們還未做過量化的研究。本文為了對零模型進行高效評估,將隨機置亂算法移植到GPU上進行,為了解決并行置亂對零模型有效性的影響,提出了一種基于隨機分配的隨機置亂算法(PRABPA)。針對規(guī)模大到GPU顯存無法一次性加載的網(wǎng)絡(luò),在PRABPA算法的基礎(chǔ)上,利用數(shù)據(jù)分組思想,提出了一種基于分組加載的隨機置亂算法(PRABPL),并保證了零模型整體的隨機性。通過對不同規(guī)模的實際網(wǎng)絡(luò)進行實驗,結(jié)果表明相比于串行隨機置亂算法,本文提出的PRABPA算法和PRABPL算法在保證零模型有效性及隨機化程度的同時,在構(gòu)建零模型的效率上得到了大幅提升。在此基礎(chǔ)上,本文通過對零模型構(gòu)建過程進行分析,發(fā)現(xiàn)通常置亂次數(shù)方式的設(shè)定不利于對零模型的評估,提出了成功置亂次數(shù)這一概念,將通常零模型構(gòu)建過程中的嘗試置亂次數(shù)更換為成功置亂次數(shù)并應(yīng)用到0階、1階、2階零模型構(gòu)建算法中,通過一系列復(fù)雜網(wǎng)絡(luò)拓?fù)渲笜?biāo)對零模型進行評估實驗,結(jié)果表明這一設(shè)定方式明確了使零模型趨于穩(wěn)定的置亂次數(shù),為研究學(xué)者在應(yīng)用零模型過程中提供了很好的參考價值。
[Abstract]:In the research field of complex networks, in order to observe the topological characteristics of various aspects of the network, people usually need to generate the corresponding zero model to compare the two models. The zero model plays a very important role in determining the topology structure of the network. It will take a lot of time to construct zero model by random scrambling algorithm under the background of large-scale network. There are no scholars to accelerate the optimization of the algorithm. In addition, no quantitative research has been done on what size random scrambling should be, the relationship between random scrambling and network size and topological characteristics, and how to evaluate whether the zero model is good enough. In order to evaluate zero model efficiently, the random scrambling algorithm is transplanted to GPU. In order to solve the effect of parallel scrambling on the validity of zero model, a random scrambling algorithm based on random assignment (PRABPA).) is proposed in this paper. Based on the PRABPA algorithm and the idea of data grouping, a random scrambling algorithm (PRABPL),) based on packet loading is proposed to guarantee the randomness of the whole zero model for the network whose scale is so large that the GPU memory can not be loaded at one time. The experimental results show that compared with the serial random scrambling algorithm, the proposed PRABPA algorithm and the PRABPL algorithm not only guarantee the validity and randomization of the zero model, but also guarantee the randomization of the zero model. The efficiency of building zero model has been greatly improved. On this basis, through the analysis of the process of zero model construction, it is found that the usual setting of scrambling times is not conducive to the evaluation of zero model, and the concept of successful scrambling times is put forward. The number of attempts in the process of constructing zero model is replaced by the number of successful scrambling, and applied to the algorithm of building zero model of order 0 or order 1 or 2. The evaluation experiment of zero model is carried out through a series of complex network topology indexes. The results show that this method makes clear the scrambling times that make the zero model stable, and provides a good reference value for the researchers in the process of applying the zero model.
【學(xué)位授予單位】：北京化工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
本文編號：2143374
[Abstract]:In the research field of complex networks, in order to observe the topological characteristics of various aspects of the network, people usually need to generate the corresponding zero model to compare the two models. The zero model plays a very important role in determining the topology structure of the network. It will take a lot of time to construct zero model by random scrambling algorithm under the background of large-scale network. There are no scholars to accelerate the optimization of the algorithm. In addition, no quantitative research has been done on what size random scrambling should be, the relationship between random scrambling and network size and topological characteristics, and how to evaluate whether the zero model is good enough. In order to evaluate zero model efficiently, the random scrambling algorithm is transplanted to GPU. In order to solve the effect of parallel scrambling on the validity of zero model, a random scrambling algorithm based on random assignment (PRABPA).) is proposed in this paper. Based on the PRABPA algorithm and the idea of data grouping, a random scrambling algorithm (PRABPL),) based on packet loading is proposed to guarantee the randomness of the whole zero model for the network whose scale is so large that the GPU memory can not be loaded at one time. The experimental results show that compared with the serial random scrambling algorithm, the proposed PRABPA algorithm and the PRABPL algorithm not only guarantee the validity and randomization of the zero model, but also guarantee the randomization of the zero model. The efficiency of building zero model has been greatly improved. On this basis, through the analysis of the process of zero model construction, it is found that the usual setting of scrambling times is not conducive to the evaluation of zero model, and the concept of successful scrambling times is put forward. The number of attempts in the process of constructing zero model is replaced by the number of successful scrambling, and applied to the algorithm of building zero model of order 0 or order 1 or 2. The evaluation experiment of zero model is carried out through a series of complex network topology indexes. The results show that this method makes clear the scrambling times that make the zero model stable, and provides a good reference value for the researchers in the process of applying the zero model.
【學(xué)位授予單位】：北京化工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【參考文獻(xiàn)】
相關(guān)期刊論文 前3條
1 邢星星;趙國興;駱祖瑩;方浩;;基于GPU的全源最短路徑算法[J];計算機科學(xué);2012年03期
2 劉欣;王非;;兩種GPU上改進的最短路徑算法[J];計算機應(yīng)用研究;2014年05期
3 王鑫廳;侯亞麗;梁存柱;王煒;劉芳;;基于不同零模型的點格局分析[J];生物多樣性;2012年02期
，本文編號：2143374
本文鏈接：http://www.lk138.cn/kejilunwen/yysx/2143374.html
最近更新
教材專著
