  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.

Data Structures and Algorithms;Social and Information Networks;Applications