第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法要點(diǎn)_第1頁
第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法要點(diǎn)_第2頁
第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法要點(diǎn)_第3頁
第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法要點(diǎn)_第4頁
第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法要點(diǎn)_第5頁
已閱讀5頁,還剩27頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第8章鏈接結(jié)構(gòu)分析子系統(tǒng)設(shè)計(jì)及核心算法本章內(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)頁的“入 鏈接” 0節(jié)點(diǎn)A-H表示網(wǎng)頁;鏈接關(guān)系用有向邊來表示;網(wǎng)頁A、B、C之間的雙向邊,表示三個(gè)網(wǎng)頁之間相互鏈接;網(wǎng)頁F與G各自有一個(gè)指向自身的有向邊。鏈接結(jié)構(gòu)關(guān)系圖的鄰接矩陣描述鄰接矩陣是用來描述圖中節(jié)點(diǎn)鄰接關(guān)系的一種方式,設(shè)n為鏈接結(jié)構(gòu)圖Graph的節(jié)點(diǎn)規(guī)

2、模,值滿足:則鄰接矩陣M是一個(gè)n*n的矩陣,其中某個(gè)兀素mi,j的取fl 3 GJ) 6 Graph0 otherwise3#圖8.1所示鏈接結(jié)構(gòu)圖,其鄰接矩陣如下:-o1110101-1010000011010010M =00001000000000100000001000000001_00000000.萬維網(wǎng)鏈接圖GWeb (V, E)Vn,節(jié)點(diǎn)數(shù) |V| = n ;V :節(jié)點(diǎn)集合,V = V 1 , V2 , V3 ,E :邊集合,E = ei , e? , e3 ,em,邊數(shù) |E|=m將萬維網(wǎng)的整個(gè)鏈接結(jié)構(gòu)圖作為對(duì)象來研究不僅對(duì)理解萬維網(wǎng)的各種屬性有直接的意義,同時(shí)還對(duì)搜索引擎領(lǐng)域的

3、相關(guān)算法研究也有著重要的幫助。 很多實(shí)驗(yàn)和觀察促進(jìn)了萬維網(wǎng)鏈接圖結(jié)構(gòu)的研究。針對(duì)圖 GWeb ( V , E ),研究;V、E 的規(guī)模;拓?fù)浣Y(jié)構(gòu); 節(jié)點(diǎn)入度、出度分布。圖 G ( V , E )的某節(jié)點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為該節(jié)點(diǎn)的“度” 。對(duì)于圖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)計(jì)(1) 圖中的節(jié)點(diǎn)存在形式復(fù)雜;非自由訪問的網(wǎng)頁(網(wǎng)頁對(duì)用戶訪問加以限制, 如采取登錄策略等) ; 自由訪問的網(wǎng)頁;傳統(tǒng)形式

