Change search
ReferencesLink to record
Permanent link

Direct link
Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
RISE, Swedish ICT, SICS. Computer Systems Laboratory.
Show others and affiliations
Number of Authors: 5
2013 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2013, 7.
Series
SICS Technical Report, ISSN 1100-3154 ; 2013:03
Keyword [en]
graph partitioning, distributed algorithm, load balancing
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-24165OAI: oai:DiVA.org:ri-24165DiVA: diva2:1043244
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(301 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 301 kBChecksum SHA-512
0cde490ef5814413d0b3c17c7301d5faf68a80977664a6aa2820980af78d419bee763720197617c6c72333766e3ee9eb9888b61a94d1758b2b794760abbda48d
Type fulltextMimetype application/pdf

By organisation
SICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link