Graph Partition Based Parallel Computing For Complex Network

Since the1980s, the study of complex systems has gradually attracted the attentionof many researchers and has become a popular research field. It is considered to be animportant breakthrough to resolve the current difficulties appearing in various fields. Thecomplex network is an important tool for studying complex systems. The structure ofany system can be described by a network, where the nodes represent subsystems andthe edges represent links between subsystems. In the past few years, researchers havefound the fact that, the network structure of complex systems in different areas are sub-ject to certain basic rules, which appear to be equally applicable to the networks of cells,computers, languages and human societies. The study of complex networks adopts thebottom-up research strategy, which is different from traditional decomposition method.Theoverallbehaviorsemergingfromnonlinearlocalinteractionareverycomplexincom-plex networks. The number of basic units in the system or subsystem is enormous, oftenreaching hundreds of thousands or even hundreds of millions. This makes the study ofcomplex networks have to resort to an efficient computational tool to achieve real-time,large-scale simulation. Parallel computing technology is one of the most mature, the mostpopular and the most feasible accelerating technology for high performance computing.Thus accelerating complex network computing by parallel computing has great signifi-cance. And how to allocate tasks in each processor is the key factor of parallel computingperformance. Graph partitioning technology is an effective method of solving this prob-lem. However, the current graph partitioning technology partitions the graph staticallyand does not pay any attention to the dynamic characteristics of complex network, nor theproperty of the scale-free and community of complex network. If the above properties aretaken into account and optimization is employed, the performance of graph partitioningof complex network will be well improved. In order to improve the performance of paral-lel computing of complex network, we take the graph partition as entry point to studyingparallel computing technology of complex network. The innovations and contributionsof this paper are listed as follows.1. Setting up the complex networks graph partitioning theory based on α property.The dynamic characteristic is one of the most important characteristics of the complexnetwork. Traditional graph partitioning theory considers only static graphs, and therefore it is not able to handle complex networks. To solve this problem, our first work is to pro-pose the describing theory of complex network graph and graph partitioning theory basedon α property. All allocation problems can be unified in modeling and research usingα property theory, which facilitates the reusing of the existed results in other allocationfield. Thus, α property theory has importance theoretical significance. The partitioningproblem can be formulated by integrating the theory of description of complex networkandthetheoryofpartitioningcomplexnetworkbasedonαproperty. Thetheoryestablish-es the theoretical basis for allocating tasks intelligently in parallel computing of complexnetwork.2. Presenting multi-level and top-down complex network graph partitioning algo-rithm under the load balancing priority. Partitioning result of complex network graphand the performance of the partitioning algorithm directly affect the performance of par-allel computing of complex network. To resolve the local optimal problem and storageoverhead problem of traditional multi-level partition algorithm, the paper presents a top-down multi-level partitioning algorithm framework, and gives the top-down multi-levelpartitioning algorithm, ABPG, which is the first top-down multi-level algorithm for par-titioning complex network graph to my best of my knowledge. The algorithm can takeadvantage of the global community information to coarsen the network to reduce the sizeof the graph partitioning problem, and adopt top-down strategy to reduce storage over-head. The experiments show that, compared with traditional algorithms, results of ABPGalgorithm improves9.2%on average, and under the load balancing priority constraints,the memory overhead is reduced to be only20.3%of the traditional algorithms.3. Presenting a community support tree based partition algorithm of complex net-work graph under the communication overhead priority. Considering the particularityof communication intensive application, the partition problem of communication over-head priority is studied in this paper. A community support tree based partition algorithmnamed TBP is presented, which constructs community support tree of complex network,and reduces the search overhead to improve the performance by using the symmetry ofcommunity support tree. The experiments show that, under the communication overheadpriority constraints, results of TBP algorithm improve10.7%in performance on averagewhen compared with traditional algorithms.4. Validating the feasibility and efficiency of the algorithms presented in this paper using the neural network parallel simulation. In order to validate the performance of thepartition algorithms, this paper chooses an important application of complex network—brainneuralnetworktostudy. Twotypesofneural networkmodel areselectedforaparal-lel implementation, representing the priority of load balance applications and the priorityof communication overhead applications, respectively. This paper compares the paral-lel partitioning performance of the original graph partitioning method and the algorithmspresented in this paper. The experimental results show that the complex network graphpartitioning algorithms presented in this paper can effectively improve the performanceof parallel computing of complex network.