关键词: 社交网络, 图论, 图分割, 分布式计算, 负载均衡

Abstract: Massive data from social networks contains a wealth of information. Among various methods to mine such information, graph theory is an attractive tool. With the increase of the volume of the graph data, distributed computation of graphs becomes an effective means to deal with large-scale graph data. In distributed graph computation, the time consumed in communications contributes significantly to the overall computation time. A well-designed graph partitioning algorithm can effectively reduce the communications as well as achieve load balancing, thus improving the efficiency of distributed graph computation. Typical examples include the Metis graph partitioning algorithm. However, existing graph partitioning algorithms to deal with social network graphs which involve non-equilibrium graph data will result in imbalance between subgraph communications, thus affecting the computational efficiency. To solve this problem, a new graph partitioning method, namely communication balanced label switching method, is presented. It behaves with three unique features: consistent subgraph scale, reduction of the communications required for the whole graph computation, and balanced communications between subgraphs. Experimental results show that in comparison with existing partitioning algorithms such as Metis, the graph partitioning method presented in this paper improves the computational time performance by 6%~30% for various data sets and cluster configurations. These results highlight the effectiveness of the presented method.

Key words: social network, graph theory, graph partitioning, distributed computing, load balancing