基于GPU的大尺度网络零模型分组生成并行算法

GPU-based parallel algorithm for partitionedly generating null model of large-scale networks

为解决生成大尺度网络的零模型时间效率较低的问题,利用数据分组思想,针对生成0阶、1阶、2阶网络零模型的随机置乱算法提出基于GPU的并行化实现。并行化过程中,设计不重复分配原则,以及存在性替换、重复性替换策略避免无效置乱。基于常用的网络拓扑指标以及网络随机化程度,验证并行算法的有效性,验证结果表明,并行的分组置乱算法相比传统的串行算法提高了时间效率,针对GPU显存无法一次性容纳的大尺度网络,能快速生成其相应的零模型,为大尺度网络零模型的研究提供了一种高效的解决方案。

To solve the problem of low time efficiency of generating null model for large scale networks,the random permutation algorithms for partitionedly generating null model of 0order,1order and 2order were parallelly implemented on GPU.The principle of unique distribution,the strategies of replacement on existence and duplication were designed to avoid invalid permutations.In terms of some commonly used network topology metrics and degree of randomization,the effectiveness of the parallel algorithms was verified.The experimental results show that,the parallel algorithms on GPU greatly improve time efficiency compared to serial ones.By using the parallel algorithms proposed,null models for large scale networks that can not be wholly loaded to GPU can be generated fast.In this way,an efficient solution for research on null models of large scale networks is proposed.