Change search
ReferencesLink to record
Permanent link

Direct link
A Distributed Algorithm for Large-Scale Graph Partitioning
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. Computer System Lab. (CSL), SICS Swedish, Sweden.
Computer System Lab. (CSL), SICS Swedish, Sweden.
KTH, School of Electrical Engineering (EES), Communication Networks.
MTA SZTE Research Group on AI, Hungarian Academy of Sciences and 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, 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
ACM, 2015. Vol. 10, no 2, 12
National Category
Engineering and Technology
Research subject
Computer Science
URN: urn:nbn:se:kth:diva-170128DOI: 10.1145/2714568ScopusID: 2-s2.0-84930973235OAI: diva2:827364
End to End Clouds
Swedish Foundation for Strategic Research

QC 20150629

Available from: 2015-06-26 Created: 2015-06-26 Last updated: 2015-06-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Rahimian, FatemehPayberah, Amir H.Girdzijauskas, SarunasHaridi, Seif
By organisation
Software and Computer systems, SCSCommunication Networks
In the same journal
ACM Transactions on Autonomous and Adaptive Systems
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
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

Altmetric score

Total: 33 hits
ReferencesLink to record
Permanent link

Direct link