大规模网络零模型的高效量化评估策略研究
发布时间：2018-07-25 09:25
【摘要】：在复杂网络研究领域,为了观察网络各方面所具备的拓扑特性,人们通常需要生成相应的零模型将二者进行比较,零模型在确定网络的拓扑结构中扮演着非常重要的角色。大规模网络背景下采用随机置乱算法构建零模型将耗费大量的时间,目前尚未有学者对该算法实现优化加速。另外,对于随机置乱的次数到底应该达到怎样的规模才恰到好处,其与网络的规模及拓扑特性之间的关系如何,进而如何评估零模型是否足够好,人们还未做过量化的研究。本文为了对零模型进行高效评估,将随机置乱算法移植到GPU上进行,为了解决并行置乱对零模型有效性的影响,提出了一种基于随机分配的随机置乱算法(PRABPA)。针对规模大到GPU显存无法一次性加载的网络,在PRABPA算法的基础上,利用数据分组思想,提出了一种基于分组加载的随机置乱算法(PRABPL),并保证了零模型整体的随机性。通过对不同规模的实际网络进行实验,结果表明相比于串行随机置乱算法,本文提出的PRABPA算法和PRABPL算法在保证零模型有效性及随机化程度的同时,在构建零模型的效率上得到了大幅提升。在此基础上,本文通过对零模型构建过程进行分析,发现通常置乱次数方式的设定不利于对零模型的评估,提出了成功置乱次数这一概念,将通常零模型构建过程中的尝试置乱次数更换为成功置乱次数并应用到0阶、1阶、2阶零模型构建算法中,通过一系列复杂网络拓扑指标对零模型进行评估实验,结果表明这一设定方式明确了使零模型趋于稳定的置乱次数,为研究学者在应用零模型过程中提供了很好的参考价值。
[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.
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：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.
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【参考文献】
相关期刊论文 前3条
1 邢星星;赵国兴;骆祖莹;方浩;;基于GPU的全源最短路径算法[J];计算机科学;2012年03期
2 刘欣;王非;;两种GPU上改进的最短路径算法[J];计算机应用研究;2014年05期
3 王鑫厅;侯亚丽;梁存柱;王炜;刘芳;;基于不同零模型的点格局分析[J];生物多样性;2012年02期
，本文编号：2143374
本文链接：https://www.wllwen.com/kejilunwen/yysx/2143374.html
