Contents
Abstract
Acknowledgements
Contents
List of Tables
List of Figures
List of Abbreviations xiii
1 Introduction
1.1 Problem Statement
1.2 Proposed Research Approach
1.3 Thesis Organization
2 Literature Review
2.1 Graph Processing frameworks
2.2 BFS for Searching Large Graphs
2.3 Reducing Inter-node Communication
2.3 Summary
3 Achieving Optimal Inter-node Communication in Graph Partitioning Using RS method and Breadth First Search
3.1 Proposed Random Selection Approach
3.2 Implementation of Proposed Approach
3.3 Experimental Results
3.3.1 Results for SSSP
3.3.1.1 Powerlaw Graph
3.3.1.2 Random near K-regular Graph (with Low Degree)
3.3.1.3 Random near K-regular Graph (with High Degree)
3.3.2 Further Analysis in case of SSSP
3.3.3 Results for PR
3.3.3.1 Powerlaw Graph
3.3.3.2 Random near K-regular Graph (with Low Degree)
3.3.3.4 Random near K-regular Graph (with High Degree)
3.3.4 Further Analysis in case of PR
3.4 Discussion
3.4.1 Statistical Analysis
3.5 Summary
4 Partitioning Large Graphs using Particle Swarm Optimization with Breadth First Search
4.1 Proposed Approach
4.1.1 Particle Swarm Optimization
4.1.2 Proposed PSO Approach
4.2 Implementation
4.3 Experimental Results
4.3.1 Results for SSSP
4.3.1.1 Powerlaw Graph
4.3.1.2 Random near K-regular Graph (with Low Degree)
4.3.1.3 Random near K-regular Graph (with High Degree)
4.3.2 Results for PR
4.3.2.1 Powerlaw Graph
4.3.2.2 Random near K-regular Graph (with Low Degree)
4.3.2.3 Random Near K-regular Graph (with High Degree)
4.4 Comparison results of RS-BFS amd PSO-BFS algorithms for SSSP
4.4.1 Powerlaw graph
4.4.2 Random Near K-regular Graph (with Low Degree
4.4.3 Random Near K-regular Graph (with High Degree)
4.5 Comparison results of RS-BFS amd PSO-BFS algorithms for PR
4.5.1 Powerlaw graph
4.5.2 Random Near K-regular Graph (with Low Degree)
4.5.3 Random Near K-regular Graph (with High Degree)
4.6 Discussion
4.7 Summary
5 Conclusions and Future Work
5.1 Future Work
References
Appendix-A
A.1 Source Code for PSO Algorithm
A.2 Source Code for RS method
