一式解讀 PageRank

Posted By Mr. Saturday

pagerank大家都說一圖抵得千言萬語,也許對於學習數學的人來說,一個數學公式也是「一式抵得千言萬語」,我們這邊就拿 PageRank 這個演算法來講好了,PageRank 一直是搜尋引擎最佳化這個產業最為關注的焦點之一,那麼你的網頁 PageRank 是怎麼算出來的?請看以下的式子:

$latex PR(A)=0.15+0.85*(\frac{PR(T_{1})}{C(T_{1})}+\frac{PR(T_{2})}{C(T_{2})}+…+\frac{PR(T_{n})}{C(T_{n})})$

其中

  • T1 到 Tn 是連結到你的 n 個網頁
  • PR(A) 是你網頁的 PageRank 值
  • PR(T1) 是 T1 這個網頁的 PageRank 值,以此類推
  • C(T1) 是 T1 這個網頁對外的連結數目,以此類推

看看上面這個公式翻譯成白話文的話,就是假設有 n 個網頁連結到你的網站,那麼你的 PageRank 就是這些網頁個別的 PageRank 值除以他們個別的對外連結數目,再白話一點,在你的立場來看,別人的 PageRank 值就是他們手上握有的投票數目,他們對外連結的數目就代表了他們把自己手中的票均分成幾份投了出去。也就是說,別人連結到你的網站,就表示他投了票給你,但是這票的效力有多少,就取決於他把票投給了幾個人,如果他手中的 PageRank 值是 5 (也就是五票),而他把票投給 10 個人的話 (也就是有十個對外連結),那麼你從他手中拿到的票就只有 0.5 票。

所以,連結到你網站的網頁越多,你的 PageRank 就越高,這個結論大致上是對的,但是如果連結到你的網站的連結都是一些很弱的連結 (對方有太多的對外連結或是 PageRank 不夠高),那麼你的 PageRank 就比較難以累積。當大家談到 PageRank 時,都喜歡說「一個連結就是一票」,其實從上面的簡單分析就知道這是不太正確的。在 PageRank 的世界中,不是每個網站都是人人平等、人人一票,有的人可以有好多票,而且要把這些票分多細去投都可以。

這樣的投票機制會衍伸出一個問題,對於你自己的網站而言,如果有很多人去你那邊留言,並且在留言中留下連結到他們自己的網站 ,那麼你的 PageRank 值就會有一些被分到這些網站去,如此一來,其他你自己真正有價值的對外連結,效力就會被減弱,投票變成了偷票。要避免這個問題很簡單,Google 已經在 2005 年就給大家一個解決方案,你只要告訴 Google 不要讓這些連結去瓜分你的 PageRank 就可以了。如果你懂得一點 HTML,方法就是在原本的連結 tag 之中加上 rel=”nofollow” 這個 attribute:

如果某個網友跑來你這邊留下連結:
<a href="http://certain-link.com">歡迎參觀</a>
你只要把上面的 code 改成
<a href="http://certain-link.com" rel="nofollow">歡迎參觀</a>

這樣子一來你的 PageRank就不會被這個連結瓜分出去了,這種 tag 方式可以告訴搜尋引擎不要把這個連結納入 PageRank 的計算,MSN Search 和 Yahoo Search 都認得這種 tag 方式。

