第8章 鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計及核心算法

1、第 8 章 鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計及核心算法本章內(nèi)容： 萬維網(wǎng)鏈接結(jié)構(gòu)圖及特性； 鏈接結(jié)構(gòu)分析方法的形式化基礎(chǔ)； 鏈接結(jié)構(gòu)分析Page Rank 算法、HITS 算法； 鏈接結(jié)構(gòu)分析結(jié)果在搜索結(jié)果排序中的應(yīng)用。8.1 萬維網(wǎng)鏈接結(jié)構(gòu)圖萬維網(wǎng)的鏈接結(jié)構(gòu)可用有向圖來描述，網(wǎng)頁是節(jié)點(diǎn)，超鏈接是有向邊。從源網(wǎng)頁指向目的網(wǎng)頁的超鏈接，為源網(wǎng)頁的“出鏈接”，為目的網(wǎng)頁的“入鏈接”。l 節(jié)點(diǎn) A-H 表示網(wǎng)頁；l 鏈接關(guān)系用有向邊來表示；l 網(wǎng)頁 A、B、C 之間的雙向邊，表示三個網(wǎng)頁之間相互鏈接；l 網(wǎng)頁F與G各自有一個指向自身的有向邊。鏈接結(jié)構(gòu)關(guān)系圖的鄰接矩陣描述。鄰接矩陣是用來描述圖中節(jié)點(diǎn)鄰接關(guān)系的一

2、種方式，設(shè)n為鏈接結(jié)構(gòu)圖 Graph 的節(jié)點(diǎn)規(guī)模，則鄰接矩陣 M 是一個n*n的矩陣，其中某個元素 mi,j的取值滿足：圖 8.1 所示鏈接結(jié)構(gòu)圖，其鄰接矩陣如下：萬維網(wǎng)鏈接圖GWeb (V, E) V：節(jié)點(diǎn)集合，V = v1 , v2 , v3 ， ， vn，節(jié)點(diǎn)數(shù)|V| = n ; E ：邊集合， E = e1 , e2 , e3 ， ，em，邊數(shù)|E|=m 。將萬維網(wǎng)的整個鏈接結(jié)構(gòu)圖作為對象來研究不僅對理解萬維網(wǎng)的各種屬性有直接的意義，同時還對搜索引擎領(lǐng)域的相關(guān)算法研究也有著重要的幫助。很多實(shí)驗(yàn)和觀察促進(jìn)了萬維網(wǎng)鏈接圖結(jié)構(gòu)的研究。針對圖 GWeb ( V , E )，研究； V、E的規(guī)模

