Predictive partitioning for efficient BFS traversal in social networks

This source preferred by Damien Fay

This data was imported from Scopus:

Authors: Fay, D.

Journal: Studies in Computational Intelligence

Volume: 644

Pages: 11-26

ISBN: 9783319305684

ISSN: 1860-949X

DOI: 10.1007/978-3-319-30569-1_2

© Springer International Publishing Switzerland 2016.In this paper we show how graph structure can be used to significantly reduce the computational bottleneck of the Breadth First Search algorithm (the foundation of many graph traversal techniques) for social networks. 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. Empirical simulations show that such partitions can reduce the message overhead in the order of 20% for graphs with common social network structural properties. These results have implications for graph processing in multiprocessor and distributed computing environments.

The data on this page was last updated at 04:39 on March 27, 2017.