Traversing massive graphs as efficiently as possible is essential for many applications. Many common operations on graphs, such as calculating the distance between two nodes, are based on the Breadth First Search traversal. However, because of the exhaustive exploration of all the nodes and edges of the graph, this operation might be very time consuming. A possible solution is distributing the graph among the nodes of a shared-nothing parallel system. Nevertheless, this operation may generate a large amount of inter-node communication. In this paper, we propose two graph partitioning techniques and improve previous distributed versions of BFS in order to reduce this communication.