1、第8章鏈接結構分析子系統設計及核心算法本章內容：萬維網鏈接結構圖及特性；鏈接結構分析方法的形式化基礎；鏈接結構分析Page Rank算法、HITS算法;鏈接結構分析結果在搜索結果排序中的應用。8.1萬維網鏈接結構圖萬維網的鏈接結構可用有向圖來描述，網頁是節點，超鏈接是有向邊。從源網頁指向目的網頁的超鏈接，為源網頁的“出鏈接”，為目的網頁的“入 鏈接” 0節點A-H表示網頁；鏈接關系用有向邊來表示；網頁A、B、C之間的雙向邊，表示三個網頁之間相互鏈接;網頁F與G各自有一個指向自身的有向邊。鏈接結構關系圖的鄰接矩陣描述鄰接矩陣是用來描述圖中節點鄰接關系的一種方式，設n為鏈接結構圖Graph的節點規

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

3、相關算法研究也有著重要的幫助。 很多實驗和觀察促進了萬維網鏈接圖結構的研究。針對圖 GWeb ( V , E )，研究；V、E 的規模；拓撲結構； 節點入度、出度分布。圖 G ( V , E )的某節點所關聯的邊數稱為該節點的“度” 。對于圖GWeb ( V , E)而言，某節點的入度就是指以該節點作為目的網頁的超鏈 接數(該節點入鏈接數) ；某節點的出度則是指以該節點為源網頁的超鏈接數(該節點出鏈接數) 。8.1.1 萬維網鏈接圖的規模GWeb (V, E)規模難以統計(1) 圖中的節點存在形式復雜；非自由訪問的網頁(網頁對用戶訪問加以限制， 如采取登錄策略等) ； 自由訪問的網頁；傳統形式

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

5、 E) 節點集合的規模。GWeb ( V , E)的邊集合規模 估計邊集合規模更困難； 超鏈接的添加不需要登記、備案，各大搜索引擎也很少公布統計數據； 只能通過實驗性萬維網語料庫的相關數據對 GWeb (V , E)的邊集合規 模有一個概括性的認識；AltaVista 語料庫，鏈接關系圖包含 2.03 億個網頁、 14.66 億條鏈接。Clueweb09 語料庫，鏈接關系圖包含的節點數為 1040 809705個，對應 的出鏈接數為 7944351835個。sogouT語料庫，鏈接關系圖包含1.39億個網頁、33.4億條鏈接。從這些語料庫， 可以估計， 邊集合的規模要大于節點集合的規模， 約為

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

7、都代表著構成該子圖的節點是相互連通 的，通過超鏈接通過一個網頁可訪問另一個。定義：弱連通子圖給定一個有向圖， 該有向圖的一個弱連通子圖是指由一部分節點組成的一個 導出子圖，對于該子圖中其中的任意兩個節點 u和V，都存在一條無向路徑使得 從 u 可以訪問到 V。對于萬維網鏈接圖， 重點考察其包含的強、 弱連通子圖的規模分布情況， 借 此了解整個鏈接圖的拓撲結構和連通情況。2000 年， Broder 的研究成果，萬維網鏈接結構圖的強、弱連通子圖的規模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萬錐網鏈接圖中強、弱連通子圖的規模分布情況圖中，橫軸為連通子圖規模，縱軸為連通子圖數量；橫軸、縱軸使用對數坐標軸。可以看出強連通子圖、弱連通子圖的規模分布規律基本相同；設連通子圖規模為Size，具有規模Size的連通子圖的數目Number近似滿足；)og(Number) =* 2+ 54 log(Size) + C指數形式表示為：Number = Cz Size-'-11幾點

