位置:成果数据库 > 期刊 > 期刊详情页
基于强连通分量的个性化的网页排名高效算法
  • ISSN号:0254-4164
  • 期刊名称:《计算机学报》
  • 时间:0
  • 分类:TP311[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
  • 作者机构:东北大学计算机科学与工程学院,沈阳110004
  • 相关基金:国家“九七三”重点基础研究发展规划项目基金(2012CB316201); 国家自然科学基金面上项目(61472070)资助
中文摘要:

个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率.

英文摘要:

Personalized PageRank (PPR) is usually employed to rank the nodes of graphs. Due to the ever increasing volume of graph, how to improve the efficiency of PPR computations has become a research focus. Thus the purpose of this paper is to improve the efficiency of PPR computations. The existing optimization algorithms can he generally classified into two categories: distributed algorithm and serial algorithm, and the general approach of them is mainly through partitioning the computations on the big graph into computations on multiple smaller sub-graphs, but the communication between sub-graphs usually involve a large amount of data and is of a high frequency. The SCC (Strongly Connected Component) based algorithms proposed in this paper can resolve these problems effectively. The main computation steps of them is: first identify and remove volumes of unrelated nodes and edges quickly before PPR computation, then transform the PPR computations on big graph into that on multiple SCC sub-graphs, which make the multiple data communications between sub-graphs turn into one time communication. The SCC based algorithm in this paper can reduce not only the communication amount between SCCs but also the storage I/O frequency, while keeping high algorithm accuracy. The experiments demonstrate that the algorithms proposed in this paper can make obvious improvements for the PPR computation efficiency.

同期刊论文项目
同项目期刊论文
期刊信息
  • 《计算机学报》
  • 北大核心期刊(2011版)
  • 主管单位:中国科学院
  • 主办单位:中国计算机学会 中国科学院计算技术研究所
  • 主编:孙凝晖
  • 地址:北京中关村科学院南路6号
  • 邮编:100190
  • 邮箱:cjc@ict.ac.cn
  • 电话:010-62620695
  • 国际标准刊号:ISSN:0254-4164
  • 国内统一刊号:ISSN:11-1826/TP
  • 邮发代号:2-833
  • 获奖情况:
  • 中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 美国数学评论(网络版),荷兰文摘与引文数据库,美国工程索引,美国剑桥科学文摘,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:48433