Research On Generation Algorithm Of Scale-free Networks

Scale-free network refers to the topology of the degree of vertex obeying the poisson distribution.With the popularity of the modern information technology,large scale data graphs are increasingly applied to social networks and other realistic scenes,and the majority of real world data graph structure meet the large scale characteristics of scale-free networks.Therefore,the performance of the graph data processing algorithms can be verified by processing gigantic scale-free network data.However,there are some problems with the existing gigantic scale-free network construction methods such as low efficiency and poor scalability.In this paper,we aim to study the efficient generation method of gigantic scale-free network,the details are as follows:First of all,aiming at the inefficiency of the existing methods in generating scale-free networks,a gigantic scale-free network generation algorithm based on BA model and the corresponding network graph data storage structure RWBT is proposed.The corresponding traversal strategy is designed to improve the efficiency of the algorithm and optimize the deletion operation of nodes,by interchanging the node serial number instead of deleting buckets so as to reduce the frequency of updating the tree,It solves the inefficient problem caused by repeated traversing nodes when dealing with large scale data graph in memory.Secondly,in this paper we propose a k-tree index structure based on RWBT structure called RWKT,and furtherly improves the storage structure of the data graph and the corresponding node traversal strategy.Sorting the internal nodes of k-tree structure reduces the number of redundant comparisons,so as to optimize the efficiency of algorithm further.Finally,based on different parameters of the algorithms is discussed in this paper to set,the experiment verify the efficiency and scalability of the algorithm respectively from the running time and the number of atomic operation aspects of an in-depth comparison.The experimental results further verify the efficiency and scalability of the algorithms.