9、結論：規模大的連通子圖數目遠小于規模小的連通子圖數目。規模最大的連通子圖所覆蓋的網絡資源數量，占網絡資源總量中相當比例。基于鏈接結構抓取，很難抓取到網絡環境中所有數據， 但通過抓取規模較大的 連通子圖可獲取最主要部分的數據。規模最大的強連通子圖，其節點規模達到560余萬，此連通子圖在 Broder研究的網頁集合總規模中占有近 28%的網頁。以此連通子圖為中心，考察其他網頁與此連通子圖的鏈接關系， 可以對整個 網絡頁面的鏈接結構關系有一個清晰的認識。根據Broder的研究結論繪制的萬維網鏈接結構示意圖如下圖所示。Others 29.9%圖萬維網鏈接結構圖Core部份規模最大的強連接子圖；IN部分

10、所有鏈接到Core中網頁，且同時不被Core中的網頁所鏈接的網頁集合；OUT部分所有被Core中的網頁所鏈接，且同時不鏈接到 Core中網頁的網頁集合；Others部分剩余的網頁集合。萬維網鏈接和連通結構概貌從IN中任何網頁，都可以鏈接到Core中網頁，進而可訪問OUT中任何網頁。IN、Core、OUT之外網頁，一部份與IN、OUT有鏈接關系，另一部分與IN、Core、OUT不相連的孤立點或點集合，規模約為所分析網頁總數的8.2%。萬維網鏈接結構以Core為核心，構成了“領結”形式的結構。8.1.3萬維網鏈接圖的入度和出度分布萬維網鏈接圖的入度、出度分別反映了某節點被其他節點鏈接，以及鏈接到

11、其他節點的情況。萬維網鏈接圖GWeb (V,E)的入度、出度分布符合幕律；入度為In degree的網頁數目 N ( In degree )近似滿足：Indegree) = C Indegree-0出度為Outdegree的網頁數目 N ( Outdegree )近似滿足:N(Outdegree) = C Outdcgree'其中a、B均為值大于零的參數，而 C與&為常數Broder的實驗結果如下圖所示。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、吐斗 萬維網鏈接圖中入度、出度的分布惜況8.2超鏈接結構分析的基礎超鏈接：兩個網頁或網頁的兩個不同部分之間的一種指向關系，源網頁是指包含超鏈接的網頁，目標網頁是超鏈接所指向的網頁。超鏈接HTML格式：< A HREF- "http: /www, tsinghus. edu + cW清華大學主頁 < /A>超鏈接的特性如果存在超鏈接L從頁面Psource指向頁面Pdestiny,則Psource與Pdestiny滿足：特性1 :內容推薦特性頁面Psource的作者推薦頁面Pdestiny的內容，且利用L的鏈接文本內容對Pdest iny進行描述。特性2 :主題相關特性

14、被超鏈接連接的兩個頁面Psource與 Pdestiny的頁面內容涉及類似的主題。特性 1 說明：入鏈接個數是頁面受其他頁面推薦程度大小的標志， 入鏈越多， 該頁面受其他 網頁作者的推薦越多，其網頁內容質量高。入鏈接個數越少， 說明該頁面不被其他網頁作者推薦， 意味著頁面內容或組織 形式不受歡迎。鏈接文本起到對網頁內容描述的作用， 由于描述來自他人， 通常被認為是對網 頁內容更加客觀的描述。這就在頁面質量與超鏈接結構圖的拓撲關系間建立了聯系， 為頁面內容質量 評價提供了一種不基于內容的方式。HITS算法、PageRank算法是依據該特性設計的。特性 2 說明與特性 1 相比，特性 2的重要程度

15、、適用性低一些；Psource Pdestiny頁面內容相關的可能性要大于隨機抽取的兩個頁面； 超鏈接表示的不僅是內容相關關系。萬維網的超鏈接關系比特性 1、特性 2 描述的復雜。導航欄鏈接 源、目標頁面的作者相同，不是內容推薦關系，而是方便用戶訪問的設置。 可以認為符合特性 2，顯然不符合特性 1。廣告鏈接 內容推薦特性、主題相關特性都無法得到保證（尤其是主題相關性）。方面變化快、時效性強，對鏈接結構分析造成了相當的困難。版權、注冊鏈接版權信息、注冊信息往往以超鏈接的形式存在，以便查閱；這類超鏈接數目大；不符合超鏈接應具有的兩個特性。相當多超鏈接不符合超鏈接算法設計中的假設各種鏈接結構分析算