4、的靜態(tài)頁面; 隨用戶查詢需求在服務(wù)器端實(shí)時(shí)生成的動(dòng)態(tài)頁面; 用 Ajax 技術(shù)生成的 URL 相同但內(nèi)容千差萬別的頁面;(2) 超鏈接的界定,存在諸多困難; “博客日歷”,每個(gè)日期都是一個(gè)超鏈接。服務(wù)器端自動(dòng)生成的超鏈接 VS 網(wǎng)頁作者手工編輯添加的鏈接。GWeb ( V , E)的節(jié)點(diǎn)集合規(guī)模 通過域名注冊(cè)服務(wù)商可統(tǒng)計(jì)網(wǎng)站、域名數(shù)量且較為準(zhǔn)確; 統(tǒng)計(jì)網(wǎng)站涉及的網(wǎng)頁數(shù)目就會(huì)面臨上面提到的問題; 研究中通常用搜索引擎的索引規(guī)模來估算萬維網(wǎng)鏈接圖的節(jié)點(diǎn)規(guī)模; 沒被任何一個(gè)搜索引擎收錄的網(wǎng)頁,被用戶訪問到的可能性微乎其微; 2008年 7月,谷歌索引量 1萬億網(wǎng)頁,一定程度上反映了 GWeb (V,

5、 E) 節(jié)點(diǎn)集合的規(guī)模。GWeb ( V , E)的邊集合規(guī)模 估計(jì)邊集合規(guī)模更困難; 超鏈接的添加不需要登記、備案,各大搜索引擎也很少公布統(tǒng)計(jì)數(shù)據(jù); 只能通過實(shí)驗(yàn)性萬維網(wǎng)語料庫的相關(guān)數(shù)據(jù)對(duì) GWeb (V , E)的邊集合規(guī) 模有一個(gè)概括性的認(rèn)識(shí);AltaVista 語料庫,鏈接關(guān)系圖包含 2.03 億個(gè)網(wǎng)頁、 14.66 億條鏈接。Clueweb09 語料庫,鏈接關(guān)系圖包含的節(jié)點(diǎn)數(shù)為 1040 809705個(gè),對(duì)應(yīng) 的出鏈接數(shù)為 7944351835個(gè)。sogouT語料庫,鏈接關(guān)系圖包含1.39億個(gè)網(wǎng)頁、33.4億條鏈接。從這些語料庫, 可以估計(jì), 邊集合的規(guī)模要大于節(jié)點(diǎn)集合的規(guī)模, 約為

6、節(jié)點(diǎn) 集合規(guī)模的幾到幾十倍。58.1.2 萬維網(wǎng)鏈接圖的連通情況定義:導(dǎo)出子圖給定G=(V, E),如果存在另外一個(gè)圖 &=(/©),滿足V包含于V, E,包含 于E,則稱G,是G的一個(gè)子圖。特別地,如果 V/包含于V,且E,包含了在節(jié)點(diǎn) 子集V/之間的所有邊,則稱G,是G的導(dǎo)出子圖。定義:強(qiáng)連通子圖給定一個(gè)有向圖, 該有向圖的一個(gè)強(qiáng)連通子圖是指由一部分節(jié)點(diǎn)組成的一個(gè) 導(dǎo)出子圖,對(duì)于該子圖中其中的任意兩個(gè)節(jié)點(diǎn)u和V,都存在一條路徑使得從u可以訪問到 v。性質(zhì):1、一個(gè)有向圖中可有多個(gè)強(qiáng)連通子圖。2、強(qiáng)連通子圖之間不存在公有節(jié)點(diǎn);否則可以合二為一。對(duì)萬維網(wǎng)連接圖,每個(gè)強(qiáng)連通子圖

7、都代表著構(gòu)成該子圖的節(jié)點(diǎn)是相互連通 的,通過超鏈接通過一個(gè)網(wǎng)頁可訪問另一個(gè)。定義:弱連通子圖給定一個(gè)有向圖, 該有向圖的一個(gè)弱連通子圖是指由一部分節(jié)點(diǎn)組成的一個(gè) 導(dǎo)出子圖,對(duì)于該子圖中其中的任意兩個(gè)節(jié)點(diǎn) u和V,都存在一條無向路徑使得 從 u 可以訪問到 V。對(duì)于萬維網(wǎng)鏈接圖, 重點(diǎn)考察其包含的強(qiáng)、 弱連通子圖的規(guī)模分布情況, 借 此了解整個(gè)鏈接圖的拓?fù)浣Y(jié)構(gòu)和連通情況。2000 年, Broder 的研究成果,萬維網(wǎng)鏈接結(jié)構(gòu)圖的強(qiáng)、弱連通子圖的規(guī)模6分布情況如下圖所示300 00010 000SCC distnburion00000oWCC distributionle+07le+06100

