智能算法——PageRank
一、PageRank的基本概念
1、PageRank的概念
PageRank，即网页排名算法，又称为网页级别算法，是由佩奇和布林在1997年提出来的链接分析算法。PageRank是用来标识网页的等级、重要性的一种方法，是衡量一个网页的重要指标。PageRank算法在谷歌的搜索引擎中对网页质量的评价起到了重要的作用，在PageRank算法提出之前，已经有人提出使用网页的入链数量进行链接分析，但是PageRank算法除了考虑入链数量之外，还参考了网页质量因素，通过组合入链数量和网页质量因素两个指标，使得网页重要性的评价更加准确。
在搜索中，有人为了使得自己的网页的排名能够靠前，想出了很多的方法来作弊，这样的作弊被称为链接作弊(Link Spam)。简单来讲，对于上述的仅考虑入链数量的网页级别算法，有人为了使自己的网页(称为网页A)的级别更高，便做了很多的网页以使得这些网页都指向网页A，这样网页A的入链数量就会变得很多，自然，网页A的网页级别就会变得很高，但是这样的网页A的高级别只是所有者作弊的结果，并不等价于网页的质量就很好。
但是，PageRank算法可以避免这样的情况，因为PageRank值同时考虑入链数量和网页质量，入链数量之前已经说了，然而，对于自己作弊生成的指向网页A的网页的质量本身就很低，这样综合的结果是网页A的网页质量也不会变得很高，这样PageRank算法就对网页质量的评价起到了很好的效果。
网页的链接分析可以抽象成图模型，如下图所示：
(图 1 有向图)
在上图中，链接关系分别为：1-->2，1-->3，1-->4，2-->1，2-->4，4-->2，4-->3。
2、PageRank的两个假设
对于某个网页的PageRank的计算是基于以下两个假设：
- 数量假设。在Web图模型中，如果一个页面节点接收到的其他网页指向的链接数量越多，那么这个页面越重要。简单来讲是指链接到网页A的链接数越多，网页A越重要。
- 质量假设。指向页面A的入链的质量不同，质量高的页面会通过链接向其他的页面传递更多的权重，所以越是质量高的页面指向页面A，则页面A越重要。简单来讲是指链接到网页A的原网页越重要，则网页A也会越重要。
数量假设，简单来讲就是在互联网中，如果一个网页接收到的其他的网页指向的入链数量越多，那么这个页面就越重要。质量假设，简单来讲就是在互联网中，对于一个页面，越是质量高的网页指向该页面，则该页面越重要。
PageRank算法很好地组合了这两个假设，使得对网页的重要性评价变得更加准确。如早期只有数量假设，现实的情况是并不是指向该网页的链接越多该网页越重要，比如可以通过一些办法使得很多的网页指向该网页，在社交网络中，可以购买一些垃圾粉，但是这样并不会提升自己的重要性，反倒是有一些很重要的用户关注你，你的重要性较高。
二、PageRank的计算方法
1、有向图的表示
如图1，对于图模型，通常可以使用矩阵来存储，成为邻接矩阵，则图1的邻接矩阵为：
其中，邻接矩阵的每一行代表的是每个节点的出链。
2、网页链接概率矩阵
对上述的邻接矩阵的出链进行归一化，即：
这样，即表示有多少概率链接到其他的点，如从节点1分别以概率
链接到节点2，节点3，节点4。
3、概率转移矩阵
对上述的网页链接概率矩阵求转置即可得到概率转移矩阵：
概率转移矩阵可以描述一个用户在网上的下一步的访问行为。若此时初始化用户对每一个网页节点的访问概率相等，即：
则当该用户下一次访问各节点的概率为：
但是，此时存在这样的一个问题，一个用户不可能一直按照链接进行操作，有时会重新进去新的页面，即以一定的概率按照转移概率浏览网页节点。
4、修改后的转移矩阵
在上述转移矩阵中加入跳出当前链接的概率：
。此时转移矩阵变为：
在谷歌的计算中，通常取
5、迭代计算求解PageRank值
通过迭代公式：
求解PageRank值，当
和
的误差在一定的范围内，即为最终的PageRank值。
三、简单的原理实现
对于是上述图1的问题，通过PageRank算法求出各节点的PageRank值为：
0.32456139 0.2251462 0.2251462 0.2251462
对应的程序代码为：
#coding:UTF-8
import numpy
from numpy import zeros
from numpy import ones
from numpy import mat
import string
import math
def loadData(filepath):
f = open(filepath)
#用于记录顶点
dict_tmp = {}
#获取到所有的顶点
for lines in f.readlines():
line = lines.strip().split("\t")
if line[0] not in dict_tmp:
dict_tmp[line[0]] = True
if line[1] not in dict_tmp:
dict_tmp[line[1]] = True
#统计顶点的个数
num = len(dict_tmp.keys())
f.close()
#构建矩阵
M = zeros((num, num))
f = open(filepath)
for lines in f.readlines():
line = lines.strip().split("\t")
#为简单起见，顶点是从0开始编码
M[string.atoi(line[0]), string.atoi(line[1])] = 1
f.close()
return M
def compareMatrix(q, p, n, e):
#对比的是两个列向量
for i in xrange(n):
if (abs(p[i,0] - q[i,0]) > e):
return False
return True
def pagerank(M, alpha, e):
#从M得到转移矩阵
num = len(M[0,])
for i in xrange(num):#行
sumCol = sum(M[i,])
for j in xrange(num):#列
M[i, j] = M[i, j] / sumCol
#转移矩阵
M = M.T
N = ones((num, num))
G = alpha * M + (1-alpha)*(1.0/num)*N
#初始化pagerank值
q = (1.0/num) * ones((num, 1))
q_new = mat(G) * mat(q)
#迭代计算
i = 0
while(not compareMatrix(q_new, q, num, e)):
q = q_new
q_new = mat(G) * mat(q)
i += 1
print i
print q_new
return q_new
if __name__ == "__main__":
M = loadData("E:\python\data.txt")
e = 0.0000001
pr = pagerank(M, 0.85, e)
print "the final pagerank:"
print pr参考文献
1、PageRank算法(点击打开链接)
2、谷歌背后的数学(点击打开链接)