SODA

Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning

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]

[img]
Preview
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