Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.ORCID iD: 0000-0003-4516-7317
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 Last updated: 2017-04-07Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Girdzijauskas, Sarunas
By organisation
Computer Systems LaboratorySICS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 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
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf