A Parallel Method for All-Pair SimRank Similarity Computation

摘要

How to measure SimRank similarity of all-pair vertices in a graph is a very important research topic which has a wide range of applications in many fields. However, computation of SimRank is costly in both time and space, making traditional computing methods failing to handle graph data of ever-growing size. This paper proposes a parallel multi-level solution for all-pair SimRank similarity computing on large graphs. We partition the objective graph first with the idea of modularity maximization and get a collapsed graph based on the blocks. Then we compute the similarities between verteices inside a block as well as the similarities between the blocks. In the end, we integrate these two types of similarities and calculate the approximate SimRank simlarities between all vertex pairs. The method is implemented on Spark platform and it makes an improvement on time efficiency while maintaining the effectiveness compared to SimRank.