谷歌搜索算法(page rank algorithm)简介--北太天元学习19
我曾经给出了谷歌搜索算法(page rank)一个比较详细的介绍，见下面的两个视频(阅读本节内容不需要看下面两个视频)。
【lecture10-1 page rank 算法简介】 https://www.bilibili.com/video/BV1kP411N77X/?share_source=copy_web&vd_source=2adc5aa7a702b808eb8b31dbd210f954
【北太天元实现pagerank算法(网页排名算法)的代码 lecture10-2-page-rank-code】 https://www.bilibili.com/video/BV1r8411e77H/?share_source=copy_web&vd_source=2adc5aa7a702b808eb8b31dbd210f954
在北太天元学习18里我们已经介绍了离散模型，而且还介绍了矩阵的特征值，有了这些准备
工作，我希望在这里这次介绍page rank的时候，做得更加简单。 这里将用一种新的方式来介绍page rank算法。
我们假设有 4 个网页 ，分别是网页1, 网页2, 网页3, 网页4。 假设在初始时刻，在网页1有很多人在浏览，在其他网页没有人浏览。所有浏览网页的人的总数记作单位1 (这个总人数非常大，例如是好几十亿人), 假设每隔一个单位时间一部分人会转移到别的网页（例如，网页上有个链接), 我们研究在不同的时刻，各个网页上的浏览者的比例。 定义时间n时的态(state) 为 p_n = [ p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n} ] , 其中 p_{i,n} 表示 在时间 n 网页i 上的浏览者的比例.
按照我们上面的描述，我们给出初始时刻态 p_0 = [ 1, 0 , 0 , 0] , 态p_{n+1} 和 态p_{n} 之间的递推关系
是我们建模的重点:
p_{n+1} = A p_{n}
其中矩阵 A 称为状态转移矩阵，
我们以 p_{1,n+1} 的计算来解释建模
p_{1,n+1} =
A(1,1)*p_{1,n} + A(1,2)*p_{2,n}
A(1,3)*p_{3,n} + A(4,1)*p_{4,n}
其中 A(1,1)*p_{1,n} 表示在 n 时刻正在浏览网页1的人数p_{1,n} 有一部分在
n+1 时刻还留在在第1个网页，这个比例是A(1,1);
其中 A(1,2)*p_{2,n} 表示在 n 时刻正在浏览网页2的人数p_{1,n} 有一部分在
n+1 时刻转移到了第1个网页，这个比例是A(1,2);
...
有一个要求是 A(1,1)+A(2,1)+A(3,1)+A(4,1) = 1 , 这表明原来在网页1浏览的人会有不同
比例的人在下一个时刻分配到不同的网页，但是总人数还是不变。
(如果考虑有人累了，不想浏览网页了，那就可以增加第5个"网页"，到了第5个"网页"的就表示
下网了)
状态转移矩阵的其它行的解释和第一行类似， 但是如何确定 A(i,j) 呢?
这个也算建模的一部分，我们可以这样来建模:
1. 如果第i个网页总共有指向指向其它网页的链接数为k，那么转移到所链接网页的概率是
1/(k+1）
例如， 第1个网页具有两个链接，分别指向2和4， 那么
A(1,1) = 1/3, A(2,1) = 1/3, A(3,1) = 0, A(4,1) = 1/3;
2. 如果一个网页没有指向任何一个其它的网页，那么浏览者会随机的选择一个其它的网页
例如 第2个网页没有指向任何其它网页, 那么
A(1,2) = 1/4, A(2,2) = 1/4, A(3,2) = 1/4, A(4,2) = 1/4;
我们给一个具体的例子, 网页1具有的链接是2和4, 网页2没有指向任何其他网页，
网页3具有的链接是1 , 网页4 指向的链接是2，3
此时
A = [ 1/3 1/4 1/2 0
1/3 1/4 0 1/3
0 1/4 1/2 1/3
1/3 1/4 0 1/3
];
初始时刻 x_0 = [ 1 ; 0; 0; 0 ] ;
我们看随着时间的变换 x_n 如何变化?
我用北太天元运行下面的脚本，然后在视频中给大家解释结果
%北太天元做网页排名 page rank 的一个简单例子
%
clc
clf;
close all;
clear all;
A = [ 1/3 1/4 1/2 0
1/3 1/4 0 1/3
0 1/4 1/2 1/3
1/3 1/4 0 1/3
];
初始p = [1; 0; 0 ; 0 ] ; %初始时刻所有的人都在第一个网页
N = 20 ; % 我们记录100个时刻的数据
p = zeros(4,N);
p(:,1) = 初始p;
for n = 1: N-1
p(:, n+1) = A*p(:,n);
end
hold on
for j = 1:4
plot(1:N, p(j,:), 'LineWidth', 5);
str(j) = sprintf("网页%d",j);
end
title("各个网页上的浏览者比例随时间变化")
hold off
legend(str);
for j = 1:4
label_str(j) = sprintf("网站%d 占比 %d %%", j, 100*p(j,end));
end
figure(2)
pie( p(:,end), label_str);
title("浏览者最后一个时刻在各个网页上的占比")
另外，我们还可以计算矩阵A的特征值，观察A的最大特征值(计算也许有数值误差,
如果特征值显示为复数，取模最大的特征值)对应的特征向量， 你会发现和我们计算的
x(:,end) 有关系?
这个关系是什么？ 读者朋友可以自己尝试一下，我会在这一节的配套视频里给出来。
