Advanced Search
    Yao Yiping and Zhang Yingxing. An Optimized Partitioning Algorithm for Complex Network Based on Social Simulations on Cluster Computing Platform[J]. Journal of Computer Research and Development, 2011, 48(9): 1759-1767.
    Citation: Yao Yiping and Zhang Yingxing. An Optimized Partitioning Algorithm for Complex Network Based on Social Simulations on Cluster Computing Platform[J]. Journal of Computer Research and Development, 2011, 48(9): 1759-1767.

    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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return