智能算法——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的计算是基于以下两个假设：

1. 数量假设。在Web图模型中，如果一个页面节点接收到的其他网页指向的链接数量越多，那么这个页面越重要。简单来讲是指链接到网页A的链接数越多，网页A越重要。
2. 质量假设。指向页面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、谷歌背后的数学(点击打开链接)