There is an ever-increasing need for exploring large-scale graph data sets in computational sciences, social networks, and business analytics. One of the most widely used graph searching algorithms is breadth-first search (BFS), which serves as a building block for a great many graph algorithms such as minimum spanning tree, betweenness centrality, and shortest paths. However, BFS is notoriously known challenging to optimize because of its poor locality and low computation to communication ratio. In this talk I will present several of our findings to improve the efficiency of BFS algorithms: exploiting different levels of parallelism to provide latency hiding and maximize memory bandwidth; reducing communication in distributed BFS to improve its scalability.