3、； 拓?fù)浣Y(jié)構(gòu)； 節(jié)點(diǎn)入度、出度分布。圖G ( V , E）的某節(jié)點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為該節(jié)點(diǎn)的“度”。對于圖 GWeb ( V , E）而言，某節(jié)點(diǎn)的入度就是指以該節(jié)點(diǎn)作為目的網(wǎng)頁的超鏈接數(shù)（該節(jié)點(diǎn)入鏈接數(shù)）；某節(jié)點(diǎn)的出度則是指以該節(jié)點(diǎn)為源網(wǎng)頁的超鏈接數(shù)（該節(jié)點(diǎn)出鏈接數(shù)）。8.1.1 萬維網(wǎng)鏈接圖的規(guī)模GWeb (V, E）規(guī)模難以統(tǒng)計(1) 圖中的節(jié)點(diǎn)存在形式復(fù)雜； 非自由訪問的網(wǎng)頁（網(wǎng)頁對用戶訪問加以限制，如采取登錄策略等）； 自由訪問的網(wǎng)頁； 傳統(tǒng)形式的靜態(tài)頁面； 隨用戶查詢需求在服務(wù)器端實(shí)時生成的動態(tài)頁面； 用 Ajax 技術(shù)生成的 URL 相同但內(nèi)容千差萬別的頁面；(2) 超鏈接的界定，

4、存在諸多困難； “博客日歷”，每個日期都是一個超鏈接。服務(wù)器端自動生成的超鏈接VS網(wǎng)頁作者手工編輯添加的鏈接。GWeb ( V , E）的節(jié)點(diǎn)集合規(guī)模 通過域名注冊服務(wù)商可統(tǒng)計網(wǎng)站、域名數(shù)量且較為準(zhǔn)確； 統(tǒng)計網(wǎng)站涉及的網(wǎng)頁數(shù)目就會面臨上面提到的問題； 研究中通常用搜索引擎的索引規(guī)模來估算萬維網(wǎng)鏈接圖的節(jié)點(diǎn)規(guī)模； 沒被任何一個搜索引擎收錄的網(wǎng)頁，被用戶訪問到的可能性微乎其微； 2008年7月，谷歌索引量1萬億網(wǎng)頁，一定程度上反映了GWeb (V, E）節(jié)點(diǎn)集合的規(guī)模。GWeb ( V , E）的邊集合規(guī)模 估計邊集合規(guī)模更困難； 超鏈接的添加不需要登記、備案，各大搜索引擎也很少公布統(tǒng)計數(shù)據(jù)； 只

5、能通過實(shí)驗(yàn)性萬維網(wǎng)語料庫的相關(guān)數(shù)據(jù)對GWeb (V , E）的邊集合規(guī)模有一個概括性的認(rèn)識； AltaVista 語料庫，鏈接關(guān)系圖包含 2.03 億個網(wǎng)頁、14.66 億條鏈接。 Clueweb09 語料庫，鏈接關(guān)系圖包含的節(jié)點(diǎn)數(shù)為 1040 809705個，對應(yīng)的出鏈接數(shù)為7944351835個。 sogouT語料庫，鏈接關(guān)系圖包含1.39 億個網(wǎng)頁、33 . 4億條鏈接。從這些語料庫，可以估計，邊集合的規(guī)模要大于節(jié)點(diǎn)集合的規(guī)模，約為節(jié)點(diǎn)集合規(guī)模的幾到幾十倍。8.1.2 萬維網(wǎng)鏈接圖的連通情況定義：導(dǎo)出子圖給定 G=(V, E)，如果存在另外一個圖 G/=(V/,E/)，滿足V/包含于V，

6、E/包含于E，則稱G/是G的一個子圖。特別地，如果V/包含于V，且E/包含了在節(jié)點(diǎn)子集V/之間的所有邊，則稱G/是G的導(dǎo)出子圖。定義：強(qiáng)連通子圖給定一個有向圖，該有向圖的一個強(qiáng)連通子圖是指由一部分節(jié)點(diǎn)組成的一個導(dǎo)出子圖，對于該子圖中其中的任意兩個節(jié)點(diǎn)u和v，都存在一條路徑使得從u可以訪問到v。性質(zhì)：1、一個有向圖中可有多個強(qiáng)連通子圖。2、強(qiáng)連通子圖之間不存在公有節(jié)點(diǎn)；否則可以合二為一。對萬維網(wǎng)連接圖，每個強(qiáng)連通子圖都代表著構(gòu)成該子圖的節(jié)點(diǎn)是相互連通的，通過超鏈接通過一個網(wǎng)頁可訪問另一個。定義：弱連通子圖給定一個有向圖，該有向圖的一個弱連通子圖是指由一部分節(jié)點(diǎn)組成的一個導(dǎo)出子圖，對于該子圖中其中

7、的任意兩個節(jié)點(diǎn)u和v，都存在一條無向路徑使得從u可以訪問到v。對于萬維網(wǎng)鏈接圖，重點(diǎn)考察其包含的強(qiáng)、弱連通子圖的規(guī)模分布情況，借此了解整個鏈接圖的拓?fù)浣Y(jié)構(gòu)和連通情況。2000年，Broder的研究成果，萬維網(wǎng)鏈接結(jié)構(gòu)圖的強(qiáng)、弱連通子圖的規(guī)模分布情況如下圖所示。l 圖中，橫軸為連通子圖規(guī)模，縱軸為連通子圖數(shù)量；l 橫軸、縱軸使用對數(shù)坐標(biāo)軸。l 可以看出強(qiáng)連通子圖、弱連通子圖的規(guī)模分布規(guī)律基本相同；l 設(shè)連通子圖規(guī)模為Size，具有規(guī)模Size的連通子圖的數(shù)目Number近似滿足；指數(shù)形式表示為：幾點(diǎn)結(jié)論：l 規(guī)模大的連通子圖數(shù)目遠(yuǎn)小于規(guī)模小的連通子圖數(shù)目。l 規(guī)模最大的連通子圖所覆蓋的網(wǎng)絡(luò)資源數(shù)

8、量，占網(wǎng)絡(luò)資源總量中相當(dāng)比例。l 基于鏈接結(jié)構(gòu)抓取，很難抓取到網(wǎng)絡(luò)環(huán)境中所有數(shù)據(jù)，但通過抓取規(guī)模較大的連通子圖可獲取最主要部分的數(shù)據(jù)。規(guī)模最大的強(qiáng)連通子圖，其節(jié)點(diǎn)規(guī)模達(dá)到560余萬，此連通子圖在 Broder研究的網(wǎng)頁集合總規(guī)模中占有近28%的網(wǎng)頁。以此連通子圖為中心，考察其他網(wǎng)頁與此連通子圖的鏈接關(guān)系，可以對整個網(wǎng)絡(luò)頁面的鏈接結(jié)構(gòu)關(guān)系有一個清晰的認(rèn)識。根據(jù)Broder的研究結(jié)論繪制的萬維網(wǎng)鏈接結(jié)構(gòu)示意圖如下圖所示。Core部份規(guī)模最大的強(qiáng)連接子圖；IN部分所有鏈接到Core中網(wǎng)頁，且同時不被Core中的網(wǎng)頁所鏈接的網(wǎng)頁集合；OUT部分所有被Core中的網(wǎng)頁所鏈接，且同時不鏈接到Core中網(wǎng)頁

9、的網(wǎng)頁集合；Others部分剩余的網(wǎng)頁集合。萬維網(wǎng)鏈接和連通結(jié)構(gòu)概貌l 從IN中任何網(wǎng)頁，都可以鏈接到Core中網(wǎng)頁，進(jìn)而可訪問OUT中任何網(wǎng)頁。l IN、Core、OUT之外網(wǎng)頁，一部份與IN、OUT有鏈接關(guān)系，另一部分與IN、Core、OUT不相連的孤立點(diǎn)或點(diǎn)集合，規(guī)模約為所分析網(wǎng)頁總數(shù)的8.2%。l 萬維網(wǎng)鏈接結(jié)構(gòu)以Core為核心，構(gòu)成了“領(lǐng)結(jié)”形式的結(jié)構(gòu)。8.1.3 萬維網(wǎng)鏈接圖的入度和出度分布萬維網(wǎng)鏈接圖的入度、出度分別反映了某節(jié)點(diǎn)被其他節(jié)點(diǎn)鏈接，以及鏈接到其他節(jié)點(diǎn)的情況。萬維網(wǎng)鏈接圖 GWeb (V,E)的入度、出度分布符合冪律；入度為Indegree 的網(wǎng)頁數(shù)目 N ( Inde

10、gree ）近似滿足：出度為Outdegree 的網(wǎng)頁數(shù)目 N ( Outdegree ）近似滿足：其中、均為值大于零的參數(shù)，而C與 C/為常數(shù)。Broder的實(shí)驗(yàn)結(jié)果如下圖所示。8.2 超鏈接結(jié)構(gòu)分析的基礎(chǔ)超鏈接：兩個網(wǎng)頁或網(wǎng)頁的兩個不同部分之間的一種指向關(guān)系，源網(wǎng)頁是指包含超鏈接的網(wǎng)頁，目標(biāo)網(wǎng)頁是超鏈接所指向的網(wǎng)頁。超鏈接HTML格式：超鏈接的特性如果存在超鏈接L從頁面Psource指向頁面Pdestiny，則Psource與 Pdestiny滿足：特性1 :內(nèi)容推薦特性頁面Psource的作者推薦頁面Pdestiny的內(nèi)容，且利用L的鏈接文本內(nèi)容對Pdestiny進(jìn)行描述。特性2 :主題

11、相關(guān)特性被超鏈接連接的兩個頁面Psource與Pdestiny的頁面內(nèi)容涉及類似的主題。特性1說明：l 入鏈接個數(shù)是頁面受其他頁面推薦程度大小的標(biāo)志，入鏈越多，該頁面受其他網(wǎng)頁作者的推薦越多，其網(wǎng)頁內(nèi)容質(zhì)量高。l 入鏈接個數(shù)越少，說明該頁面不被其他網(wǎng)頁作者推薦，意味著頁面內(nèi)容或組織形式不受歡迎。l 鏈接文本起到對網(wǎng)頁內(nèi)容描述的作用，由于描述來自他人，通常被認(rèn)為是對網(wǎng)頁內(nèi)容更加客觀的描述。這就在頁面質(zhì)量與超鏈接結(jié)構(gòu)圖的拓?fù)潢P(guān)系間建立了聯(lián)系，為頁面內(nèi)容質(zhì)量評價提供了一種不基于內(nèi)容的方式。HITS 算法、PageRank算法是依據(jù)該特性設(shè)計的。特性2說明l 與特性1相比，特性2的重要程度、適用性低一

12、些；l Psource、Pdestiny頁面內(nèi)容相關(guān)的可能性要大于隨機(jī)抽取的兩個頁面；l 超鏈接表示的不僅是內(nèi)容相關(guān)關(guān)系。萬維網(wǎng)的超鏈接關(guān)系比特性1、特性2描述的復(fù)雜。導(dǎo)航欄鏈接l 源、目標(biāo)頁面的作者相同，不是內(nèi)容推薦關(guān)系，而是方便用戶訪問的設(shè)置。l 可以認(rèn)為符合特性2，顯然不符合特性1。廣告鏈接l 內(nèi)容推薦特性、主題相關(guān)特性都無法得到保證（尤其是主題相關(guān)性)。l 方面變化快、時效性強(qiáng)，對鏈接結(jié)構(gòu)分析造成了相當(dāng)?shù)睦щy。版權(quán)、注冊鏈接l 版權(quán)信息、注冊信息往往以超鏈接的形式存在，以便查閱；l 這類超鏈接數(shù)目大；l 不符合超鏈接應(yīng)具有的兩個特性。相當(dāng)多超鏈接不符合超鏈接算法設(shè)計中的假設(shè)l 各種鏈接

13、結(jié)構(gòu)分析算法在真實(shí)環(huán)境中無法單獨(dú)被用于網(wǎng)頁質(zhì)量評估l 改進(jìn)算法還是可以為頁面質(zhì)量評估提供參考；l 數(shù)據(jù)清理后的近似理想環(huán)境中，還是可以發(fā)揮作用。本章，假設(shè)萬維網(wǎng)結(jié)構(gòu)中的超鏈接滿足以上兩個特性。8.3 HITS 算法的基本思路及實(shí)現(xiàn)HITS算法：HITS是Hyperlink-Induced Topic Search的縮寫，基于超鏈接推演的主題搜索算法。核心思想；l 對網(wǎng)頁的“內(nèi)容權(quán)威度”、“鏈接權(quán)威度”進(jìn)行評價；l 內(nèi)容權(quán)威度 ( Authority Value )：網(wǎng)頁本身內(nèi)容的受歡迎程度；l 鏈接權(quán)威度（Hub Value ) ：網(wǎng)頁鏈接到其他受歡迎資源的程度。例：學(xué)術(shù)論文內(nèi)容權(quán)威度：內(nèi)容質(zhì)

14、量比較高、創(chuàng)新性較強(qiáng)、對學(xué)科發(fā)展能起到較大的推進(jìn)作用。鏈接權(quán)威度：對某個特定領(lǐng)域進(jìn)行了較為詳盡的調(diào)研，能夠介紹相當(dāng)數(shù)目的內(nèi)容質(zhì)量高的其他論文和研究工作。網(wǎng)頁內(nèi)容權(quán)威度：與網(wǎng)頁提供的內(nèi)容信息質(zhì)量有關(guān)，被其他網(wǎng)頁引用得越多，其內(nèi)容權(quán)威度越高。網(wǎng)頁鏈接權(quán)威度：與網(wǎng)頁提供的超鏈接質(zhì)量有關(guān)，網(wǎng)頁鏈向內(nèi)容質(zhì)量高的網(wǎng)頁越多，其鏈接權(quán)威度越高。HITS 算法所要解決的問題l 對用戶提交的大多數(shù)查詢，搜索引擎都會返回大量的相關(guān)查詢結(jié)果；l 大多數(shù)用戶傾向查找出結(jié)果集合中對獲取信息最有價值的那一部分網(wǎng)頁；l 算法的輸入：搜索引擎返回的與查詢主題在內(nèi)容上相關(guān)的結(jié)果集合；l 算法的輸出：對結(jié)果集合中網(wǎng)頁的內(nèi)容權(quán)威度、

15、鏈接權(quán)威度的評價。HITS 算法實(shí)施的階段：1、對用戶輸人的查詢主題，通過搜索，獲取內(nèi)容相關(guān)的網(wǎng)頁集合，適當(dāng)擴(kuò)展網(wǎng)頁集合；2、通過 “迭代一收斂”過程，計算網(wǎng)頁集合中每個頁面的鏈接權(quán)威度與內(nèi)容權(quán)威度，輸出按鏈接權(quán)威度、內(nèi)容權(quán)威度排序的結(jié)果列表。HITS算法在階段1，建立與查詢主題相關(guān)的圖（主題子圖）主題子圖給定查詢主題，構(gòu)造主題子圖過程：、用搜索引擎得到查詢主題的結(jié)果集合，稱為根集（Root Set）；、將所指向的網(wǎng)頁集合以及其他指向的網(wǎng)頁集合包含進(jìn)來形成集合，稱為基本集合（Base Set）。為控制圖的節(jié)點(diǎn)數(shù)量，施加的控制：l 搜索引擎返回結(jié)果數(shù)量大，將其限制在一個小的范圍內(nèi)，如設(shè)置為200

16、；l 某個網(wǎng)頁的鏈入網(wǎng)頁的數(shù)量大，將其限制在一個給定的范圍內(nèi)，如設(shè)置為50。為了消除導(dǎo)航用鏈接的影響，刪除站內(nèi)鏈接（即超鏈接的鏈源和鏈宿都在同一個主機(jī)上）。在構(gòu)造完主題子圖之后，可以通過迭代算法來計算出網(wǎng)頁的鏈接權(quán)威度、內(nèi)容權(quán)威度。網(wǎng)頁內(nèi)容權(quán)威度、網(wǎng)頁鏈接權(quán)威度間為相互加強(qiáng)的關(guān)系：l 具有較高網(wǎng)頁鏈接權(quán)威度的網(wǎng)頁應(yīng)該指向較多的網(wǎng)頁內(nèi)容權(quán)威度高的網(wǎng)頁；l 高網(wǎng)頁內(nèi)容權(quán)威度的網(wǎng)頁應(yīng)該被多個高網(wǎng)頁鏈接權(quán)威度的網(wǎng)頁所指向。對網(wǎng)頁i，令ai：內(nèi)容權(quán)威度；hi：鏈接權(quán)威度；B(i)：網(wǎng)頁i的入鏈接集；F(i)：網(wǎng)頁的出鏈接集；則有：例：頁面1的內(nèi)容權(quán)威度、鏈接權(quán)威度操作：計算內(nèi)容權(quán)威度；O操作：計算鏈接權(quán)

17、威度；對權(quán)值進(jìn)行規(guī)范化。l 規(guī)范化內(nèi)容權(quán)威度的公式：l 規(guī)范化鏈接權(quán)威度的公式：迭代地進(jìn)行操作、操作，直到最近兩輪迭代的規(guī)范化內(nèi)容權(quán)威度、鏈接權(quán)威度的差異很小，則認(rèn)為已收斂。HITS算法處理的對象個數(shù)相對較少，一般也就在幾萬個以內(nèi)，計算速度相對較快。因?yàn)樗敲嫦虿樵兊乃惴?，對用戶響?yīng)的時間要快，所以一般情況下只是求出次優(yōu)解就可以了。在Kleinberg的實(shí)驗(yàn)中，循環(huán)迭代20次，就可使前個（取之間）網(wǎng)頁排序足夠地穩(wěn)定了。例：針對結(jié)構(gòu)圖，計算每個網(wǎng)頁的鏈接權(quán)威度、內(nèi)容權(quán)威度。解：根據(jù)上圖構(gòu)造主題子圖，鄰接矩陣，表示為8.4 PageRank算法的基本思路及實(shí)現(xiàn) PageRank算法：l 拉里佩奇（

18、Larry Page）等人提出；l 根據(jù)WEB超鏈接關(guān)系對網(wǎng)頁重要程度進(jìn)行估計；l 2008年1月申請美國專利，同年在論文“The Anatomy of a Large-Scale Hyper textual Web Search Engine”中公開；l 將從頁面A到頁面B的超鏈接作為A向B的一次投票，但不是簡單地統(tǒng)計票數(shù)來衡量質(zhì)量高低，還要考慮投票者因素，較“重要”網(wǎng)頁的投票會更受重視。PageRank基于“從許多優(yōu)質(zhì)網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁”的思想判定網(wǎng)頁的重要性。PageRank衡量“網(wǎng)頁質(zhì)量”的方式l “質(zhì)量”定義有很強(qiáng)的主觀性；n 從時效性、頁面結(jié)構(gòu)組織、獨(dú)特性等角度定

19、義；n HITS算法的“鏈接權(quán)威度”與“內(nèi)容權(quán)威度”；l PageRank用戶隨機(jī)瀏覽互聯(lián)網(wǎng)時訪問到某個頁面的概率；隨機(jī)瀏覽模型 l 模型描述用戶對網(wǎng)頁的訪問行為；l 隨機(jī)體現(xiàn)在：瀏覽起始點(diǎn)選擇的隨機(jī)性、頁內(nèi)超鏈接選擇的隨機(jī)性；l 所用瀏覽器：n 無地址欄，無后退、前進(jìn)按鈕；不能輸入URL訪問網(wǎng)頁，且只能向前瀏覽不能回退；n 提供“隨便逛逛”功能，點(diǎn)擊“隨便逛逛”按鈕，挑選一個隨機(jī)的起點(diǎn)，開始瀏覽；l 可從網(wǎng)頁內(nèi)所含超鏈接中隨機(jī)選擇一個頁面繼續(xù)進(jìn)行瀏覽；l 沿著超鏈接前進(jìn)了一定數(shù)目的網(wǎng)頁后，對頁面內(nèi)容不感興，可使用“隨便逛逛”跳轉(zhuǎn)到另一個網(wǎng)頁上進(jìn)行瀏覽，如此反復(fù)。在瀏覽過程中，用戶訪問到某個頁

20、面的概率就稱為該頁面的PageRank。頁面PageRank計算：網(wǎng)頁被用戶訪問到的可能性有兩種。、使用“隨便逛逛”跳轉(zhuǎn)到頁面A假設(shè)“隨便逛逛”以隨機(jī)方式推薦網(wǎng)頁，互聯(lián)網(wǎng)上網(wǎng)頁總數(shù)為N，則用戶使用“隨便逛逛”訪問到網(wǎng)頁A的概率為1/N。、瀏覽過程中通過其他網(wǎng)頁上超鏈接訪問到頁面A假設(shè)鏈接到A的個網(wǎng)頁為 P，P，P，P。則用戶通過P訪問A的概率為：PageRank()*P( P=A)PageRank()：用戶訪問到頁面的概率，P( P=A)：用戶訪問頁面時，點(diǎn)擊鏈接到A頁面的超鏈接的概率。假設(shè)用戶瀏覽P時點(diǎn)擊頁面上各超鏈接概率相等；用戶通過P，P，P，P訪問到A的概率為：或假設(shè)。不存在不含超鏈接

21、的網(wǎng)頁，用戶主動使用“隨便逛逛”功能概率為a，則用戶訪問到頁面A的概率為：用戶使用“隨便逛逛”功能訪問到頁面A的概率；：用戶使用超鏈接訪問到頁面A的概率；可以看到，對給定的參數(shù)a，頁面A的PageRank值由鏈接到它的各個頁面的PageRank值決定的。如果考慮全萬維網(wǎng)頁面PageRank的計算，就會發(fā)現(xiàn)是一個迭代計算過程。PageRank（簡化）算法(1) 取萬維網(wǎng)鏈接結(jié)構(gòu)圖G , G的規(guī)模為N，即G中包括N個節(jié)點(diǎn)。對于 G 中的每一個節(jié)點(diǎn)n，設(shè) PR（n）是其PageRank值，而向量為G對應(yīng)的PageRank結(jié)果向量。(2) 設(shè)定，即：對G中每一個節(jié)點(diǎn)n，設(shè)定其初始值PR(0)(n)均為

22、。(3) For k= 1,2,3，TN對G中的每一個節(jié)點(diǎn)n , 其中，a為預(yù)先設(shè)定的參數(shù)，Outdegree (Pi)為頁面Pi的出度值。(4) 當(dāng)結(jié)果向量未收斂時，返回（3）繼續(xù)循環(huán)；當(dāng)收斂時，算法結(jié)束，輸出所計算出的G中每一個節(jié)點(diǎn)n的PR(n）的結(jié)果。例：如圖所示的鏈接結(jié)構(gòu)圖中，各個網(wǎng)頁都具有超鏈接，A頁面鏈向頁面B與C,B與C分別鏈向D頁面，而D頁面鏈回A頁面。我們可以依照上述PageRank 簡化算法計算圖8. 9的PageRank數(shù)值如下：隨后迭代的結(jié)果。由上表可見：l 進(jìn)行到第30次迭代，算法結(jié)果已經(jīng)基本收斂；l 第30次迭代的結(jié)果與第100次迭代的結(jié)果差別小于千分之一；l 采用

23、算法迭代30次左右的結(jié)果即可以滿足需求。l 迭代中頁面PageRank變化，但各頁面PageRank的和等于1；PageRank（簡化）算法的問題 l 有些網(wǎng)頁沒有出鏈接 TXT, DOC, JPG, 隨機(jī)瀏覽進(jìn)入死胡同 l 只能使用“隨便逛逛” 相當(dāng)于為“死胡同”網(wǎng)頁和G中的所有網(wǎng)頁之間添加了一條虛擬的出鏈接 “死胡同”網(wǎng)頁的PageRank借助“隨便逛逛”平均分配給G中的所有網(wǎng)頁 PageRank（標(biāo)準(zhǔn)）算法(1) 取萬維網(wǎng)鏈接結(jié)構(gòu)圖G , G的規(guī)模為N，即G中包括N個節(jié)點(diǎn)。對于G中的每一個節(jié)點(diǎn)n，設(shè)PR(n)是其PageRank值，而向量為G對應(yīng)的PageRank結(jié)果向量。(2) 設(shè)定，

24、即：對G中每一個節(jié)點(diǎn)n設(shè)定其初始值PR(0)(n)均為，同時設(shè)定臨時變量。(3) For k = 1 , 2 , 3 ， ，M 對G中的每一個節(jié)點(diǎn)n , 若 Outdegree ( n ) 0 ，則有：若Outdegree ( n )=0，則有：其中，a為預(yù)先設(shè)定的參數(shù)，Outdegree (Pi)為頁面Pi的出度值。 將臨時變量賦值給：(k)= 臨時變量賦初值：(4) 當(dāng)結(jié)果向量未收斂時，返回(3)繼續(xù)循環(huán)；當(dāng)收斂時，算法結(jié)束，輸出所計算出的G中每一個節(jié)點(diǎn)n的PR(n）的結(jié)果。PageRank（標(biāo)準(zhǔn)）算法的問題與改進(jìn) l 算法效率低 每次遍歷節(jié)點(diǎn)n時，如果n的出度為0，需要對每一個鏈接圖內(nèi)的

25、節(jié)點(diǎn)進(jìn)行操作。 相當(dāng)于為“死胡同”網(wǎng)頁和G中的所有網(wǎng)頁之間添加了一條虛擬的出鏈接 l 改進(jìn)鄰接矩陣 原鄰接矩陣設(shè)鏈接結(jié)構(gòu)圖G的節(jié)點(diǎn)規(guī)模為n，則鄰接矩陣M是一個n*n的矩陣，元素 mi,j取值滿足：改進(jìn)鄰接矩陣設(shè)鏈接結(jié)構(gòu)圖G的節(jié)點(diǎn)規(guī)模為n，改進(jìn)鄰接矩陣A是一個n*n的矩陣，元素ai,j取值滿足：改進(jìn)鄰接矩陣的元素取值l 如果G中存在邊（i，j），則ai,j的取值是1除以節(jié)點(diǎn)i對應(yīng)的出度；l 如果節(jié)點(diǎn)i對應(yīng)的出度為0，則第i行對應(yīng)的所有元素取值為1 / n； 為什么1 / n？l 其他情況下，ai,j的元素取值為0。如設(shè)I=（1，1，1，1)，則迭代過程可以表示為：問題：l 實(shí)際中，n的數(shù)值巨大，A往往是稀疏矩陣；l 用適用于稀疏矩陣運(yùn)算的加速算法來改善；PageRank（加速）算法輸人：萬維網(wǎng)鏈接結(jié)構(gòu)圖G（節(jié)點(diǎn)規(guī)模為N）的鏈接關(guān)系特征文件D，參數(shù)a，迭代次數(shù)M ; D的結(jié)構(gòu)： 只記錄改進(jìn)鄰接矩陣中的非零元素