Abstract: 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.