【PageRank】简介
source link: https://www.guofei.site/2019/04/27/pagerank.html
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】简介
2019年04月27日Author: Guofei
文章归类: 3-3-图模型 ，文章编号: 350
版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2019/04/27/pagerank.html
引入
PageRank是Sergey Brin与Larry Page于1998年在WWW7会议上提出来的，用来解决链接分析中网页排名的问题。在衡量一个网页的排名，直觉告诉我们：
- 当一个网页被更多网页所链接时，其排名会越靠前；
- 排名高的网页应具有更大的表决权，即当一个网页被排名高的网页所链接时，其重要性也应对应提高。
对于这两个直觉，PageRank算法所建立的模型非常简单：一个网页的排名等于所有链接到该网页的网页的加权排名之和：
PRi=∑(j,i)∈EPRjOjPRi=∑(j,i)∈EPRjOj
其中，
PRiPRi指的是网页i的 PageRank 值。这个值越大，表示网页越重要。
OjOj指的是网页j的外链数（the number of out-links）
推导
模型
网页相互链接，形成一个有向图 G=(V,E)G=(V,E)
记P=(PR1,PR2,…,PRn)TP=(PR1,PR2,…,PRn)T 为n维PageRank值向量，
记A为有向图G对应的转移矩阵，A={1/Oi0if(i,j)∈EotherwiseA={1/Oiif(i,j)∈E0otherwise
于是P=ATPP=ATP
求解
PageRank采用power iteration方法来求出PageRank值
我们发现，P是ATAT的特征值为1的特征向量，为了存在这个特征向量，矩阵A必须满足3个性质
- 每行必须村子一个非零值，即必须存在一个外链接（没有外链接的网页被称为dangling pages）
- 不可约（irreducible），即矩阵A所对应的有向图G必须是强连通的，对于任意两个节点u,v∈V，存在一个从u到v的路径
- 非周期性（aperiodic），即每个节点存在自回路。
一般情况下AA不满足三个性质，对A做进一步处理：
- 为了满足第一条性质，如果一行全为0，那么把行替换为e/ne/n
- 为满足2,3性质，做平滑处理P=((1−d)En+dAT)P=((1−d)En+dAT)，其中，d为 damping factor，常置为0与1之间的一个常数；E为单位阵。
您的支持将鼓励我继续创作！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK