Streaming Balanced Graph Partitioning Algorithms for Random Graphs
Isabelle Stanton · 2012
The has been a recent explosion in the size of stored data, partially due to advances in storage technology, and partially due to the growing popularity of cloudcomputing and the vast quantities of data generated, motivates the need for streaming algorithms that can compute approximate solutions without full random access to all of the data. We address the problem of computing a balanced k-partitioning of a graph with only one pass over the data. Based on experimental results in [11] we analyze two variants of a randomized greedy algorithm, one that prefers the arg max and one that is proportional, on random graphs with embedded balanced k-cuts and theoretically bound the performance of each algorithms- the arg max algorithm is able to asymptotically recover the embedded k-cut, while, surprisingly, the proportional variant can not. 1