HotCSE Seminar
Computational Science & Engineering
Wednesday Apr 10, 12pm-1pm, Pettit 102A

Computing Common Neighbors: Approaches and Optimizations

Jing An
Advisor: Prof. David Bader


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.


Xiaojing (Jing) An is a second year Ph.D. student, in HPC lab advised by Prof. David A. Bader. Her research direction is graphs algorithms on HPC systems, including both improving graph algorithms and their implementations.