-
题名基于强连通分量的个性化的网页排名高效算法
被引量:3
- 1
-
-
作者
杨红果
申德荣
寇月
聂铁铮
于戈
-
机构
东北大学计算机科学与工程学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2017年第3期584-600,共17页
-
基金
国家"九七三"重点基础研究发展规划项目基金(2012CB316201)
国家自然科学基金面上项目(61472070)资助~~
-
文摘
个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率.
-
关键词
个性化的网页排名
分布式算法
串行算法
强连通子图
通信量
i/o频率
-
Keywords
personalized page-rank
distributed computing
serial computing
strongly connectedcomponent
communication amount
i/o frequency
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-