Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
A distributed algorithm for large-scale graph partitioning
RISE, Swedish ICT, SICS. KTH Royal Institute of Technology, Sweden.
RISE, Swedish ICT, SICS.ORCID iD: 0000-0002-2748-8929
KTH Royal Institute of Technology, Sweden.
Hungarian Academy of Sciences, Hungary; University of Szeged, Hungary.
Show others and affiliations
2015 (English)In: ACM Transactions on Autonomous and Adaptive Systems, ISSN 1556-4665, E-ISSN 1556-4703, Vol. 10, no 2, article id 12Article in journal (Refereed) Published
Abstract [en]

Balanced graph partitioning is an NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems, including the optimal storage of large sets of graph-structured data over several hosts. However, in 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 article, we propose a fully distributed algorithm called Ja-be-Ja that uses local search and simulated annealing techniques for two types of graph partitioning: edge-cut partitioning and vertex-cut partitioning. The algorithm is massively parallel: There is no central coordination, each vertex is processed independently, and only the direct neighbors of a vertex and a small subset of random vertices in the graph need to be known locally. 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 show that the minimal edge-cut value empirically 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. We also show that Ja-be-Ja computes very low vertex-cuts, which are proved significantly more effective than edge-cuts for processing most real-world graphs.

Place, publisher, year, edition, pages
Association for Computing Machinery , 2015. Vol. 10, no 2, article id 12
Keywords [en]
Distributed algorithm, Edge-cut partitioning, Graph partitioning, Load balancing, Simulated annealing, Vertex-cut partitioning, Algorithms, Computational complexity, Data handling, Digital storage, Network management, Parallel algorithms, Resource allocation, Balanced graph partitioning, Centralized algorithms, Edge cuts, Graph structured data, Simulated annealing techniques, State-of-the-art algorithms, Vertex-cut, Graph theory
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:ri:diva-41882DOI: 10.1145/2714568Scopus ID: 2-s2.0-84930973235OAI: oai:DiVA.org:ri-41882DiVA, id: diva2:1377786
Available from: 2019-12-12 Created: 2019-12-12 Last updated: 2019-12-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Payberah, AmirHaridi, Seif

Search in DiVA

By author/editor
Payberah, AmirHaridi, Seif
By organisation
SICS
In the same journal
ACM Transactions on Autonomous and Adaptive Systems
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
v. 2.35.9