8、00010 0001O0G10Q10IComponent distribution *Power lawxponeTi; 2.541 10 100 100000 size of componentu.7#g 8.2萬錐網(wǎng)鏈接圖中強(qiáng)、弱連通子圖的規(guī)模分布情況圖中,橫軸為連通子圖規(guī)模,縱軸為連通子圖數(shù)量;橫軸、縱軸使用對(duì)數(shù)坐標(biāo)軸??梢钥闯鰪?qiáng)連通子圖、弱連通子圖的規(guī)模分布規(guī)律基本相同;設(shè)連通子圖規(guī)模為Size,具有規(guī)模Size的連通子圖的數(shù)目Number近似滿足;)og(Number) =* 2+ 54 log(Size) + C指數(shù)形式表示為:Number = Cz Size-'-11幾點(diǎn)

9、結(jié)論:規(guī)模大的連通子圖數(shù)目遠(yuǎn)小于規(guī)模小的連通子圖數(shù)目。規(guī)模最大的連通子圖所覆蓋的網(wǎng)絡(luò)資源數(shù)量,占網(wǎng)絡(luò)資源總量中相當(dāng)比例。基于鏈接結(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)系, 可以對(duì)整個(gè) 網(wǎng)絡(luò)頁面的鏈接結(jié)構(gòu)關(guān)系有一個(gè)清晰的認(rèn)識(shí)。根據(jù)Broder的研究結(jié)論繪制的萬維網(wǎng)鏈接結(jié)構(gòu)示意圖如下圖所示。Others 29.9%圖萬維網(wǎng)鏈接結(jié)構(gòu)圖Core部份規(guī)模最大的強(qiáng)連接子圖;IN部分

10、所有鏈接到Core中網(wǎng)頁,且同時(shí)不被Core中的網(wǎng)頁所鏈接的網(wǎng)頁集合;OUT部分所有被Core中的網(wǎng)頁所鏈接,且同時(shí)不鏈接到 Core中網(wǎng)頁的網(wǎng)頁集合;Others部分剩余的網(wǎng)頁集合。萬維網(wǎng)鏈接和連通結(jié)構(gòu)概貌從IN中任何網(wǎng)頁,都可以鏈接到Core中網(wǎng)頁,進(jìn)而可訪問OUT中任何網(wǎng)頁。IN、Core、OUT之外網(wǎng)頁,一部份與IN、OUT有鏈接關(guān)系,另一部分與IN、Core、OUT不相連的孤立點(diǎn)或點(diǎn)集合,規(guī)模約為所分析網(wǎng)頁總數(shù)的8.2%。萬維網(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)鏈接,以及鏈接到

11、其他節(jié)點(diǎn)的情況。萬維網(wǎng)鏈接圖GWeb (V,E)的入度、出度分布符合幕律;入度為In degree的網(wǎng)頁數(shù)目 N ( In degree )近似滿足:Indegree) = C Indegree-0出度為Outdegree的網(wǎng)頁數(shù)目 N ( Outdegree )近似滿足:N(Outdegree) = C Outdcgree'其中a、B均為值大于零的參數(shù),而 C與&為常數(shù)Broder的實(shí)驗(yàn)結(jié)果如下圖所示。le+10In-degree(May 99,Oct 99)disir.Out-dcgrce(May 99,Oct 99)dstr.MUepKltJ:*qEnllle+09 -!

