Predictive partitioning for efficient BFS traversal in social networks

In this paper we show how graph structure can be used to drastically reduce the computational bottleneck of the Breadth First Search algorithm (the foundation of many graph traversal techniques). In particular, we address parallel implementations where the bottleneck is the number of messages between processors emitted at the peak iteration. First, we derive an expression for the expected degree distribution of vertices in the frontier of the algorithm which is shown to be highly skewed. Subsequently, we derive an expression for the expected message along an edge in a particular iteration. This skew suggests a weighted, iteration based, partition would be advantageous. Employing the METIS algorithm we then show empirically that such partitions can reduce the message overhead by up to 50% in some particular instances and in the order of 20% on average. These results have implications for graph processing in multiprocessor and distributed computing environments.