Computing Common Neighbors: Approaches and Optimizations

Similarity indices between vertices are used in a range of graph analytics including link prediction, graph compression, and community detection. The common neighbor count is a widely used and foundational index due to its simplicity and effectiveness. Current common neighbor counting approaches are not able to scale to graphs commonly seen today: they either rely on expensive set intersections, are not amenable to parallelism and massive scale graphs, or cannot efficiently target only the most relevant results. We introduce a new efficient and scalable approach for counting common neighbors that is able to scale on parallel shared memory machines without atomics, and allows for significant performance improvements existing libraries. We also extend our approach to other common neighbor based indices such as the Jaccard Index and the Adamic/Adar Index. Our implementation is OpenMP-based and counts top common neighbors on real-world graphs with tens of billions of edges in tens of seconds on commodity servers.