An Optimized Partitioning Algorithm for Complex Network Based on Social Simulations on Cluster Computing Platform

Partitioning is regarded as one of the most important issues which seriously influence the performance of the network-based social simulation on cluster computing platform. Partitioning algorithms based on computing a k-way partitioning of undirected graph is an enabling technology for parallel simulation as it could provide the effective decomposition of the computations. Unfortunately, since the scale-free network topology, which is a common characteristic in the network-based social simulations, new challenges are imposed to the graph partitioning algorithms. While background load of hosts causes unbalancing constraints associated with the vertices, currently partitioning algorithms based on k-way partitioning of undirected graph may produce poor-quality solutions and also require more running time and memories. This paper formalizes the partitioning problem statement of the network-based social simulation, and proposes a new partitioning algorithm for the power-law graphs. According to the algorithm, the hub nodes in the graph are filtered out and assigned to the partitions firstly; and then the k-way partitioning problem could be transformed into a minimum cost assignment problem which can obtain partitions with unbalancing constraints. This partitioning algorithm could find a solution with value at most three times the optimal value and can be executed in time O((k!+1)·kn). The experiments demonstrate that the algorithm is efficient.