LeaderRank的外推加速方法

Extrapolation methods for accelerating LeaderRank

复杂网络中的节点排序在网络结构和传播动力学等研究中占据重要地位.LeaderRank作为一种重要的节点排序算法,已得到了广泛应用.在幂法计算LeaderRank的基础上,提出3种计算LeaderRank的外推方法,分别为Aitken外推法、幂外推法和改进幂外推法.为了对比各方法的优劣,在4个真实网络上进行数值实验,结果表明:Aitken外推法的计算速度优于幂外推法,而精度略差于幂外推法;改进幂外推法则在计算速度和精度上均有优良表现.

Identifying vital nodes in complex networks is important for investigating net-work structures and their corresponding propagation processes.LeaderRank,as an algorithm for ranking the nodes of complex networks,has been widely applied in variousfields.Based on the power method,this study proposes three methods for accelerating the computation of LeaderRank,i.e.,the Aitken extrapolation method,the power extrapolation method,and the modified version of the latter.Experiments on the dataset of four real networks show that the Aitken extrapolation method is faster than the power extrapolation method,albeit with a lower precision,and that the modified power extrapolation method provides good balance between accuracy and speed.