16、法在真實環境中無法單獨被用于網頁質量評估 改進算法還是可以為頁面質量評估提供參考； 數據清理后的近似理想環境中，還是可以發揮作用。本章，假設萬維網結構中的超鏈接滿足以上兩個特性。8.3 HITS 算法的基本思路及實現HITS 算法：HITS是Hyperlink-lnduced Topic Search的縮寫，基于超鏈接推演的主題搜索 算法。核心思想；對網頁的“內容權威度” 、“鏈接權威度”進行評價；內容權威度 ( Authority Value )：網頁本身內容的受歡迎程度；鏈接權威度( Hub Value ) ：網頁鏈接到其他受歡迎資源的程度 例：學術論文內容權威度：內容質量比較高、 創新性

17、較強、對學科發展能起到較大的推進作用。鏈接權威度：對某個特定領域進行了較為詳盡的調研， 能夠介紹相當數目的內容質量高的其他論文和研究工作。網頁內容權威度：與網頁提供的內容信息質量有關，被其他網頁引用得越多，其內容權威度越網頁鏈接權威度：與網頁提供的超鏈接質量有關，網頁鏈向內容質量高的網頁越多，其鏈接權威度越高。HITS算法所要解決的問題對用戶提交的大多數查詢，搜索引擎都會返回大量的相關查詢結果； 大多數用戶傾向查找出結果集合中對獲取信息最有價值的那一部分網頁;算法的輸入：搜索引擎返回的與查詢主題在內容上相關的結果集合；算法的輸出：對結果集合中網頁的內容權威度、鏈接權威度的評價。HITS算法實施

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

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

20、 p對權值進行規范化規范化內容權威度的公式:規范化鏈接權威度的公式:115迭代地進行I操作、O操作，直到最近兩輪迭代的規范化內容權威度、 鏈接權威 度的差異很小，則認為已收斂。輸入A）. G是鏈接頁面的集合，k是一個口然數令遼我示矢量（1. U H 1）6RHWhili | a（_| | | h力$_ | O，do 對（如一“ h）應用I操作級獲得新的“； 對（；申兒J應用（）操作號獲得新的h 標準化auihority值申獲得a 標準化hub值/二得到九End返回（仆加）HITS算法處理的對象個數相對較少，一般也就在幾萬個以內，計算速度相 對較快。因為它是面向查詢的算法，對用戶響應的時間要快，