12、t+O8 :i-e+07 -le-06 - 00 000 -100001000 -ln4iegree(May 99)卩 ower law,exponCTiL 2.09k-defiz«e<Oct 99Power law,exponent 2.09器啓 d jo -JJJLunLlle+JOle+09le+O8le+07le+06 lOOOOO10 00000 J1001001 10 100 100 000Jl(jOut-degncefMay 99 t Power hwxpnnenl 2.72 Out-degree(Oct 99)30 100 1000 out-degree(a)圖

13、吐斗 萬維網(wǎng)鏈接圖中入度、出度的分布惜況8.2超鏈接結(jié)構(gòu)分析的基礎(chǔ)超鏈接:兩個(gè)網(wǎng)頁或網(wǎng)頁的兩個(gè)不同部分之間的一種指向關(guān)系,源網(wǎng)頁是指包含超鏈接的網(wǎng)頁,目標(biāo)網(wǎng)頁是超鏈接所指向的網(wǎng)頁。超鏈接HTML格式:< A HREF- "http: /www, tsinghus. edu + cW清華大學(xué)主頁 < /A>超鏈接的特性如果存在超鏈接L從頁面Psource指向頁面Pdestiny,則Psource與Pdestiny滿足:特性1 :內(nèi)容推薦特性頁面Psource的作者推薦頁面Pdestiny的內(nèi)容,且利用L的鏈接文本內(nèi)容對(duì)Pdest iny進(jìn)行描述。特性2 :主題相關(guān)特性

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

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

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

17、較強(qiáng)、對(duì)學(xué)科發(fā)展能起到較大的推進(jìn)作用。鏈接權(quán)威度:對(duì)某個(gè)特定領(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算法所要解決的問題對(duì)用戶提交的大多數(shù)查詢,搜索引擎都會(huì)返回大量的相關(guān)查詢結(jié)果; 大多數(shù)用戶傾向查找出結(jié)果集合中對(duì)獲取信息最有價(jià)值的那一部分網(wǎng)頁;算法的輸入:搜索引擎返回的與查詢主題在內(nèi)容上相關(guān)的結(jié)果集合;算法的輸出:對(duì)結(jié)果集合中網(wǎng)頁的內(nèi)容權(quán)威度、鏈接權(quán)威度的評(píng)價(jià)。HITS算法實(shí)施

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

19、用鏈接的影響,刪除站內(nèi)鏈接(即超鏈接的鏈源和鏈宿都在同 一個(gè)主機(jī)上)。在構(gòu)造完主題子圖之后,可以通過迭代算法來計(jì)算出網(wǎng)頁的鏈接權(quán)威度、內(nèi) 容權(quán)威度。網(wǎng)頁內(nèi)容權(quán)威度、網(wǎng)頁鏈接權(quán)威度間為相互加強(qiáng)的關(guān)系:具有較高網(wǎng)頁鏈接權(quán)威度的網(wǎng)頁應(yīng)該指向較多的網(wǎng)頁內(nèi)容權(quán)威度高的網(wǎng)頁; 高網(wǎng)頁內(nèi)容權(quán)威度的網(wǎng)頁應(yīng)該被多個(gè)高網(wǎng)頁鏈接權(quán)威度的網(wǎng)頁所指向。對(duì)網(wǎng)頁i,令ai:內(nèi)容權(quán)威度;hi:鏈接權(quán)威度;B(i):網(wǎng)頁i的入鏈接集;F(i):網(wǎng)頁1的出鏈接集;則有:色=丫 bJh=為勺例:頁面1的內(nèi)容權(quán)威度、鏈接權(quán)威度14 1 = /心十心+力I 兒=心+化+ ©I操作:計(jì)算內(nèi)容權(quán)威度;O操作:計(jì)算鏈接權(quán)威度;q:

20、 p對(duì)權(quán)值進(jìn)行規(guī)范化規(guī)范化內(nèi)容權(quán)威度的公式:規(guī)范化鏈接權(quán)威度的公式:115迭代地進(jìn)行I操作、O操作,直到最近兩輪迭代的規(guī)范化內(nèi)容權(quán)威度、 鏈接權(quán)威 度的差異很小,則認(rèn)為已收斂。輸入A). G是鏈接頁面的集合,k是一個(gè)口然數(shù)令遼我示矢量(1. U H 1)6RHWhili | a(_| | | h力$_ | O,do 對(duì)(如一“ h)應(yīng)用I操作級(jí)獲得新的“; 對(duì)(;申兒J應(yīng)用()操作號(hào)獲得新的h 標(biāo)準(zhǔn)化auihority值申獲得a 標(biāo)準(zhǔn)化hub值/二得到九End返回(仆加)HITS算法處理的對(duì)象個(gè)數(shù)相對(duì)較少,一般也就在幾萬個(gè)以內(nèi),計(jì)算速度相 對(duì)較快。因?yàn)樗敲嫦虿樵兊乃惴?,?duì)用戶響應(yīng)的時(shí)間要快,

21、所以一般情況下只 是求出次優(yōu)解就可以了。在Kleinberg的實(shí)驗(yàn)中,循環(huán)迭代20次,就可使前C個(gè)(C取510之間) 網(wǎng)頁排序足夠地穩(wěn)定了。16例:針對(duì)結(jié)構(gòu)圖,計(jì)算每個(gè)網(wǎng)頁的鏈接權(quán)威度、內(nèi)容權(quán)威度解:根據(jù)上圖構(gòu)造主題子圖V=A,B,C,鄰接矩陣E= <A,A> ,A,B> , <A,C> , <B,A> , <B,C> , <C,B> ,表示為1rE =10101o由此得到英轉(zhuǎn)宣矩陣為110_Er =101_110.(口,嗎,=E' (h 呂 * h R、h 廣),(Aa* hfi» h(')口h* 口

22、廠因此有,%=ftA + 嘰.ati =+ hf = flA + 嘰h=ClA + WB + etc *=a a十 » /:( = 3初始化吋.令5 = %=ac=hA = hli=h=1.第一次迭代il算心值: 2 Up = 2 ? de 2計(jì)算&值:占丸=6申方舟=4 .力g = 2 為簡便計(jì)算,釆用最大值的規(guī)范化方法。規(guī)范化S5 = 1,月=1* ac = 1 規(guī)范化b_ _ 2 _ 1繼續(xù)迭代曲至收斂。最后:5 = 1,g = O*732, ac 1hA = l9 論=5 732. Ac =0.26818HITS (Hyperlink-1nduced Topic Se

23、arch)算法(1) 選取網(wǎng)絡(luò)信息檢索系統(tǒng)的結(jié)果集合R將尺賦所指向的網(wǎng)頁和指向的網(wǎng)頁枸成的鏈接結(jié)構(gòu)圖稱為G。對(duì)于G中的每一個(gè)節(jié)點(diǎn)心設(shè)和分別是其鏈接權(quán)威度和內(nèi)容權(quán)威度,向量H和才分別 為G的鏈接權(quán)威度和內(nèi)容權(quán)威度結(jié)果向凰°(2) 設(shè)定即:對(duì)G中每一個(gè)節(jié)點(diǎn)心設(shè)定其初始值(總)和A的均 為1.(3) For i = 對(duì)G中的每一個(gè)節(jié)點(diǎn)捍,A&)= 另稱為I操作)Hu. so'i 對(duì)G中的每一個(gè)節(jié)點(diǎn)心H5)=杓 (稱為0操作) 將Hw(n)和AUWG)作規(guī)范化處理,使尸=1,工(H|尸=K4)當(dāng)結(jié)果向量目和/未收斂時(shí),返回(3) H和A收斂時(shí),輸出算法所計(jì)算出的G中每一個(gè) 節(jié)

