Rahimian, Fatemeh and Payberah, Amir H. and Girdzijauskas, Sarunas and Jelasity, Mark and Haridi, Seif (2013) *Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning.* [SICS Report]

| PDF 301Kb |

## Abstract

Balanced graph partitioning is a well known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems such as the optimal storage of large sets of graph-structured data over several hosts, or identifying clusters in on-line social networks. In such very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. In this paper, we propose a distributed graph partitioning algorithm, called Ja-be-Ja1. The algorithm is massively parallel: each graph node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known. Strict synchronization is not required. These features allow Ja-be-Ja to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by Ja-be-Ja is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks Ja-be-Ja outperforms Metis.

Item Type: | SICS Report |
---|---|

Uncontrolled Keywords: | graph partitioning; distributed algorithm; load balancing |

ID Code: | 5473 |

Deposited By: | Vicki Carleson |

Deposited On: | 22 Mar 2013 16:00 |

Last Modified: | 22 Mar 2013 16:00 |

Repository Staff Only: item control page