Efficient Parallel Algorithms For Exact SimRank Computations

SimRank is a popular measure for evaluating node similarities in graphs, but its high computational cost limits scalability for large graphs. The ExactSim [1] algorithm achieves precise single-source SimRank similarities but suffers from significant computation time. In this work, we parallelize key components of ExactSim — Personalized PageRank (PPR) computations and SimRank calculations on a CPU-based shared memory multi-core system. By optimizing these modules, we significantly reduce runtime, making ExactSim more practical for large-scale applications. Our results (on graph sizes ranging from 0.1 million edges to 100 million edges) demonstrate the effectiveness of parallelization in improving both efficiency and scalability.