Compress And Accelerate Layout Algorithm For Large-Scale Networks Research

One of the ways to study complex networks is making them visualized. With the advent of Web2.0 era and the big data era, the scales of complex networks are becoming larger. People need to express and understand the big data more exactly so that they can explore the useful information from the data further. As it is difficult for the traditional way to meet the requirements, visualizing of complex networks is becoming a major way to understand and study the big data. However, the rapid growth of data scale brings the new challenge to complex network visualization in the layout effect and computing efficiency.Because of the layout aesthetics and some other reasons, the FDA(Force-Directed Algorithm) is the most widely used. Thus, we aim at improving the FDA from two aspects. In the aspect of optimizing the layout effect, we propose three algorithms for compressing complex network basing on articulation points, betweenness centrality and the k-core concept, respectively. In the compression algorithms, the nodes are categorized into various sets and handled in different ways. In this way, the scales of networks decrease and the layout shows the network structure clearly from the macroscopic. In the aspect of algorithm efficiency, we migrate three parts of FDA:repulsive force, attraction force and updating coordinates onto GPU for the compressed network. It improves the efficiency of the algorithm greatly, which helps people getting the layout in a relatively short time.Finally, the definition of Information Content is proposed to measure the compression of networks quantitatively. After that, we analysis the experimental results and observe the change of the characteristics of the networks before and after compression. The results prove the correctness and effectiveness of the compression algorithms we proposed in GPU accelerating.