1、首先先大致介紹下pagerank，pagerank是Google排名算法法則的一部分，是用來(lái)標(biāo)記網(wǎng)頁(yè)的等級(jí)的一種方法，也是用來(lái)衡量一個(gè)網(wǎng)頁(yè)好壞的唯一標(biāo)準(zhǔn)。pagerank他采用PR值來(lái)劃分網(wǎng)頁(yè)的受歡迎度，PR值越高，則表名受歡迎度越高，PR最高為10，最低為0，一般PR達(dá)到4，則表名網(wǎng)站已經(jīng)不錯(cuò)了。PR為4的網(wǎng)站比PR為3的網(wǎng)站不是單純的好一點(diǎn)來(lái)形容，他是一種里氏震級(jí)的形式來(lái)形容的，就好比地震的等級(jí)，是指數(shù)刻度增長(zhǎng)的，因此可以想象PR為10的網(wǎng)站是一種什么程度。因?yàn)檫@個(gè)算法是Google提出的，因此Google將自己的網(wǎng)站PR值設(shè)置為10，所以想要自己的網(wǎng)站PR達(dá)到10，是非常難的，如果你的網(wǎng)站可以達(dá)到Google的水平。
2、介紹完了pagerank是一個(gè)什么東西后，我們就來(lái)介紹一下pagerank如何計(jì)算的。
2.1、用個(gè)例子來(lái)說(shuō)明下PageRank算法
在網(wǎng)頁(yè)A中有B、C、D三個(gè)鏈接，在網(wǎng)頁(yè)B中有A、C兩個(gè)個(gè)鏈接，在網(wǎng)頁(yè)C中有D鏈接，網(wǎng)頁(yè)D中有A、B兩個(gè)鏈接。（可以看出這個(gè)圖是強(qiáng)鏈接的，任何一個(gè)節(jié)點(diǎn)都可以到達(dá)另一個(gè)節(jié)點(diǎn)）。
我們假設(shè)每一個(gè)鏈接訪問(wèn)的概率是相同的，為了計(jì)算方便我們將每一個(gè)網(wǎng)頁(yè)的PageRank設(shè)置為1。
先給出計(jì)算公式
PR(pj) 表示網(wǎng)頁(yè) pj 的 PageRank 得分，L(pj) 表示網(wǎng)頁(yè) pj 的出鏈接數(shù)量，1/L(pj) 就表示從網(wǎng)頁(yè) pj 跳轉(zhuǎn)到 pi 的概率。
所以我們來(lái)計(jì)算第一次迭代后的PR值：
PR(A)=PR(B)/2+PR(D)/2
PR(B)=PR(A)/3+PR(D)/2
PR(C)=PR(A)/3+PR(B)/2
PR(D)=PR(A)/3+PR(C)/1
PR(A)+PR(B)+PR(C)+PR(D)=1
PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294
通過(guò)上面的公式在不斷的進(jìn)行迭代，可以得到一個(gè)收斂值，大概是在（0.265，0.235，2.206，0.294）附近。
2.2看完公式之后，我們來(lái)考慮倆種特殊的情況
2.2.1終止問(wèn)題
上面過(guò)程要滿足收斂性，需要具備一個(gè)條件：圖是強(qiáng)連通的，即從任意網(wǎng)頁(yè)可以到達(dá)其他任意網(wǎng)頁(yè)。
互聯(lián)網(wǎng)中存在網(wǎng)頁(yè)不滿足強(qiáng)連通的特性，因?yàn)橛幸恍┚W(wǎng)頁(yè)不指向任何網(wǎng)頁(yè)，按照上面公式迭代計(jì)算下去，導(dǎo)致前面累計(jì)得到的轉(zhuǎn)移概率被清零，最終得到的概率分布向量所有元素幾乎都為0。
假設(shè)把上面圖中C到D的鏈接丟掉，C變成了一個(gè)終止點(diǎn)，得到下面這個(gè)圖：
轉(zhuǎn)移矩陣M為：
不斷迭代，最終得到所有元素都為0。
2.2.2、陷阱問(wèn)題
陷阱問(wèn)題：是指有些網(wǎng)頁(yè)不存在指向其他網(wǎng)頁(yè)的鏈接，但存在指向自己的鏈接。比如下面這個(gè)圖：
這種情況下，PageRank算法不斷迭代會(huì)導(dǎo)致概率分布值全部轉(zhuǎn)移到c網(wǎng)頁(yè)上，這使得其他網(wǎng)頁(yè)的概率分布值為0，從而整個(gè)網(wǎng)頁(yè)排名就失去了意義。如果按照上面圖則對(duì)應(yīng)的轉(zhuǎn)移矩陣M為：
不斷迭代，最終得倒如下結(jié)果：
為了解決終止點(diǎn)問(wèn)題和陷阱問(wèn)題，下面需要對(duì)算法進(jìn)行改進(jìn)。假設(shè)選取下一個(gè)跳轉(zhuǎn)頁(yè)面時(shí)，既不選當(dāng)前頁(yè)面，也不選當(dāng)前網(wǎng)頁(yè)上的其他鏈接，而是以一定概率跳轉(zhuǎn)到其他不相關(guān)網(wǎng)頁(yè)，那么上面兩個(gè)問(wèn)題就能得到很好的解決，這就是完整PageRank算法思想。
N表示的時(shí)網(wǎng)頁(yè)鏈接的個(gè)數(shù)，α表示不進(jìn)行隨機(jī)跳轉(zhuǎn)的概率。
利用上面公式繼續(xù)迭代下去，直到收斂，得到最終rank值。
PageRank 的計(jì)算是采樣迭代法實(shí)現(xiàn)的：一開(kāi)始所有網(wǎng)頁(yè)結(jié)點(diǎn)的初始 PageRank 值都可以設(shè)置為某個(gè)相同的數(shù)，例如 1，然后我們通過(guò)上面這個(gè)公式，得到每個(gè)結(jié)點(diǎn)新的 PageRank 值。每當(dāng)一張網(wǎng)頁(yè)的 PageRank 發(fā)生了改變，它也會(huì)影響它的出鏈接所指向的網(wǎng)頁(yè)，因此我們可以再次使用這個(gè)公式，循環(huán)地修正每個(gè)網(wǎng)頁(yè)結(jié)點(diǎn)的值。由于這是一個(gè)馬爾科夫過(guò)程，所以我們能從理論上證明，所有網(wǎng)頁(yè)的 PageRank 最終會(huì)達(dá)到一個(gè)穩(wěn)定的數(shù)值。整個(gè)證明過(guò)程很復(fù)雜，這里我們只需要知道這個(gè)迭代計(jì)算的過(guò)程就行了。
3、基于本文主題叫做數(shù)學(xué)建模之美，也是一篇讀后感，所以我們還是寫一下感受吧。
鏈接：https://pan.baidu.com/s/1qMKEbBTcuNekgqevPTVAWQ
提取碼：aorr
這個(gè)算法的優(yōu)美之處，就在于巧妙地將網(wǎng)頁(yè)內(nèi)容的好壞，根據(jù)鏈接數(shù)的形式，用PR值進(jìn)行了排名，它不僅激發(fā)網(wǎng)頁(yè)越做越好，也促進(jìn)了各個(gè)網(wǎng)頁(yè)之間的聯(lián)系。
同時(shí)在結(jié)構(gòu)方面，他將一個(gè)復(fù)雜的問(wèn)題，進(jìn)行了簡(jiǎn)單的類比，用圖結(jié)構(gòu)的形式代替鏈接的形式，用戶訪問(wèn)的順序，也就是節(jié)點(diǎn)的走向。所以數(shù)學(xué)之美就在于他是非常的簡(jiǎn)單，用簡(jiǎn)單的原理，向我們展示了一個(gè)復(fù)雜的問(wèn)題。
