PageRank is a fundamental property of graph and there have been plenty of PageRank algorithms. Generally, we consider undirected graph as a complicated directed graph. However, some properties of undirected graph, such as symmetry, are ignored when computing PageRank by existing algorithms. In this paper, we propose a parallel PageRank algorithm which is specially for undirected graph. We first demonstrate that the PageRank vector can be viewed as a linear combination of eigenvectors of probability transition matrix and the corresponding coefficients are the functions of eigenvalues. Then we introduce the Chebyshev polynomial approximation by which PageRank vector can be computed iteratively. Finally, we propose the parallel PageRank algorithm as the Chebyshev polynomial approximating algorithm(CPAA). Experimental results show that CPAA only takes 60% of iteration rounds of the power method and is at least 4 times faster than the power method.


翻译:PageRank 是图形的一个基本属性, 并有大量 PageRank 算法。 一般来说, 我们把非方向性图表视为复杂的定向图形。 但是, 在用现有算法计算 PageRank 时, 某些非方向性图表的属性, 如对称性, 被忽略。 在本文中, 我们提议了一种平行的 PageRank 算法, 专门用于非方向性图表 。 我们首先显示, PageRank 矢量可被视为概率转换矩阵和相应系数的元素的线性组合。 然后, 我们引入了 Chebyshev 多边近似值, 从而可以迭代计算 PageRank 矢量。 最后, 我们提议将平行的 PageRank 算法建议为 Chebyshev 多元相近算算算算算算法 。 我们实验结果显示, CPAAA 只能使用60% 的电源法循环, 并且至少比电法快4倍 。

0
下载
关闭预览

相关内容

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由[1] 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。
【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
【经典书】图论第四版,180页pdf
专知会员服务
145+阅读 · 2021年7月2日
专知会员服务
22+阅读 · 2021年3月23日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
42+阅读 · 2020年7月7日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
9+阅读 · 2019年11月15日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Arxiv
0+阅读 · 2022年2月3日
Arxiv
13+阅读 · 2021年10月22日
Arxiv
7+阅读 · 2021年10月19日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
Arxiv
3+阅读 · 2020年4月29日
VIP会员
相关VIP内容
【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
【经典书】图论第四版,180页pdf
专知会员服务
145+阅读 · 2021年7月2日
专知会员服务
22+阅读 · 2021年3月23日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
42+阅读 · 2020年7月7日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关论文
Arxiv
0+阅读 · 2022年2月3日
Arxiv
13+阅读 · 2021年10月22日
Arxiv
7+阅读 · 2021年10月19日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
Arxiv
3+阅读 · 2020年4月29日
Top
微信扫码咨询专知VIP会员