中文摘要：

负载划分是决定集群计算环境下基于复杂网络的并行社会学仿真性能的核心因素之一．由于背景负载等因素的影响，集群系统中往往需要根据实际可用计算资源非均匀分配仿真任务，而现有针对无标度特性拓扑结构的并行仿真负载划分算法无法适应集群环境下计算负载非均匀划分的需求．针对这一问题，提出了一个基于集散节点聚合的负载划分算法，将集群计算环境下基于复杂网络的并行社会学仿真负载划分优化问题转换为一个二部图最小代价赋值问题，最终得到仿真任务到计算节点的分配方案．理论证明该算法近似解与全局最优解比值不超过3，时间复杂度不超过O（（k!＋1）·kn）．实验结果表明该负载划分算法相比现有算法平均提高18．8％的仿真运行性能，证明了该算法的有效性和实用性．

英文摘要：

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.