Abstract
The processing of graphs is of increasing importance in many applications, with the size of such graphs growing rapidly. As with scientific computing, there is a growing need to understand the relationship between system architectures and graph algorithms, especially as both the scale of the system and the size of the graph increase. To date there is one such graph benchmark that has several hundred comparative reports available, namely Breadth First Search, which has over the last few years fueled new algorithms that have improved typical performance very significantly. This paper suggests an additional benchmark based on the computation of neighborhoods and Jaccard coefficients that is of both a different intrinsic complexity and can be recast in multiple ways that may be suitable for different classes of real-world applications.