PageRank算法的核心思想
source link: https://ylhao.github.io/2019/05/17/271/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
PageRank算法的核心思想
网页的排名主要取决于：
- 网页的质量
- 网页与查询的相关性
PageRank算法的作用是度量网页的质量。真正找到计算网页自身质量的完美的数据模型的是Google的创始人拉里⋅佩奇和谢尔盖⋅布林。
PageRank的核心思想：
- 在互联网上如果一个网页被很多其他网页所链接，说明他受到普遍的承认和信赖，他的排名就高（PageRank值大）。
- 网页排名越高（PageRank值越大），网页贡献的链接的权重越大。
从PageRank核心思想出发，可以做以下假设：
- 用S(vi)定义vi这个页面的PageRank值。
- 用ϵ表示所有其他可以链接到vi这个页面的网页集合。
- 那么便可以用(j,i)来定义集合中的一个（由页面vj链接到页面vi)。
一个页面的PageRank值可以定义为：
S(vi)=∑(j,i)∈ϵS(vj)
如上图所示，A,B,C,D表示4个网页，那么网页的PageRank值可以定义为：
S(A)=S(B)+S(C)
可以看到B、C两点都外链了2个节点，那么对于B,C来说，是可以选择不去A的而去另外一个链接的，所以外链进入A是有一定概率的，更改PageRank的定义：
S(vi)=∑(j,i)∈ϵS(vj)Out(vj)
其中Out(vj)表示网页vj中的外链总数量。
PageRank算法的计算过程
计算一个网页的PageRank值需要用到网页本身的PageRank值，这是一个“先有鸡还是先有蛋”的问题。布林解决了这个问题。首先布林将这个问题变为了一个二维矩阵相乘的问题，并用迭代的方法解决了这个问题。
- 首先假设所有网页的排名（PageRank值）相同。
- 根据这个初始值算出各个网页的第一次排名（PageRank值）。
- 然后再根据第一次排名算出第二次排名（PageRank值）。
- S(v)=[S(v1),S(v2),S(v3),…,S(vn)]T，即S(v)为一个n维的PageRank值向量。
- A为一个矩阵且：
A_{ji}=\left{ \begin{aligned} \frac{1}{out(v_j)},\qquad if (j,i) \in \epsilon \ 0,\qquad if (j,i) \notin \epsilon\ \end{aligned} \right.
如果给S(v)一个初始值S(v)0，便可以通过下式不断迭代求解：
S(v)k=AT⋅S(v)k−1
【TextRank】关键词提取 算法原理 公式推导 源码分析
)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]
文章标题:PageRank算法的核心思想
文章字数:626
本文作者:ylhao
发布时间:2019-05-17, 23:50:13
最后更新:2019-06-07, 11:50:53
原始链接:https://ylhao.github.io/2019/05/17/271/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。
未找到相关的 Issues 进行评论
请联系 @ylhao 初始化创建
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK