Research On Stratergy Of Efficient Quantitative Assessment Of Null Model Of Large Scale Networks

Inthe filed of complex networks, in order to observe of the topological characteristics of network in various aspects, people usually need to build the corresponding null model and compare these two objects. Null model plays a very important role in determining the topology of the network. In the background of large-scale networks, using random scrambling algorithm to generate the null model will cost a lot of time, yet there are no scholars has accelerated or optimized the algorithm. In addition, the random scrambling times should be in what scale is just right, what’s the relationship among null model, network’s size and topological characteristics and how to evaluate whether the null model is good enough, people have not yet done quantitative research on the above problems.In order to efficiently evaluate the null model, the random scrambling algorithm was transferred to GPU. To solve the effect of parallel scrambling on the effectiveness of null model, a random scrambling algorithm based on random assignment(PRABPA) was proposed. For those networks whose sizes are too large to be loaded to the GPU memory at one time, the idea of data partition was used, on the basis of PRABPA, a random parallel randomized algorithm based on partition loaded(PRABPL) was proposed, and the randomness of the whole null model was guaranteed. Through experiment on actual networks of different scales, the results show that the PRABPA and the PRABPL proposed in this paper not only can ensure null model’s effectiveness and randomized degree, but also greatly improved the efficiency of constructing null model compared with serial algorithms.On this basis, byanalyzing the constructing process of the null model we found that the usual way of setting scrambling times was not conducive to the assessment of null model, so the concept of successful scrambling times was proposed, and attempted scrambling times was replaced with it and applied to 0K, 1K and 2K null model’s constructing process. By using a series of complex network topological metrics to do the quantitative evaluation experiment for null model, the experimental results show that this approach makes the scrambling times that can make null model become stable clear, and provide a good reference for the application of null models for researchers.