The More the Merrier: Efficient Multi-Source Graph Traversal

Graph analytics on social networks, Web data, and com-munication networks has been widely used in a plethora of applications. Many graph analytics algorithms are based on breadth-first search (BFS) graph traversal, which is not only time-consuming for large datasets but also involves much redundant computation when executed multiple times from different start vertices. In this paper, we propose Multi-Source BFS (MS-BFS), an algorithm designed for running multiple concurrent BFSs over the same graph on a single CPU core that scales up as the number of cores increases. MS-BFS leverages the properties of small-world networks, which apply to many real-world graphs, and enables effi-cient graph traversal that: (i) shares common computation across concurrent BFSs; (ii) greatly reduces the number of random memory accesses during BFS; and (iii) does not in-cur synchronization costs. We demonstrate how the graph analytics application of computing the closeness centrality value of entities in a graph can be efficiently solved with MS-BFS. We also present an extensive experimental evalu-ation with both synthetic and real datasets, including Twit-ter and Wikipedia, showing that MS-BFS provides almost linear scalability with respect to the number of cores and excellent scalability for increasing graph sizes, outperform-ing state-of-the-art BFS algorithms by more than one order of magnitude when running a large number of BFSs. 1