高技术通讯2025，Vol.35Issue(6)：579-589,11.DOI:10.3772/j.issn.1002-0470.2025.06.002
VS-NRM:基于数据划分的PageRank并行图算法优化
VS-NRM:optimization of parallel PageRank based on graph partitioning
摘要
Abstract
PageRank is a crucial algorithm for assessing the significance of vertices within a graph.Nevertheless,the weak locality of PageRank severely restricts its efficiency.This paper proposes an optimized parallel PageRank algo-rithm based on graph partitioning,named vertex sort-node ReMap(VS-NRM),which boosts the performance of PageRank by enhancing memory performance.Firstly,a data partitioning algorithm based on destination-source vertex sorting is introduced.This algorithm partitions edges with the same destination into the same partition on the basis of uniform partitioning.Subsequently,it arranges the outgoing edges of each vertex set according to the desti-nation vertices and sorts the source vertices of the edge sets with the same destination to minimize random memory access.Secondly,a breadth-first number remapping data partitioning method is proposed.This method can effec-tively reduce the discontinuity of adjacent vertices,thereby cutting down on random memory access that arises from significant differences between source vertices sharing the same destination.Finally,a high-degree vertices priority numbering data partitioning method based on power graph properties is presented.This method gives priority to high-degree vertices to improve the sequence of low-degree vertices,further enhancing memory access locality.Ex-perimental results demonstrate that VS-NRM attains over a 20％performance enhancement in comparison to the state-of-the-art methods.关键词
PageRank/图数据划分/节点排序/重编号/高度数节点优先Key words
PageRank/graph partitioning/vertex sorting/remapping/high-degree vertices priority引用本文复制引用
张萍,曹华伟,杨莫凡,梁彦,安学军..VS-NRM:基于数据划分的PageRank并行图算法优化[J].高技术通讯,2025,35(6):579-589,11.基金项目
国家重点研发计划(2023YFB4502305)和北京市自然科学基金(4232036)资助项目. （2023YFB4502305）
