JIITA, vol. 2, no. 2, pp.84-89, Jun, 2018
DOI: soon
Partitioning Large Graphs using Particle Swarm Optimization with Breadth First Search
Srimanth Gadde 1), Robert C. Green II 2,*), William Acosta 3), Vijay Devabhaktuni 1)
1) University of Toledo, Toledo, OH, USA
2) Bowling Green State University, Bowling Green, OH, USA
3) DISH Network, Englewood, CO, USA
Abstract: Processing large graph datasets represents an increasingly important area in computing research and applications. The size of many graph datasets has increased beyond the processing capacity of a single computing node, necessitating distributed approaches. Processing over a distributed system of nodes leads to an inter-partition communication cost problem, negatively affecting the system performance. Previously proposed graph partitioning approaches minimize the inter-partition communication on large graphs, yet require high computation overhead. To address this problem, a robust algorithm combining Particle Swarm Optimization (PSO) with Breadth First Search (BFS) is implemented, which does not require high computation overhead, reduces the interpartition communication, and maximizes intra-partition communication by achieving an appropriate balance partition. In the first phase (PSO Selection), a core set of vertices are selected and assigned to the computing nodes. In the second phase, the graph is partitioned by placing the remaining nodes through the use of BFS. Experimental results show graph intra-partition performance for canonical graphs representative of realworld data is improved up to 50% in case of Powerlaw graph, up to 33% in case of Random near K-regular graph (with low degree), and up to 16% in case of Random near K-regular graph (with high degree). (Abstract)
Keyword: graph partitioning; particle swarm optimization; breadth first search; inter-partition communication
Full Paper: