Change search
ReferencesLink to record
Permanent link

Direct link
Distributed balanced edge-cut partitioning of large graphs having weighted vertices
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Large scale graphs are sometimes too big to store and process on a single machine. Instead, these graphs have to be divided into smaller parts and distributed over several machines, while minimizing the dependency between the different parts. This is known as the graph partitioning problem, which has been shown to be NP-complete. The problem is well studied, however most solutions are either not suitable for a distributed environment or unable to do balanced partitioning of graphs having weighted vertices. This thesis presents an extension to the distributed balanced graph partitioning algorithm JA-BE-JA, that solves the balanced partitioning problem for graph having weighted vertices. The extension, called wJA-BE-JA, is implemented in both the Spark framework and in Scala. The two main contributions of this report are the algorithm and a comprehensive evaluation of its performance, including a comparison with the recognized METIS graph partitioner. The evaluation shows that a random sampling policy in combination with the simulated annealing technique gives good results. It further shows that the algorithm is competitive to METIS, as the extension outperforms METIS in 17 of 20 tests.

Place, publisher, year, edition, pages
TRITA-ICT-EX, 2015:46
URN: urn:nbn:se:kth:diva-175145OAI: diva2:860026
Available from: 2015-10-09 Created: 2015-10-09 Last updated: 2015-10-09Bibliographically approved

Open Access in DiVA

No full text

By organisation
School of Information and Communication Technology (ICT)

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

Total: 84 hits
ReferencesLink to record
Permanent link

Direct link