值得注意的是,Google 在決定網頁的搜尋結果排名時,PageRank 只是其中一項依據, 畢竟 PageRank 的計算與搜尋的內容無關,是一個絕對的數值,所以在決定搜尋結果的排名時,Google 還要看使用者是在搜尋什麼東西,用另外的機制來決定網頁的排名,而這就是另外一個故事了。

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!
  • scott

    Dear Mr. Saturday:

    公式中 0.85 是一個 damping factor , 不曉得大大清不清楚這個值是怎麼定來的??一定都是0.85嗎? 又 1-0.85=0.15 , 是不是表示每個page的Pagerank 最低值是0.15 ?

    3Q

  • scott

    Dear Mr. Saturday:

    公式中 0.85 是一個 damping factor , 不曉得大大清不清楚這個值是怎麼定來的??一定都是0.85嗎? 又 1-0.85=0.15 , 是不是表示每個page的Pagerank 最低值是0.15 ?

    3Q

  • To Scott,
    0.85 這個 damping factor 是 Larry Page 和 Sergey Brin 建議使用的一個值,雖然我這篇文章講的公式很直覺好懂,但是實際上 Google 在計算整個網路上所有網站的 PageRank 時,會需要用 Iterative 的方法來進行大規模的矩陣運算,來求一個 Markov Chain 的穩定收斂狀態 (這個穩定狀態就是最後的 PageRank 值),其中一個 Iterative 的方法是 power method,而式子中的這個 damping factor 會影響到 power method 計算的收斂速度和時間長短,這個值越接近零,收斂得就越快 (通常收斂時,誤差範圍是在 10 的 -10 次方以下),但是這個時候 teleportation matrix 的 artificiality 問題會比較大,反之,這個值越接近一,計算的時間一方面爆增到不可忍受的地步,一方面算出來的東西會比較 sensitive (網路有小小變動,整個 PageRank 結果會大變動),但是得出來的結果理論上比較 effective。
    所以這個 damping factor 其實是一個在零與一之間關於計算時間和有效性的 tradeoff,如果你有興趣,建議你看看矩陣運算的書囉。

  • To Scott,
    0.85 這個 damping factor 是 Larry Page 和 Sergey Brin 建議使用的一個值,雖然我這篇文章講的公式很直覺好懂,但是實際上 Google 在計算整個網路上所有網站的 PageRank 時,會需要用 Iterative 的方法來進行大規模的矩陣運算,來求一個 Markov Chain 的穩定收斂狀態 (這個穩定狀態就是最後的 PageRank 值),其中一個 Iterative 的方法是 power method,而式子中的這個 damping factor 會影響到 power method 計算的收斂速度和時間長短,這個值越接近零,收斂得就越快 (通常收斂時,誤差範圍是在 10 的 -10 次方以下),但是這個時候 teleportation matrix 的 artificiality 問題會比較大,反之,這個值越接近一,計算的時間一方面爆增到不可忍受的地步,一方面算出來的東西會比較 sensitive (網路有小小變動,整個 PageRank 結果會大變動),但是得出來的結果理論上比較 effective。
    所以這個 damping factor 其實是一個在零與一之間關於計算時間和有效性的 tradeoff,如果你有興趣,建議你看看矩陣運算的書囉。

  • Muser

    Google 從未公開真正 Pagerank 的演算法,
    只有在最初兩位大頭的博士論文當中略見端倪,
    可是後來在 Google 與 Yahoo! 合作、分家,
    所使用的演算法都不一樣,這個數學式是從哪裡來的,
    能否說明?@@

  • Muser

    Google 從未公開真正 Pagerank 的演算法,
    只有在最初兩位大頭的博士論文當中略見端倪,
    可是後來在 Google 與 Yahoo! 合作、分家,
    所使用的演算法都不一樣,這個數學式是從哪裡來的,
    能否說明?@@

  • Hi, Muser,
    Google的PageRank演算法在Web上討論相當熱烈,Mr. Saturday只有稍微解釋了一下。如果你對PageRank很有興趣的話,可以看Smashing Magazine的這一篇:)
    http://www.smashingmagazine.com/2007/06/05/google-pagerank-what-do-we-really-know-about-it/

  • Hi, Muser,
    Google的PageRank演算法在Web上討論相當熱烈,Mr. Saturday只有稍微解釋了一下。如果你對PageRank很有興趣的話,可以看Smashing Magazine的這一篇:)
    http://www.smashingmagazine.com/2007/06/05/google-pagerank-what-do-we-really-know-about-it/

  • Pingback: 本日書籤 06/ 7/2007 « penk - Keep on rockin’ in the free world()

  • Pingback: Top Posts « WordPress.com()

  • 現在的搜尋結果已經和PAGERANK有很大差異了,建議多看依下他們新的專利申請文件。

    http://www.pjhuang.net/pagerankblog/2007/04/seo.html

  • 現在的搜尋結果已經和PAGERANK有很大差異了,建議多看依下他們新的專利申請文件。

    http://www.pjhuang.net/pagerankblog/2007/04/seo.html

  • To pjhuang,

    謝謝您提供的資料,我這邊的 PageRank 公式是簡化過後的版本 (實際上 Page 和 Brin 提出的原始公式更為簡化),據我個人所知的範圍,Google 對於網頁的評價機制,除了 PageRank 的細節有所調整之外,還另外加入了 100 種以上其他的演算法在計算網頁的絕對排名。但是整個評價的方向並沒有偏離這個簡化的公式太多,我文章中提出的解釋也因此還是適用的。所以並不能說現在的排名結果跟 PageRank 有很大的差異。:)

  • To pjhuang,

    謝謝您提供的資料,我這邊的 PageRank 公式是簡化過後的版本 (實際上 Page 和 Brin 提出的原始公式更為簡化),據我個人所知的範圍,Google 對於網頁的評價機制,除了 PageRank 的細節有所調整之外,還另外加入了 100 種以上其他的演算法在計算網頁的絕對排名。但是整個評價的方向並沒有偏離這個簡化的公式太多,我文章中提出的解釋也因此還是適用的。所以並不能說現在的排名結果跟 PageRank 有很大的差異。:)

  • Pingback: SmallKen's Blog » Blog Archive » 說什麼是 PageRank?()

  • Pingback: 一式解讀 PageRank « 謝一瑋 (部落格)()

  • Pingback: Web [email protected] : Eurekster swicki - 打造專屬的迷你搜尋引擎 « Mr./Ms. Days - 網路, 資訊, 觀察, 生活()

  • smith

    已經是很久以前的舊文了,不過今天才看到,就來補充一下。

    如果我們不要用投票的觀點來看PageRank。

    使用者之所以會到訪一個網頁,簡單分成兩種情況:

    情況1. 使用者一開始就知道這個網頁,「直接」到訪這個網頁。

    情況2. 使用者是從別的網頁連過來,「間接」到訪這個網頁。

    對任何一個網頁來說,第1種情況發生的機率是15%,第2種情況發生的機率是85%。

    假設有一個page A,沒有任何其它的page有連結它。
    那麼依據這個概念,它的PageRank就是0.15,因為總是會有人不透過其它網頁而直接到訪page A(例如page A的作者)。

    所以,在決定damping factor 時,有必要在一開始的時候,盡量貼近現實世界當中「情況1」與「情況2」的比例(當然這個所謂現實世界的比例就有許多主觀判斷的成份在內),才有個判斷是否「effective」的依據。

    之後,再由可取得的計算能力及要求的誤差範圍來進行調整會較為合理。

  • smith

    已經是很久以前的舊文了,不過今天才看到,就來補充一下。

    如果我們不要用投票的觀點來看PageRank。

    使用者之所以會到訪一個網頁,簡單分成兩種情況:

    情況1. 使用者一開始就知道這個網頁,「直接」到訪這個網頁。

    情況2. 使用者是從別的網頁連過來,「間接」到訪這個網頁。

    對任何一個網頁來說,第1種情況發生的機率是15%,第2種情況發生的機率是85%。

    假設有一個page A,沒有任何其它的page有連結它。
    那麼依據這個概念,它的PageRank就是0.15,因為總是會有人不透過其它網頁而直接到訪page A(例如page A的作者)。

    所以,在決定damping factor 時,有必要在一開始的時候,盡量貼近現實世界當中「情況1」與「情況2」的比例(當然這個所謂現實世界的比例就有許多主觀判斷的成份在內),才有個判斷是否「effective」的依據。

    之後,再由可取得的計算能力及要求的誤差範圍來進行調整會較為合理。

  • Pingback: 從連結炸彈到排行榜炸彈? « Mr./Ms. Days - 網路, 資訊, 觀察, 生活()

  • Pingback: 部落()

  • Pingback: [Mr./Ms. Days] 部落格: 企業公關的新面向 | ottblog.taiwansamsung.com()

  • Pingback: Google 讓我們變笨 ? - MMDays()

  • Pingback: My Homepage()