PAGERANK学习笔记

一、PageRank简介

​ PageRank(PR)是谷歌搜索用来在搜索引擎中对网站进行排名的算法，Sergey Brin and Lawrence Page 发布了一篇论文《The Anatomy of a Large-Scale Hypertextual Web Search Engine.》。其中提出PageRank算法，PageRank算法输出一个概率分布，用于表示随机点击链接的人到达任何特定页面的可能性。可以计算任何大小的文档集合的PageRank。PageRank 计算需要通过集合进行多次传递（称为“迭代”），以调整近似的 PageRank 值，以更贴近理论真实值。

​ 在最初的google paper中介绍这个算法的等式是

image-20230731123236589

我们假设页面 A 具有页面 T1…Tn 指向它。参数 d 是一个阻尼系数，可以设置为 0 到 1 之间。我们通常将 d 设置为 0.85。此外，C（A）被定义为从页面A流出的链接数量。

PageRanks在网页上形成概率分布，因此所有网页的PageRanks的总和将为1。

PageRank可以被认为是用户行为的模型。假设有一个“随机冲浪者”，他随机获得一个网页并不断点击链接，从未点击“返回”，但最终感到无聊并从另一个随机页面开始。随机冲浪者访问页面的概率是其PageRank。而且，d阻尼因子是“随机冲浪者”在每个页面上感到无聊并请求另一个随机页面的概率。一个重要的变化是仅将阻尼因子 d 添加到单个页面或一组页面。这允许个性化，并且几乎不可能故意误导系统以获得更高的排名。

img

图1表示一个有向图，节点A,B,C,D,E,F,H,K表示八个网页，他们的 链接关系如图一箭头所指的方向

​ 入链：从页面流出的链接

​ 出链：从页面访问的链接（可以理解为referer)

​ 在图1中，A的出链有两个，入链有一个，所以A的PR值是

image-20230731000617948

  • 如果一个页面被很多高质量（PR值高的）页面指向，则该页面可以具有很高的PageRank

二、PageRank在计算的过程时会出现几个问题

• 等级泄露（Rank Leak) 网页只有入链，没有出链( H ) 为了避免PR为0 需要赋值

• 等级沉没（Rank Sink） 网页只有出链没有入链 (F)为了避免PR为0 需要赋值

• Spider Traps 网页和其他节点无链接，只有自己指向自己 (k)

三、PageRank定义

假定有N个节点，每个节点到任意一个节点几率相等，那么转移的几率是1/N

  • 一个网页的PR值=所有入链集合的加权PR之和

uri A为评估页面，B{referer1.referer2}是A入链的集合

PR(A)=d*(PR(referer1)/referer1的所有出链数量+PR(referer2)/referer2的所有出链数量+…)

四、PageRank随机浏览模型

img

使用迭代法计算Pagerank值【根据图1的范例】

image-20230731123311622

将所有节点转换成数字，在将所有入链转换成坐标来得到矩阵

每行为对应页面的入链 B页面有两个入链D,和E （D和E都有两个出链，那么如果访问关系是按照链接跳转，那么从D和E跳转到B的可能性质都为1/2

五、python完整代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import numpy as np
import pandas as pd

p = 0.85  # 引入浏览当前网页的概率为p,假设p=0.85

df = pd.read_csv('file/1.csv')
edges = [list(edge) for edge in zip(df['t1'], df['t2'])]

# 根据边获取节点的集合
nodes = list(set(np.array(edges).flatten()))

N = len(nodes)
# 将字符串，映射成阿拉伯数字
dict_uri = dict(enumerate(nodes))
#将字典键值反转  同时获取空值的id
node_to_num={}
num_isnull=-1
for key, val in dict_uri.items():
    node_to_num[val]=key
    if val=='Q':
        num_isnull=key
for edge in edges:
    edge[0] = node_to_num[edge[0]]
    edge[1] = node_to_num[edge[1]]
# 生成初步的矩阵
a = np.zeros([N, N])
for edge in edges:
    a[edge[1], edge[0]] = 1

# 入链，行a[i]里面的元素都是i的入链
length = a.shape[1]  # 网页数量
# 构造转移矩阵
# 出链，行a[i]里面的元素都是i的出链
b = np.transpose(a)  # b为a的转置矩阵
m = np.zeros((a.shape), dtype=float)
for i in range(a.shape[0]):
    for j in range(a.shape[1]):
        # 如果一个节点没有任何出链，Dead Ends
        if b[j].sum() == 0:
            b[j] = b[j] + np.array([1 / length] * length)
        m[i][j] = a[i][j] / (b[j].sum())  # 完成初始化分配

# pr值得初始化
v = np.zeros((m.shape[0], 1), dtype=float)  # 构造一个存放pr值得矩阵
for i in range(m.shape[0]):
    v[i] = float(1) / m.shape[0]

count = 0
ee = np.array([[1 / length] * length]).reshape(length, -1)
# 循环100次计算pageRank值
for i in range(1000):
    #  解决spider traps问题，spider traps会导致网站权重向一个节点偏移，将转移矩阵加上打开其他网页的概率1-p
    v = p * np.dot(m, v) + (1 - p) * ee
    count += 1
# pageRank值

t = 0
info = dict()
for i in v:
    info[dict_uri[t]] = list(i)[0]
    # info.append(temp)
    t += 1
pagerank_sorted_values = sorted(info.items(), key=lambda x: x[1], reverse=True)
print(pagerank_sorted_values)
all=0
for i in pagerank_sorted_values:
    all+=list(i)[1]
print(all)

参考链接