Pagerank 算法背景,、原理,、矩陣化計(jì)算
2.3.1Pagerank 算法背景伴隨著全球計(jì)算機(jī)信息技術(shù)的飛速發(fā)展，通過(guò)互聯(lián)網(wǎng)搜尋來(lái)獲取信息給用 戶(hù)的生活帶來(lái)了巨大的便利。但是人們?cè)鯓硬拍茉诤棋男畔⒑Ｑ笾锌焖偎褜?到有用的信息呢,？ 1988年,，Google公司的創(chuàng)始人、Stanford大學(xué)計(jì)算機(jī)博士 Lawrence Page和Sergey Brin合作共同研究出了 Pagerank算法[85],，通過(guò)這種算 法能對(duì)搜索引擎上的網(wǎng)頁(yè)的相關(guān)性和重要性進(jìn)行排名,，從而在信息篩選方面給 用戶(hù)提供便利。伴隨著Google公司在全世界范圍內(nèi)取得巨大成功,，Pagerank算 法也成為全球經(jīng)典的十大數(shù)據(jù)挖掘算法及改變未來(lái)的九大算法之一,。互聯(lián)網(wǎng)上 龐大的網(wǎng)頁(yè)群之間彼此鏈接存在著十分復(fù)雜的相關(guān)性,，Pagerank算法正是基于 網(wǎng)頁(yè)的鏈接關(guān)系來(lái)進(jìn)行網(wǎng)頁(yè)的排序,，網(wǎng)頁(yè)的重要度高低直接決定著其排名的高 低。2.3.2Pagerank 算法原理Pagerank算法是單純依據(jù)頁(yè)面之間的復(fù)雜鏈接關(guān)系來(lái)進(jìn)行重要度計(jì)算,，每 個(gè)頁(yè)面的重要度指標(biāo)為其Pagerank值（下文將簡(jiǎn)稱(chēng)PR值),，重要度高的頁(yè)面將 對(duì)應(yīng)較高的PR值，而不太重要的網(wǎng)頁(yè)將對(duì)應(yīng)較低的PR值,。表2.1是部分國(guó)內(nèi) 網(wǎng)站的PR值排名,。通過(guò)表格可知PR值與網(wǎng)頁(yè)的反鏈數(shù)有關(guān)，所謂反鏈數(shù)即從 其他網(wǎng)頁(yè)導(dǎo)入本網(wǎng)頁(yè)的鏈接數(shù)量（在有向圖中稱(chēng)為入度）,。一般來(lái)講反鏈數(shù)越多 (入度越大）,，其PR值也越大，但通過(guò)表格統(tǒng)計(jì)發(fā)現(xiàn)騰訊網(wǎng)的反鏈數(shù)為1252835 個(gè),，在所有網(wǎng)頁(yè)中是最多的,，但是其PR值僅僅排在第三位，這是因?yàn)轫?yè)面的 PR值不僅與其反鏈數(shù)有關(guān),，還與被鏈接過(guò)來(lái)網(wǎng)頁(yè)的重要度有關(guān),。就像在由多個(gè) 社會(huì)個(gè)體組成的社會(huì)關(guān)系網(wǎng)絡(luò)中衡量個(gè)體的社會(huì)影響力，不僅需要朋友越多,， 而且還要朋友質(zhì)量越高才代表個(gè)體的社會(huì)地位越高,。所以Pagemnk算法的主要原理是：如果頁(yè)面A能夠鏈接到頁(yè)面B，那么將 認(rèn)為頁(yè)面A傳遞給頁(yè)面B —個(gè)重要度值（PR值）,，此值的大小取決于頁(yè)面A的 重要度（PR值）以及其出鏈數(shù),，并假設(shè)任何頁(yè)面的重要度都被平均傳遞到它所 鏈接的頁(yè)面。由于網(wǎng)頁(yè)之間存在相互鏈接關(guān)系,，這個(gè)計(jì)算過(guò)程會(huì)一直迭代下去,， 最后根據(jù)頁(yè)面迭代后的平穩(wěn)PR值進(jìn)行排序?；谶@一思想,，將整個(gè)互聯(lián)網(wǎng)系 統(tǒng)抽象成一個(gè)有向圖G= (V,，E)，其中將n個(gè)頁(yè)面抽象成網(wǎng)絡(luò)圖的節(jié)點(diǎn)V,，用有向邊E代表頁(yè)面之間的鏈接關(guān)系,。若網(wǎng)頁(yè)'、％,、...Vk是鏈入到網(wǎng)頁(yè)A的頁(yè)面 節(jié)點(diǎn),，那么網(wǎng)頁(yè)A的PR值PR(A)計(jì)算公式為：式（2.4)中PR(Vi)和CCV；)為分別為頁(yè)面節(jié)點(diǎn)'的PR值和出度,；根據(jù) Pagerank算法原理我們可以總結(jié)出：①鏈入到頁(yè)面A的網(wǎng)頁(yè)數(shù)量k越大,，頁(yè)面A的PR值就會(huì)越大，頁(yè)面A的重要度越大,；②頁(yè)面A的鏈入頁(yè)面乂,、％、...'的重要度越大,，頁(yè)面A會(huì)受它們的影響變得更重要,；③頁(yè)面節(jié)點(diǎn)\的出度越大，即CCVD越大,，那么頁(yè)面節(jié)點(diǎn)A從頁(yè)面節(jié)點(diǎn)乂處 分得的PR值越少,。公式（2.4)假設(shè)當(dāng)用戶(hù)在瀏覽頁(yè)面\時(shí)，下一個(gè)瀏覽頁(yè)面是均勻地選擇下一個(gè)其所指向的頁(yè)面,。Pagemnk算法可以用隨機(jī)沖浪模式來(lái)進(jìn)行刻畫(huà)[85],，用戶(hù) 在互聯(lián)網(wǎng)上隨機(jī)瀏覽網(wǎng)頁(yè)，那么網(wǎng)頁(yè)的重要度和網(wǎng)頁(yè)被訪(fǎng)問(wèn)的概率成正比,，得 到的PR值就是網(wǎng)頁(yè)被訪(fǎng)問(wèn)的概率和網(wǎng)頁(yè)排序的依據(jù),。如圖有6個(gè)頁(yè)面A、B,、 C,、D、E,、F,，假如初始PR值都是1，那么： 圖中頁(yè)面節(jié)點(diǎn)重要度排名依次是B,、A,、C、E,、F,、D，圖2.7所示的有向 圖是一種非常理想的情況,，節(jié)點(diǎn)的重要度只能沿著有向邊進(jìn)行傳遞,，是否任何 有向圖經(jīng)過(guò)反復(fù)迭代后會(huì)達(dá)到平穩(wěn)狀態(tài)呢,？顯然不會(huì)，由若干個(gè)節(jié)點(diǎn)組成的有 向圖中,，如果存在以下3種情況，那么節(jié)點(diǎn)的PR值將不會(huì)收斂,。①如果存在強(qiáng)連通圖（圖中任意節(jié)點(diǎn)相互可達(dá)）只有入鏈沒(méi)有出鏈,，我們 稱(chēng)這種情況為等級(jí)下沉（Rank sinks)如圖2.9所示，網(wǎng)頁(yè)節(jié)點(diǎn)D,、E,、F組成的強(qiáng)連通圖只有入鏈沒(méi)有出鏈，那么來(lái)自其他節(jié)點(diǎn)的PR值進(jìn)入強(qiáng)連通圖后會(huì)一 直停留,，無(wú)法進(jìn)入節(jié)點(diǎn)A,、B、C,。最終的結(jié)果是節(jié)點(diǎn)D,、E、F的PR值會(huì)一直 增大,，直到節(jié)點(diǎn)A,、B、C的PR值為0,，那么PR值的計(jì)算將失去意義,。②如果有向圖中存在節(jié)點(diǎn)F只有鏈入的頁(yè)面節(jié)點(diǎn)，并且出度為0,如圖2.10 所示,，我們稱(chēng)之為等級(jí)泄露（Rank leaks),，那么頁(yè)面訪(fǎng)問(wèn)將被困在頁(yè)面節(jié)點(diǎn)F， 頁(yè)面節(jié)點(diǎn)A,、B,、C、D,、E的PR值終將會(huì)變?yōu)?,，而節(jié)點(diǎn)F的PR值將達(dá)到最 大，顯然這種情況也無(wú)法通過(guò)迭代獲得平穩(wěn)的PR值,。③有向圖中存在節(jié)點(diǎn)F的出度和入度都為0,，我們稱(chēng)之為孤立節(jié)點(diǎn)，如圖 2.11,，那么按照公式（2.4),，節(jié)點(diǎn)F的PR值將會(huì)為0,但是頁(yè)面F還有被用戶(hù) 訪(fǎng)問(wèn)的可能，顯然PR值為0不符合實(shí)際,。其中PR (A)為網(wǎng)頁(yè)A的PR值,，n為總頁(yè)面的數(shù)量,，'、,、...'代表能夠鏈入A的頁(yè)面,，CCX)為頁(yè)面節(jié)點(diǎn)\的出度，d為阻尼因子,，它是為了避免等級(jí) 下沉或登記泄露而設(shè)立的緩沖因子,，它代表頁(yè)面沿著鏈接方向進(jìn)行傳遞的概率為d，谷歌公司一般取為d=0.85,，每條鏈接對(duì)應(yīng)傳遞的PR值都是 考慮到孤立節(jié)點(diǎn)的存在,，賦予每個(gè)頁(yè)面節(jié)點(diǎn)一個(gè)PR初始值^^。2.3.3PR值的矩陣化計(jì)算當(dāng)有向圖中節(jié)點(diǎn)比較少時(shí),，可以通過(guò)解方程組的方式進(jìn)行節(jié)點(diǎn)的PR值計(jì) 算,，但是當(dāng)節(jié)點(diǎn)數(shù)量比較龐大時(shí)，這種方法就顯得難以實(shí)現(xiàn),。Pagerank算法假 設(shè)用戶(hù)所瀏覽的網(wǎng)頁(yè)與過(guò)去的瀏覽歷史無(wú)關(guān),，依賴(lài)現(xiàn)有的瀏覽狀態(tài)，可以看作是一個(gè)馬爾可夫過(guò)程,，那么對(duì)于n個(gè)頁(yè)面和鏈接關(guān)系組成的有向圖G = (V,，E)，其鄰接矩陣C中元素為1的個(gè)數(shù)為有向圖的鏈接數(shù),，將矩陣C每行元素除以此 行元素的總和（行元素全為0除外）會(huì)得到一個(gè)矩陣C',，矩陣Cf每行元素之 和都為1，那么矩陣C'可以看作是馬爾科夫轉(zhuǎn)移概率矩陣,。圖2.7所示的有向 圖的鄰接矩陣及轉(zhuǎn)移概率矩陣分別為：若指定一個(gè)n維向量P,，向量的分量分別代表各個(gè)網(wǎng)頁(yè)節(jié)點(diǎn)的PR值，Px+1表示第（x+1)次迭代所得到的各個(gè)網(wǎng)頁(yè)的PR值所組成的（nxl)矩陣,，用概率轉(zhuǎn) 移矩陣計(jì)算PR值的公式為：其中E為（nxl)階矩陣并且元素全為1,，設(shè)S為指定的迭代收斂平穩(wěn)閥值， 取各網(wǎng)頁(yè)節(jié)點(diǎn)的初始PR值P1,，迭代計(jì)算當(dāng)滿(mǎn)足|PX+1-PX|<S時(shí),，迭代結(jié)束。 所以Pagemnk算法的實(shí)現(xiàn)過(guò)程可以通過(guò)如圖2.12所示的算法流程圖來(lái)進(jìn)行刻畫(huà),。本文采摘自“基于故障率相關(guān)的加工中心的可靠性及風(fēng)險(xiǎn)評(píng)估”,，因?yàn)榫庉嬂щy導(dǎo)致有些函數(shù)、表格,、圖片,、內(nèi)容無(wú)法顯示，有需要者可以在網(wǎng)絡(luò)中查找相關(guān)文章,！本文由海天精工整理發(fā)表文章均來(lái)自網(wǎng)絡(luò)僅供學(xué)習(xí)參考,，轉(zhuǎn)載請(qǐng)注明,！