引入
PageRank是Sergey Brin与Larry Page于1998年在WWW7会议上提出来的，用来解决链接分析中网页排名的问题。在衡量一个网页的排名，直觉告诉我们：
- 当一个网页被更多网页所链接时，其排名会越靠前；
- 排名高的网页应具有更大的表决权，即当一个网页被排名高的网页所链接时，其重要性也应对应提高。
对于这两个直觉，PageRank算法所建立的模型非常简单：一个网页的排名等于所有链接到该网页的网页的加权排名之和：
$PR_i=\sum\limits_{(j,i)\in E}\dfrac{PR_j}{O_j}$
其中，
$PR_i$指的是网页i的 PageRank 值。这个值越大，表示网页越重要。
$O_j$指的是网页j的外链数（the number of out-links）
推导
模型
网页相互链接，形成一个有向图 $G=(V,E)$
记$P=(PR_1,PR_2,…,PR_n)^T$ 为n维PageRank值向量，
记A为有向图G对应的转移矩阵，\(A=\left \{ \begin{array}{l}
1/O_i&if (i,j)\in E\\
0&otherwise\\
\end{array}\right.\)
于是$P=A^TP$
求解
PageRank采用power iteration方法来求出PageRank值
我们发现，P是$A^T$的特征值为1的特征向量，为了存在这个特征向量，矩阵A必须满足3个性质
- 每行必须村子一个非零值，即必须存在一个外链接（没有外链接的网页被称为dangling pages）
- 不可约（irreducible），即矩阵A所对应的有向图G必须是强连通的，对于任意两个节点u,v∈V，存在一个从u到v的路径
- 非周期性（aperiodic），即每个节点存在自回路。
一般情况下$A$不满足三个性质，对A做进一步处理：
- 为了满足第一条性质，如果一行全为0，那么把行替换为$e/n$
- 为满足2,3性质，做平滑处理$P=((1-d)\dfrac{E}{n}+dA^T)$，其中，d为 damping factor，常置为0与1之间的一个常数；E为单位阵。
