我曾經(jīng)給出了谷歌搜索算法(page rank)一個(gè)比較詳細(xì)的介紹，見下面的兩個(gè)視頻(閱讀本節(jié)內(nèi)容不需要看下面兩個(gè)視頻)。
【lecture10-1 page rank 算法簡介】 https://www.bilibili.com/video/BV1kP411N77X/?share_source=copy_web&vd_source=2adc5aa7a702b808eb8b31dbd210f954
【北太天元實(shí)現(xiàn)pagerank算法(網(wǎng)頁排名算法)的代碼 lecture10-2-page-rank-code】 https://www.bilibili.com/video/BV1r8411e77H/?share_source=copy_web&vd_source=2adc5aa7a702b808eb8b31dbd210f954

在北太天元學(xué)習(xí)18里我們已經(jīng)介紹了離散模型，而且還介紹了矩陣的特征值，有了這些準(zhǔn)備
工作，我希望在這里這次介紹page rank的時(shí)候，做得更加簡單。 這里將用一種新的方式來介紹page rank算法。

我們假設(shè)有 4 個(gè)網(wǎng)頁 ，分別是網(wǎng)頁1,? 網(wǎng)頁2, 網(wǎng)頁3, 網(wǎng)頁4。 假設(shè)在初始時(shí)刻，在網(wǎng)頁1有很多人在瀏覽，在其他網(wǎng)頁沒有人瀏覽。所有瀏覽網(wǎng)頁的人的總數(shù)記作單位1 (這個(gè)總?cè)藬?shù)非常大，例如是好幾十億人),? 假設(shè)每隔一個(gè)單位時(shí)間一部分人會轉(zhuǎn)移到別的網(wǎng)頁（例如，網(wǎng)頁上有個(gè)鏈接), 我們研究在不同的時(shí)刻，各個(gè)網(wǎng)頁上的瀏覽者的比例。 定義時(shí)間n時(shí)的態(tài)(state) 為 p_n = [ p_{1,n}, p_{2,n}, p_{3,n}, p_{4,n} ] , 其中 p_{i,n} 表示 在時(shí)間 n 網(wǎng)頁i 上的瀏覽者的比例.??

按照我們上面的描述，我們給出初始時(shí)刻態(tài) p_0 = [ 1, 0 , 0 , 0] ,? 態(tài)p_{n+1} 和 態(tài)p_{n} 之間的遞推關(guān)系
是我們建模的重點(diǎn):

p_{n+1} =? A p_{n}

其中矩陣 A 稱為狀態(tài)轉(zhuǎn)移矩陣，
我們以 p_{1,n+1} 的計(jì)算來解釋建模
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 時(shí)刻正在瀏覽網(wǎng)頁1的人數(shù)p_{1,n} 有一部分在
n+1 時(shí)刻還留在在第1個(gè)網(wǎng)頁，這個(gè)比例是A(1,1);
其中 A(1,2)*p_{2,n} 表示在 n 時(shí)刻正在瀏覽網(wǎng)頁2的人數(shù)p_{1,n} 有一部分在
n+1 時(shí)刻轉(zhuǎn)移到了第1個(gè)網(wǎng)頁，這個(gè)比例是A(1,2);
...? ?
有一個(gè)要求是 A(1,1)+A(2,1)+A(3,1)+A(4,1) = 1 , 這表明原來在網(wǎng)頁1瀏覽的人會有不同
比例的人在下一個(gè)時(shí)刻分配到不同的網(wǎng)頁，但是總?cè)藬?shù)還是不變。 　
(如果考慮有人累了，不想瀏覽網(wǎng)頁了，那就可以增加第5個(gè)"網(wǎng)頁"，到了第5個(gè)"網(wǎng)頁"的就表示
?下網(wǎng)了)

狀態(tài)轉(zhuǎn)移矩陣的其它行的解釋和第一行類似， 但是如何確定 A(i,j) 呢?
這個(gè)也算建模的一部分，我們可以這樣來建模:
1. 如果第i個(gè)網(wǎng)頁總共有指向指向其它網(wǎng)頁的鏈接數(shù)為k，那么轉(zhuǎn)移到所鏈接網(wǎng)頁的概率是
?? 1/(k+1）
?? ??? ??? ? 例如， 第1個(gè)網(wǎng)頁具有兩個(gè)鏈接，分別指向2和4， 那么
?? ??? ??? ? A(1,1) = 1/3,? A(2,1) = 1/3, A(3,1) = 0, A(4,1) = 1/3;
2. 如果一個(gè)網(wǎng)頁沒有指向任何一個(gè)其它的網(wǎng)頁，那么瀏覽者會隨機(jī)的選擇一個(gè)其它的網(wǎng)頁
?? ? 例如 第2個(gè)網(wǎng)頁沒有指向任何其它網(wǎng)頁, 那么
?????? A(1,2) = 1/4, A(2,2) = 1/4, A(3,2) = 1/4,? A(4,2) = 1/4; ?? ?

我們給一個(gè)具體的例子, 網(wǎng)頁1具有的鏈接是2和4, 網(wǎng)頁2沒有指向任何其他網(wǎng)頁，
?? 網(wǎng)頁3具有的鏈接是1 , 網(wǎng)頁4 指向的鏈接是2，3
此時(shí)
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
?? ??? ??? ?];
? ?
初始時(shí)刻 x_0 = [ 1 ; 0; 0; 0 ] ;
我們看隨著時(shí)間的變換 x_n 如何變化?
我用北太天元運(yùn)行下面的腳本，然后在視頻中給大家解釋結(jié)果

%北太天元做網(wǎng)頁排名 page rank 的一個(gè)簡單例子

%

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 ] ; %初始時(shí)刻所有的人都在第一個(gè)網(wǎng)頁

N = 20 ; % 我們記錄100個(gè)時(shí)刻的數(shù)據(jù)

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("網(wǎng)頁%d",j);

end

title("各個(gè)網(wǎng)頁上的瀏覽者比例隨時(shí)間變化")

hold off

legend(str);

for j = 1:4

label_str(j) = sprintf("網(wǎng)站%d 占比 %d %%", j, 100*p(j,end));

end

figure(2)

pie( p(:,end), label_str);

title("瀏覽者最后一個(gè)時(shí)刻在各個(gè)網(wǎng)頁上的占比")

另外，我們還可以計(jì)算矩陣A的特征值，觀察A的最大特征值(計(jì)算也許有數(shù)值誤差,
如果特征值顯示為復(fù)數(shù)，取模最大的特征值)對應(yīng)的特征向量， 你會發(fā)現(xiàn)和我們計(jì)算的
x(:,end) 有關(guān)系?

這個(gè)關(guān)系是什么？ 讀者朋友可以自己嘗試一下，我會在這一節(jié)的配套視頻里給出來。