24、點(diǎn)貳的和的結(jié)果°8.4 PageRank算法的基本思路及實(shí)現(xiàn)PageRank 算法:拉里佩奇(Larry Page)等人提出;根據(jù)WEB超鏈接關(guān)系對(duì)網(wǎng)頁重要程度進(jìn)行估計(jì);2008年1月申請(qǐng)美國專利,同年在論文“ The An atomy of a Large-Scale Hyper textual Web Search Engine 中公開;將從頁面A到頁面B的超鏈接作為A向B的一次投票,但不是簡單地統(tǒng)計(jì)票 數(shù)來衡量質(zhì)量高低,還要考慮投票者因素,較“重要”網(wǎng)頁的投票會(huì)更受重視。PageRa nk基于“從許多優(yōu)質(zhì)網(wǎng)頁鏈接過來的網(wǎng)頁,必定還是優(yōu)質(zhì)網(wǎng)頁”的 思想判定網(wǎng)頁的重要性。PageR

25、ank 衡量“網(wǎng)頁質(zhì)量”的方式“質(zhì)量”定義有很強(qiáng)的主觀性;從時(shí)效性、頁面結(jié)構(gòu)組織、獨(dú)特性等角度定義;HITS算法的“鏈接權(quán)威度”與“內(nèi)容權(quán)威度”;PageRa nk用戶隨機(jī)瀏覽互聯(lián)網(wǎng)時(shí)訪問到某個(gè)頁面的概率;隨機(jī)瀏覽模型模型描述用戶對(duì)網(wǎng)頁的訪問行為;隨機(jī)體現(xiàn)在:瀏覽起始點(diǎn)選擇的隨機(jī)性、頁內(nèi)超鏈接選擇的隨機(jī)性;所用瀏覽器:無地址欄,無后退、前進(jìn)按鈕;不能輸入 URL訪問網(wǎng)頁,且只能向前瀏 覽不能回退;提供“隨便逛逛”功能,點(diǎn)擊“隨便逛逛”按鈕,挑選一個(gè)隨機(jī)的起點(diǎn), 開始瀏覽;可從網(wǎng)頁內(nèi)所含超鏈接中隨機(jī)選擇一個(gè)頁面繼續(xù)進(jìn)行瀏覽;沿著超鏈接前進(jìn)了一定數(shù)目的網(wǎng)頁后, 對(duì)頁面內(nèi)容不感興,可使用“隨便逛逛”

