pagerank

原理

pagerank算法是为了分析网页排名(PR值)。可以想象:

  • 网页被其他网页指向次数越多,越重要
  • 排名高的网页具有更大的表决权,换言之,具有更大的权重

所以,pagerank的原理就是: 一个网页的排名等于所有链接到该网页的网页的排名加权和。

显然,这样的排名相较于根据关键词在网页中出现次数的搜索更为客观。

但是,每个网页应该只能投一票。因此,如果一个网页链接到10个网页,那么它对每个网页的贡献就是其自身排名的1/10。

由于每个网页排名取决于其他,因此就存在“鸡生蛋蛋生鸡”的问题。通过赋初值,然后求收敛值的方法来求解。pagerank是否有解通过以下两点来决定:

  • 是否存在收敛值
  • 收敛极限是否与初值有关

这样,问题也就转化成了Markov过程的收敛性证明。若要收敛,需要状态转移矩阵满足3个条件:

  • 是随机矩阵,严格的说是每一列的矩阵元素非负、之和为1(随机矩阵并非只有这一种形式)
  • 不可约,即矩阵对应有向图必须强连通,对于任意两个节点存在连通路径
  • 非周期,每个节点存在自回路

当我们假设用户可以一定概率不根据状态转移矩阵而是随机访问(等概率访问)每个网页时,不可约和非周期就得到了满足。这个假设的现实意义就是用户不通过链接进行跳转而是直接在地址栏输入网址进行访问。

优缺点

优点

是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。

缺点

  1. 人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低

  2. 没有区分站内导航链接。很多网站的首页都有很多对站内其他页面的链接,称为站内导航链接。这些链接与不同网站之间的链接相比,肯定是后者更能体现PageRank值的传递关系。

  3. 没有过滤广告链接和功能链接(例如常见的“分享到微博”)。这些链接通常没有什么实际价值,前者链接到广告页面,后者常常链接到某个社交网站首页。

  4. 对新网页不友好。一个新网页的一般入链相对较少,即使它的内容的质量很高,要成为一个高PR值的页面仍需要很长时间的推广。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 2 18:52:27 2017

@author: muzhen
"""

import numpy as np

# transition matrix a, a[i][j] represents whether web j exists link to web i or not.
a = np.array([[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 0, 0]], dtype=float)

# compute the transition probability matrix
def graphmove(a):
b = np.sum(a, axis=0)
c = a / b
return c

# init probability vector which represents the probability user in each web at first.
def firstPr(c):
return np.full((c.shape[0],1), 1.0/c.shape[1])

def pagerank(c,pr,b):
"""
Args:
b is the prob user changes web by transition matrix, (1 - b) is the prob user changes web accordding to probability vector.
"""
pr_init = pr
while True:
pr_new = b * np.dot(c, pr) + (1 - b) * pr_init
if (pr == pr_new).all() == True:
break
else:
pr = pr_new

return pr_new

if __name__ == '__main__':o

c = graphmove(a)
pr = firstPr(c)
b = 0.85
pr = pagerank(c, pr, b)
print(pr)

references

PageRank算法

随机矩阵(stochastic matrix)与 PageRank

【十大经典数据挖掘算法】PageRank

PageRank算法–从原理到实现