1缨称、首先先大致介紹下pagerank，pagerank是Google排名算法法則的一部分祝迂，是用來標記網(wǎng)頁的等級的一種方法睦尽，也是用來衡量一個網(wǎng)頁好壞的唯一標準。pagerank他采用PR值來劃分網(wǎng)頁的受歡迎度型雳，PR值越高当凡，則表名受歡迎度越高山害，PR最高為10，最低為0沿量，一般PR達到4浪慌，則表名網(wǎng)站已經(jīng)不錯了。PR為4的網(wǎng)站比PR為3的網(wǎng)站不是單純的好一點來形容朴则，他是一種里氏震級的形式來形容的权纤，就好比地震的等級，是指數(shù)刻度增長的乌妒，因此可以想象PR為10的網(wǎng)站是一種什么程度汹想。因為這個算法是Google提出的，因此Google將自己的網(wǎng)站PR值設置為10撤蚊，所以想要自己的網(wǎng)站PR達到10古掏，是非常難的，如果你的網(wǎng)站可以達到Google的水平侦啸。
2槽唾、介紹完了pagerank是一個什么東西后，我們就來介紹一下pagerank如何計算的匹中。
2.1夏漱、用個例子來說明下PageRank算法
在網(wǎng)頁A中有B、C顶捷、D三個鏈接挂绰，在網(wǎng)頁B中有A、C兩個個鏈接服赎，在網(wǎng)頁C中有D鏈接葵蒂，網(wǎng)頁D中有A、B兩個鏈接重虑。（可以看出這個圖是強鏈接的践付，任何一個節(jié)點都可以到達另一個節(jié)點）。
我們假設每一個鏈接訪問的概率是相同的缺厉，為了計算方便我們將每一個網(wǎng)頁的PageRank設置為1永高。
先給出計算公式
PR(pj) 表示網(wǎng)頁 pj 的 PageRank 得分，L(pj) 表示網(wǎng)頁 pj 的出鏈接數(shù)量提针，1/L(pj) 就表示從網(wǎng)頁 pj 跳轉(zhuǎn)到 pi 的概率命爬。
所以我們來計算第一次迭代后的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
通過上面的公式在不斷的進行迭代，可以得到一個收斂值辐脖，大概是在（0.265饲宛，0.235，2.206嗜价，0.294）附近艇抠。
2.2看完公式之后幕庐，我們來考慮倆種特殊的情況
2.2.1終止問題
上面過程要滿足收斂性，需要具備一個條件：圖是強連通的家淤，即從任意網(wǎng)頁可以到達其他任意網(wǎng)頁异剥。
互聯(lián)網(wǎng)中存在網(wǎng)頁不滿足強連通的特性，因為有一些網(wǎng)頁不指向任何網(wǎng)頁絮重，按照上面公式迭代計算下去届吁，導致前面累計得到的轉(zhuǎn)移概率被清零，最終得到的概率分布向量所有元素幾乎都為0绿鸣。
假設把上面圖中C到D的鏈接丟掉，C變成了一個終止點暂氯，得到下面這個圖：
轉(zhuǎn)移矩陣M為：
不斷迭代潮模，最終得到所有元素都為0。
2.2.2痴施、陷阱問題
陷阱問題：是指有些網(wǎng)頁不存在指向其他網(wǎng)頁的鏈接擎厢，但存在指向自己的鏈接。比如下面這個圖：
這種情況下辣吃，PageRank算法不斷迭代會導致概率分布值全部轉(zhuǎn)移到c網(wǎng)頁上动遭，這使得其他網(wǎng)頁的概率分布值為0，從而整個網(wǎng)頁排名就失去了意義神得。如果按照上面圖則對應的轉(zhuǎn)移矩陣M為：
不斷迭代厘惦，最終得倒如下結(jié)果：
為了解決終止點問題和陷阱問題，下面需要對算法進行改進哩簿。假設選取下一個跳轉(zhuǎn)頁面時宵蕉，既不選當前頁面，也不選當前網(wǎng)頁上的其他鏈接节榜，而是以一定概率跳轉(zhuǎn)到其他不相關網(wǎng)頁羡玛，那么上面兩個問題就能得到很好的解決，這就是完整PageRank算法思想宗苍。
N表示的時網(wǎng)頁鏈接的個數(shù)稼稿，α表示不進行隨機跳轉(zhuǎn)的概率。
利用上面公式繼續(xù)迭代下去讳窟，直到收斂让歼，得到最終rank值。
PageRank 的計算是采樣迭代法實現(xiàn)的：一開始所有網(wǎng)頁結(jié)點的初始 PageRank 值都可以設置為某個相同的數(shù)挪钓，例如 1是越，然后我們通過上面這個公式，得到每個結(jié)點新的 PageRank 值碌上。每當一張網(wǎng)頁的 PageRank 發(fā)生了改變倚评，它也會影響它的出鏈接所指向的網(wǎng)頁浦徊，因此我們可以再次使用這個公式，循環(huán)地修正每個網(wǎng)頁結(jié)點的值天梧。由于這是一個馬爾科夫過程盔性，所以我們能從理論上證明，所有網(wǎng)頁的 PageRank 最終會達到一個穩(wěn)定的數(shù)值呢岗。整個證明過程很復雜冕香，這里我們只需要知道這個迭代計算的過程就行了。
3后豫、基于本文主題叫做數(shù)學建模之美悉尾，也是一篇讀后感，所以我們還是寫一下感受吧挫酿。
鏈接：https://pan.baidu.com/s/1qMKEbBTcuNekgqevPTVAWQ
提取碼：aorr
這個算法的優(yōu)美之處构眯，就在于巧妙地將網(wǎng)頁內(nèi)容的好壞，根據(jù)鏈接數(shù)的形式早龟，用PR值進行了排名惫霸，它不僅激發(fā)網(wǎng)頁越做越好，也促進了各個網(wǎng)頁之間的聯(lián)系葱弟。
同時在結(jié)構(gòu)方面壹店，他將一個復雜的問題，進行了簡單的類比芝加，用圖結(jié)構(gòu)的形式代替鏈接的形式硅卢，用戶訪問的順序，也就是節(jié)點的走向藏杖。所以數(shù)學之美就在于他是非常的簡單老赤，用簡單的原理，向我們展示了一個復雜的問題制市。