21、所以一般情況下只 是求出次優解就可以了。在Kleinberg的實驗中，循環迭代20次,就可使前C個（C取510之間） 網頁排序足夠地穩定了。16例：針對結構圖，計算每個網頁的鏈接權威度、內容權威度解：根據上圖構造主題子圖V=A,B,C，鄰接矩陣E= <A,A> ,A,B> , <A,C> , <B,A> , <B,C> , <C,B> ,表示為1rE =10101o由此得到英轉宣矩陣為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計算&值:占丸=6申方舟=4 .力g = 2 為簡便計算，釆用最大值的規范化方法。規范化S5 = 1，月=1* ac = 1 規范化b_ _ 2 _ 1繼續迭代曲至收斂。最后：5 = 1，g = O*732, ac 1hA = l9 論=5 732. Ac =0.26818HITS (Hyperlink-1nduced Topic Se

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

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

25、ank 衡量“網頁質量”的方式“質量”定義有很強的主觀性；從時效性、頁面結構組織、獨特性等角度定義；HITS算法的“鏈接權威度”與“內容權威度”；PageRa nk用戶隨機瀏覽互聯網時訪問到某個頁面的概率;隨機瀏覽模型模型描述用戶對網頁的訪問行為；隨機體現在：瀏覽起始點選擇的隨機性、頁內超鏈接選擇的隨機性；所用瀏覽器：無地址欄，無后退、前進按鈕；不能輸入 URL訪問網頁，且只能向前瀏 覽不能回退；提供“隨便逛逛”功能，點擊“隨便逛逛”按鈕，挑選一個隨機的起點， 開始瀏覽；可從網頁內所含超鏈接中隨機選擇一個頁面繼續進行瀏覽；沿著超鏈接前進了一定數目的網頁后， 對頁面內容不感興，可使用“隨便逛逛”

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

27、:用戶訪問P i頁面時，點擊鏈接到A頁面的超鏈接的概率 假設用戶瀏覽Pi時點擊頁面上各超鏈接概率相等；21#P(Pi1Outdegree(R)#用戶通過Pi，P2，P3,，Pk訪問到A的概率為:#J PageRank(P)芋 PageRa nk(P)P二 AOutdegree(R)#假設。不存在不含超鏈接的網頁，用戶主動使用“隨便逛逛”功能概率為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)可以看到，對給定的參數 a,頁面A的PageRank值由鏈接到它的各個頁面 的PageRank值決定的。如果考慮全萬維網頁面 PageRank的計算，就會發現是 一個迭代計算過程。PageRank (簡化)算法取萬維網鏈接結構圖G , G的規模為N，即G中包括N個節點對于G中的每一個節點n,設PR(n)是其PageRank值，而向量PR為GPR =(丄，丄，丄N N N對應的PageRank結果向量。設定,丄即：對G中每一個節點n，設定其初始值PR(O)(n)均為N For k= 1,2,3,，TN對G中

29、的每一個節點n ,(k)* 1“ 、八PR(kJl)(P)(n) = a *(1 - a)-PRNPnOutdegree(P)其中，a為預先設定的參數，Outdegree (P)為頁面Pi的出度值。(4) 當結果向量PR未收斂時，返回(3)繼續循環；當PR收斂時，算法結束, 輸出所計算出的G中每一個節點n的PR(n)的結果。例：如圖所示的鏈接結構圖中，各個網頁都具有超鏈接，A頁面鏈向頁面B與C,B與C分別鏈向D頁面，而D頁面鏈回A頁面。我們可以依照上述PageRank簡化算法計算圖8. 9的PageRank數值如下：23#24初值：庶=(*，+，+，*),設 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隨后迭代的結果表亂1 圖乩9對應的PageRank計算結杲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由上表可見：進行到第30次迭代，算法結果已經基本收斂；第30次迭代的結果與第100次迭代的結果差別小于千分之一;采用算法迭代30次左右的結果即可以滿足需求。迭代中頁面PageRank變化，但各頁面 PageRank的和等于1 ；PageRank (簡化)算法的問題有些網頁沒有出鏈接TXT, DOC

34、, JPG,隨機瀏覽進入死胡同只能使用“隨便逛逛”相當于為 死胡同”網頁和G中的所有網頁之間添加了一條虛擬的出鏈接死胡同”網頁的PageRank借助“隨便逛逛”平均分配給 G中的所有網頁PageRank (標準)算法取萬維網鏈接結構圖G , G的規模為N，即G中包括N個節點對于G中的每一個節點n,設PR(n)是其PageRank值，而向量PR為G對應 的PageRank結果向量。 設定PR =(,，)，即：對G中每一個節點n設定其初始值PR(n)N N N N均為-，同時設定臨時變量I =(旦，旦,旦,，旦NN N N N For k = 1 , 2,3，M對G中的每一個節點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為預先設定的參數，Outdegree (P)為頁面Pi的出度值。 將臨時變量賦值給PR : PR(k)=l臨時變量賦初值：(話話話戶 當結果向量PR未收斂時，返回 繼續循環；當PR收斂時，算法結束，輸出 所計算出的G中每一個節點n的PR（n）的結果。PageRank （標準）算法的問題與改進算法效率低每次遍歷節點n時，如果n的出度為0，需要對

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