• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Improving quality of graph partitioning using multi-level optimization

Programming and Computer Software. 2015. Vol. 41. No. 5. P. 302-306.
S. D. Kuznetsov, Turdakov D. Y., Пастухов Р. К., Коршунов А. В.

Graph partitioning is required for solving tasks on graphs that need to be distributed over disks or computers. This problem is well studied, but the majority of the results on this subject are not suitable for processing graphs with billions of nodes on commodity clusters, since they require shared memory or lowlatency messaging. One of the approaches suitable for cluster computing is the balanced label propagation, which is based on the label propagation algorithm. In this work, we show how multi-level optimization can be used to improve quality of the partitioning obtained by means of the balanced label propagation algorithm.