Parallel k-Way Partitioning Approach for Large Graphs

Abstract:

With the emergence of large social networks, such as Facebook and Twitter, graphs with millions to billions vertices are common. Instead of processing the network within a single machine, all the applications related are intended to be done in a distributed way using a cluster of commodity machines. In this paper, we study the parallel graph partitioning problem, which is the fundamental operation for large graphs. With the help of Hadoop/MapReduce, we propose a parallel k-way partitioning approach. Unlike the previous ones, which require enough memory to keep the whole graph data within, our novel approach breaks such limitations. Also, due to the distributed nature, it is easy to integrate our partitioning approach into existed parallel platforms. We conduct extensive experiments on real graphs and synthetic graphs. All the experimental results prove the effectiveness and efficiency of our approach.

• Periodical: Advanced Materials Research (Volumes 912-914)
• Pages: 1309-1312
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.912-914.1309
• Online since: April 2014
• Authors: Jin Xu*, Yu Zhong, Bo Peng
• Keywords: MapReduce, Parallel Graph Partitioning

References

[1] Facebook. http: /www. facebook. com.

[2] Twitter. http: /www. twitter. com.

[3] LinkedIn. http: /www. linkedin. com.

[4] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1): 359-392, (1999).

DOI: 10.1137/s1064827595287997

[5] B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Proc. of Supercomputing, (1995).

[6] F. Pellegrini and J. Roman. SCOTCH: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In HPCN, pages 493-498, (1996).

DOI: 10.1007/3-540-61142-8_588

[7] Kale, Laxmikant V., et al. Message-driven parallel language runtime design and optimizations for multicore-based massively parallel machines., (2012).

[8] LaSalle, Dominique, and George Karypis. Multi-Threaded Graph Partitioning., 27th IEEE International Parallel & Distributed Processing Symposium. (2013).

DOI: 10.1109/ipdps.2013.50

[9] Sanders, Peter, and Christian Schulz. Distributed evolutionary graph partitioning., arXiv preprint arXiv: 1110. 0477 (2011).

[10] Mapreduce. In http: /en. wikipedia. org/wiki/MapReduce.

[11] Hadoop: An open-source implementation of mapreduce. In http: /hadoop. apache. org.

[12] D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In Proceedings of SDM '04, (2004).