【摘要】：在復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域,為了觀察網(wǎng)絡(luò)各方面所具備的拓?fù)涮匦?人們通常需要生成相應(yīng)的零模型將二者進(jìn)行比較,零模型在確定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中扮演著非常重要的角色。大規(guī)模網(wǎng)絡(luò)背景下采用隨機(jī)置亂算法構(gòu)建零模型將耗費(fèi)大量的時間,目前尚未有學(xué)者對該算法實(shí)現(xiàn)優(yōu)化加速。另外,對于隨機(jī)置亂的次數(shù)到底應(yīng)該達(dá)到怎樣的規(guī)模才恰到好處,其與網(wǎng)絡(luò)的規(guī)模及拓?fù)涮匦灾g的關(guān)系如何,進(jìn)而如何評估零模型是否足夠好,人們還未做過量化的研究。本文為了對零模型進(jìn)行高效評估,將隨機(jī)置亂算法移植到GPU上進(jìn)行,為了解決并行置亂對零模型有效性的影響,提出了一種基于隨機(jī)分配的隨機(jī)置亂算法(PRABPA)。針對規(guī)模大到GPU顯存無法一次性加載的網(wǎng)絡(luò),在PRABPA算法的基礎(chǔ)上,利用數(shù)據(jù)分組思想,提出了一種基于分組加載的隨機(jī)置亂算法(PRABPL),并保證了零模型整體的隨機(jī)性。通過對不同規(guī)模的實(shí)際網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn),結(jié)果表明相比于串行隨機(jī)置亂算法,本文提出的PRABPA算法和PRABPL算法在保證零模型有效性及隨機(jī)化程度的同時,在構(gòu)建零模型的效率上得到了大幅提升。在此基礎(chǔ)上,本文通過對零模型構(gòu)建過程進(jìn)行分析,發(fā)現(xiàn)通常置亂次數(shù)方式的設(shè)定不利于對零模型的評估,提出了成功置亂次數(shù)這一概念,將通常零模型構(gòu)建過程中的嘗試置亂次數(shù)更換為成功置亂次數(shù)并應(yīng)用到0階、1階、2階零模型構(gòu)建算法中,通過一系列復(fù)雜網(wǎng)絡(luò)拓?fù)渲笜?biāo)對零模型進(jìn)行評估實(shí)驗(yàn),結(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

【參考文獻(xiàn)】

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

1 邢星星;趙國興;駱祖瑩;方浩;;基于GPU的全源最短路徑算法[J];計算機(jī)科學(xué);2012年03期

2 劉欣;王非;;兩種GPU上改進(jìn)的最短路徑算法[J];計算機(jī)應(yīng)用研究;2014年05期

3 王鑫廳;侯亞麗;梁存柱;王煒;劉芳;;基于不同零模型的點(diǎn)格局分析[J];生物多樣性;2012年02期

，

本文編號：2143374