26、 跳轉(zhuǎn)到另一個(gè)網(wǎng)頁上進(jìn)行瀏覽,如此反復(fù)。在瀏覽過程中,用戶訪問到某個(gè)頁面的概率就稱為該頁面的PageRank。用戶離開肖肅匸世頁面PageRank計(jì)算:網(wǎng)頁被用戶訪問到的可能性有兩種。1、使用“隨便逛逛”跳轉(zhuǎn)到頁面 A假設(shè)“隨便逛逛”以隨機(jī)方式推薦網(wǎng)頁,互聯(lián)網(wǎng)上網(wǎng)頁總數(shù)為N,則用戶使用“隨便逛逛”訪問到網(wǎng)頁 A的概率為1/N。2、瀏覽過程中通過其他網(wǎng)頁上超鏈接訪問到頁面A假設(shè)鏈接到A的k個(gè)網(wǎng)頁為Pi, P2 , P3,,Pk。則用戶通過Pi訪問A 的概率為:PageRank(P i )*P( P i =>A)PageRank(P J:用戶訪問到P i頁面的概率,P( Pi =>A)

27、:用戶訪問P i頁面時(shí),點(diǎn)擊鏈接到A頁面的超鏈接的概率 假設(shè)用戶瀏覽Pi時(shí)點(diǎn)擊頁面上各超鏈接概率相等;21#P(Pi1Outdegree(R)#用戶通過Pi,P2,P3,,Pk訪問到A的概率為:#J PageRank(P)芋 PageRa nk(P)P二 AOutdegree(R)#假設(shè)。不存在不含超鏈接的網(wǎng)頁,用戶主動(dòng)使用“隨便逛逛”功能概率為a, 則用戶訪問到頁面A的概率為:PageRank(A)二 a* i Outdegree(R)(1 -a)* ' PageRank(Pi)N冷 Outdegree(R)1a*丄:用戶使用“隨便逛逛”功能訪問到頁面 A的概率;N(1-a)* a

28、PageRank:Pi):用戶使用超鏈接訪問到頁面A的概率; 冷 Outdegree(R)可以看到,對(duì)給定的參數(shù) a,頁面A的PageRank值由鏈接到它的各個(gè)頁面 的PageRank值決定的。如果考慮全萬維網(wǎng)頁面 PageRank的計(jì)算,就會(huì)發(fā)現(xiàn)是 一個(gè)迭代計(jì)算過程。PageRank (簡化)算法取萬維網(wǎng)鏈接結(jié)構(gòu)圖G , G的規(guī)模為N,即G中包括N個(gè)節(jié)點(diǎn)對(duì)于G中的每一個(gè)節(jié)點(diǎn)n,設(shè)PR(n)是其PageRank值,而向量PR為GPR =(丄,丄,丄N N N對(duì)應(yīng)的PageRank結(jié)果向量。設(shè)定,丄即:對(duì)G中每一個(gè)節(jié)點(diǎn)n,設(shè)定其初始值PR(O)(n)均為N For k= 1,2,3,,TN對(duì)G中

29、的每一個(gè)節(jié)點(diǎn)n ,(k)* 1“ 、八PR(kJl)(P)(n) = a *(1 - a)-PRNPnOutdegree(P)其中,a為預(yù)先設(shè)定的參數(shù),Outdegree (P)為頁面Pi的出度值。(4) 當(dāng)結(jié)果向量PR未收斂時(shí),返回(3)繼續(xù)循環(huán);當(dāng)PR收斂時(shí),算法結(jié)束, 輸出所計(jì)算出的G中每一個(gè)節(jié)點(diǎn)n的PR(n)的結(jié)果。例:如圖所示的鏈接結(jié)構(gòu)圖中,各個(gè)網(wǎng)頁都具有超鏈接,A頁面鏈向頁面B與C,B與C分別鏈向D頁面,而D頁面鏈回A頁面。我們可以依照上述PageRank簡化算法計(jì)算圖8. 9的PageRank數(shù)值如下:23#24初值:庶=(*,+,+,*),設(shè) a 為 0.2第一次迭代;PR(A

30、) = 0 2 ± + (1 0. 2八(PR(D)/Outdegree(D) 4=0* 05 + 0, 8 0, 254PR(1)(B) = 0. 2 丄 + (I 0. 2) - (PRt0> (A)/Outdegree(A) 41 1 _=0.05 + 0.8 j * y = 0. 15PR(C) = 0,2 丄 + (1 0. 2八(PR(A)/Outdegree<A)> 4=0,05+0.8 # * 二 0.15PR(D) = 0. 2 丄 + (1 0. 2八(PR(0>(B)/Outdegree(B) 4+ PRf0)(C)/Outdegree(

31、C) = 0. 05 + 0. 8 (扌 + 工=0. 4525第二次迭代:PR(A= 0. 2 ± + (1 0. 2八(PRtn(D)/Outdegree(D) 4=0.05 +CM 6 45 = 0*41PR(B= CL 2 3 + (1 0. 2) * (PR(A)/Outdegree(A) 41 10.05 + 0. 8 4 4 = 0. 1542FR(C) = 0* 2 丄 + Q 0. 2八(PR(A)/Outdegree(A)4=0.05 + 0, 8 4丄=0* 154 LFRO (D) = 0展* 丄 +1 CL 2八(PRC0) (B)/Outdegree(B)

32、4+ PR<0>(C>/Outdegree(C) = 0.05 + 0, 8 - (0.15 + 0.15)=0. 29隨后迭代的結(jié)果表亂1 圖乩9對(duì)應(yīng)的PageRank計(jì)算結(jié)杲PR(A)PR(B)PR(C)PR(D)Y FR第1次迭代0.25000.2500Q* 25000.25001. 0000第2次迭代0.25000. 15000. 15000,4500LOOOO第3次迭代0+41000.15000. 15000.29001. 0000第4決迭代0,28200.21400.21400.2900l.OODQ第5次迭代0, 28200, K280.16280,39241.0

33、000第10次送杜0.30680,1861 10.18S10.3210L 0000第湖次迭代0.31440.17580.17580t 33411. 0000第昭次迭代0,31580.17620r17620,33191.0000第100次迭松0.31560.17620, 17620.3320L 0000由上表可見:進(jìn)行到第30次迭代,算法結(jié)果已經(jīng)基本收斂;第30次迭代的結(jié)果與第100次迭代的結(jié)果差別小于千分之一;采用算法迭代30次左右的結(jié)果即可以滿足需求。迭代中頁面PageRank變化,但各頁面 PageRank的和等于1 ;PageRank (簡化)算法的問題有些網(wǎng)頁沒有出鏈接TXT, DOC

34、, JPG,隨機(jī)瀏覽進(jìn)入死胡同只能使用“隨便逛逛”相當(dāng)于為 死胡同”網(wǎng)頁和G中的所有網(wǎng)頁之間添加了一條虛擬的出鏈接死胡同”網(wǎng)頁的PageRank借助“隨便逛逛”平均分配給 G中的所有網(wǎng)頁P(yáng)ageRank (標(biāo)準(zhǔn))算法取萬維網(wǎng)鏈接結(jié)構(gòu)圖G , G的規(guī)模為N,即G中包括N個(gè)節(jié)點(diǎn)對(duì)于G中的每一個(gè)節(jié)點(diǎn)n,設(shè)PR(n)是其PageRank值,而向量PR為G對(duì)應(yīng) 的PageRank結(jié)果向量。 設(shè)定PR =(,,),即:對(duì)G中每一個(gè)節(jié)點(diǎn)n設(shè)定其初始值PR(n)N N N N均為-,同時(shí)設(shè)定臨時(shí)變量I =(旦,旦,旦,,旦NN N N N For k = 1 , 2,3,M對(duì)G中的每一個(gè)節(jié)點(diǎn)n ,若Outde

35、gree ( n ) > 0,則有:Pr(t (n)-R,ifnP,I(P) = l(P) (Va)*-Outdegree(n)若 Outdegree ( n )=0,則有:PR(k)(門) 育 G,I(P)二 l(P) (1 - a)*-N其中,a為預(yù)先設(shè)定的參數(shù),Outdegree (P)為頁面Pi的出度值。 將臨時(shí)變量賦值給PR : PR(k)=l臨時(shí)變量賦初值:(話話話戶 當(dāng)結(jié)果向量PR未收斂時(shí),返回 繼續(xù)循環(huán);當(dāng)PR收斂時(shí),算法結(jié)束,輸出 所計(jì)算出的G中每一個(gè)節(jié)點(diǎn)n的PR(n)的結(jié)果。PageRank (標(biāo)準(zhǔn))算法的問題與改進(jìn)算法效率低每次遍歷節(jié)點(diǎn)n時(shí),如果n的出度為0,需要對(duì)

36、每一個(gè)鏈接圖內(nèi)的節(jié)點(diǎn)進(jìn) 行操作。相當(dāng)于為 死胡同”網(wǎng)頁和G中的所有網(wǎng)頁之間添加了一條虛擬的出鏈接 改進(jìn)鄰接矩陣原鄰接矩陣設(shè)鏈接結(jié)構(gòu)圖G的節(jié)點(diǎn)規(guī)模為n,則鄰接矩陣M是一個(gè)n*n的矩陣,元素mq取值滿足:3dfj)e gotherwise28#改進(jìn)鄰接矩陣設(shè)鏈接結(jié)構(gòu)圖G的節(jié)點(diǎn)規(guī)模為n,改進(jìn)鄰接矩陣A是一個(gè)n*n的矩陣,元 素ai,j取值滿足:10e GS 4" = 0iotherwise改進(jìn)鄰接矩陣的元素取值如果G中存在邊(i, j),則a,j的取值是1除以節(jié)點(diǎn)i對(duì)應(yīng)的出度;如果節(jié)點(diǎn)i對(duì)應(yīng)的出度為0,則第i行對(duì)應(yīng)的所有元素取值為1 / n; 為什么1 / n?其他情況下,ai,j的元素取值為0。#如設(shè)I

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論