Method for partitioning large-scale static network based on graphics processor

Abstract

The invention discloses a method for partitioning a large-scale static network based on a graphics processor, which mainly aims to solve the problem that the existing network partitioning method is not suitable for partitioning a large-scale network and low in efficiency. The method comprises the following steps: by defining a result matrix S of network partitioning, transforming the operation ofrespectively calculating the characteristic vector and characteristic value of each sub-module in network partitioning into the operation of calculating the characteristic vector and characteristic value of the whole network; and according to the parallel computing architecture of the graphics processor, decomposing the calculation of the characteristic vector and the characteristic value in network partitioning into a plurality of basic calculations, so that the original huge dense matrix calculation is simplified to the computations between sparse matrixes and vectors. In the invention, through reasonably combining the basic calculations, memory space is saved, the consumption of data transmission is decreased, and the efficiency of network partitioning is effectively improved, so that the partitioning of an extra-large scale static network which is difficult to implement becomes possible.

Description

technical field [0001] The invention relates to the technical fields of computers and electronic information, in particular to a large-scale static network division method. Background technique [0002] Network models have received great attention in the fields of statistical physics and applied mathematics in recent years, and the concept of network has also been successfully applied to other fields, such as the Internet, social networks, and ecological networks. Network research includes the calculation of various attributes of the network, including small-world attributes, heavy-tailed distribution, and community structure; among them, the study of network community structure is of great significance to network research. For example, the study of social network community structure can help discover groups common interests and characteristics. The study of network community structure can help to understand the structure, function and topological relationship of the networ...

AI Technical Summary

Problems solved by technology

[0021] This method can provide more accurate results, and has strict theoretical proofs to ensure that the solution is optimal, but the implementation of the method is more complicated and cannot withstand the calculation of large-scale networks.

The complexity of the method is mainly manifested in the following two aspects: first, it involves the modular matrix B (G) The calculation of the eigenvalues, and when the network dimension is large, the calculation of the matrix eigenvalues ​​is huge, for example, when using the Jacobian iterative algorithm, the time complexity of each iteration is O(n 3 ); Second, in the process of continuously dividing the network into two parts, the size of the sub-block will change, and the continuity of sub-block subscripts cannot be guaranteed, so it is not conducive to the parallelization of the algorithm

Images