第 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 章 鏈接結(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)頁的“入鏈接”。

● 節(jié)點(diǎn) A-H 表示網(wǎng)頁；

● 鏈接關(guān)系用有向邊來表示；

● 網(wǎng)頁

● 網(wǎng)頁A 、B 、C 之間的雙向邊，表示三個(gè)網(wǎng)頁之間相互鏈接； F 與G 各自有一個(gè)指向自身的有向邊。

1

鏈接結(jié)構(gòu)關(guān)系圖的鄰接矩陣描述。

鄰接矩陣是用來描述圖中節(jié)點(diǎn)鄰接關(guān)系的一種方式，設(shè)n 為鏈接結(jié)構(gòu)圖 Graph 的節(jié)點(diǎn)規(guī)模，則鄰接矩陣 M 是一個(gè)n*n的矩陣，其中某個(gè)元素 m i,j 的取值滿足：

圖 8.1 所示鏈接結(jié)構(gòu)圖，其鄰接矩陣如下：

萬維網(wǎng)鏈接圖GWeb (V, E)

V ：節(jié)點(diǎn)集合，V = { v1 , v2 , v3 ， ? ， v n ｝，節(jié)點(diǎn)數(shù)|V| = n ;

E ：邊集合， E = { e1 , e2 , e3 ， ? ，e m ｝，邊數(shù)|E|=m 。

2

將萬維網(wǎng)的整個(gè)鏈接結(jié)構(gòu)圖作為對象來研究不僅對理解萬維網(wǎng)的各種屬性有直接的意義，同時(shí)還對搜索引擎領(lǐng)域的相關(guān)算法研究也有著重要的幫助。

很多實(shí)驗(yàn)和觀察促進(jìn)了萬維網(wǎng)鏈接圖結(jié)構(gòu)的研究。

針對圖 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)的“度”。

對于圖 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)頁對用戶訪問加以限制，如采取登錄策略等）； 自由訪問的網(wǎng)頁；

傳統(tǒng)形式的靜態(tài)頁面； 隨用戶查詢需求在服務(wù)器端實(shí)時(shí)生成的動態(tài)頁面； 用 Ajax 技術(shù)生成的 URL 相同但內(nèi)容千差萬別的頁面；

(2) 超鏈接的界定，存在諸多困難；

“博客日歷”，每個(gè)日期都是一個(gè)超鏈接。

服務(wù)器端自動生成的超鏈接VS 網(wǎng)頁作者手工編輯添加的鏈接。

GWeb ( V , E）的節(jié)點(diǎn)集合規(guī)模

通過域名注冊服務(wù)商可統(tǒng)計(jì)網(wǎng)站、域名數(shù)量且較為準(zhǔn)確；

統(tǒng)計(jì)網(wǎng)站涉及的網(wǎng)頁數(shù)目就會面臨上面提到的問題；

研究中通常用搜索引擎的索引規(guī)模來估算萬維網(wǎng)鏈接圖的節(jié)點(diǎn)規(guī)模； 3

沒被任何一個(gè)搜索引擎收錄的網(wǎng)頁，被用戶訪問到的可能性微乎其微； 2008年7月，谷歌索引量1萬億網(wǎng)頁，一定程度上反映了GWeb (V, 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ù)對GWeb (V , E ）的邊集合規(guī)模有一個(gè)概括性的認(rèn)識；

AltaVista 語料庫，鏈接關(guān)系圖包含 2.03 億個(gè)網(wǎng)頁、14.66 億條鏈接。 Clueweb09 語料庫，鏈接關(guān)系圖包含的節(jié)點(diǎn)數(shù)為 1040 809705個(gè)，對應(yīng)的出鏈接數(shù)為7944351835個(gè)。

sogouT 語料庫，鏈接關(guān)系圖包含1.39 億個(gè)網(wǎng)頁、33 . 4億條鏈接。

從這些語料庫，可以估計(jì)，邊集合的規(guī)模要大于節(jié)點(diǎn)集合的規(guī)模，約為節(jié)點(diǎn)集合規(guī)模的幾到幾十倍。

4

8.1.2 萬維網(wǎng)鏈接圖的連通情況

定義：導(dǎo)出子圖

給定 G=(V, E)，如果存在另外一個(gè)圖 G /=(V/,E /) ，滿足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)出子圖，對于該子圖中其中的任意兩個(gè)節(jié)點(diǎn)u 和v ，都存在一條路徑使得從u 可以訪問到v 。

性質(zhì)：

1、一個(gè)有向圖中可有多個(gè)強(qiáng)連通子圖。

2、強(qiáng)連通子圖之間不存在公有節(jié)點(diǎn)；否則可以合二為一。

對萬維網(wǎng)連接圖，每個(gè)強(qiáng)連通子圖都代表著構(gòu)成該子圖的節(jié)點(diǎn)是相互連通的，通過超鏈接通過一個(gè)網(wǎng)頁可訪問另一個(gè)。

定義：弱連通子圖

給定一個(gè)有向圖，該有向圖的一個(gè)弱連通子圖是指由一部分節(jié)點(diǎn)組成的一個(gè)導(dǎo)出子圖，對于該子圖中其中的任意兩個(gè)節(jié)點(diǎn)u 和v ，都存在一條無向路徑使得從u 可以訪問到v 。

對于萬維網(wǎng)鏈接圖，重點(diǎn)考察其包含的強(qiáng)、弱連通子圖的規(guī)模分布情況，借此了解整個(gè)鏈接圖的拓?fù)浣Y(jié)構(gòu)和連通情況。

2000年，Broder 的研究成果，萬維網(wǎng)鏈接結(jié)構(gòu)圖的強(qiáng)、弱連通子圖的規(guī)模 5

分布情況如下圖所示。

● 圖中，橫軸為連通子圖規(guī)模，縱軸為連通子圖數(shù)量；

● 橫軸、縱軸使用對數(shù)坐標(biāo)軸。

● 可以看出強(qiáng)連通子圖、弱連通子圖的規(guī)模分布規(guī)律基本相同； ● 設(shè)連通子圖規(guī)模為Size ，具有規(guī)模Size 的連通子圖的數(shù)目Number 近似滿足；

指數(shù)形式表示為：

幾點(diǎn)結(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)系，可以對整個(gè)網(wǎng)絡(luò)頁面的鏈接結(jié)構(gòu)關(guān)系有一個(gè)清晰的認(rèn)識。

根據(jù)Broder 的研究結(jié)論繪制的萬維網(wǎng)鏈接結(jié)構(gòu)示意圖如下圖所示。 6

Core 部份

規(guī)模最大的強(qiáng)連接子圖；

IN 部分

所有鏈接到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)頁。

之外網(wǎng)頁，一部份與IN 、OUT 有鏈接關(guān)系，另一部分與IN 、● IN 、Core 、OUT

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)鏈接，以及鏈接到其他節(jié)點(diǎn)的情況。

萬維網(wǎng)鏈接圖 GWeb (V,E) 的入度、出度分布符合冪律；

入度為Indegree 的網(wǎng)頁數(shù)目 N ( Indegree ）近似滿足：

出度為Outdegree 的網(wǎng)頁數(shù)目 N ( Outdegree ）近似滿足：

7

其中α、β均為值大于零的參數(shù)，而C 與 C /為常數(shù)。

Broder 的實(shí)驗(yàn)結(jié)果如下圖所示。

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 格式：

超鏈接的特性

如果存在超鏈接L 從頁面Psource 指向頁面Pdestiny ，則Psource 與 Pdestiny 滿足：

特性1 :內(nèi)容推薦特性

頁面Psource 的作者推薦頁面Pdestiny 的內(nèi)容，且利用L 的鏈接文本內(nèi)容對Pdestiny 進(jìn)行描述。

特性2 :主題相關(guān)特性

被超鏈接連接的兩個(gè)頁面Psource 與Pdestiny 的頁面內(nèi)容涉及類似的主題。

8

特性1說明：

● 入鏈接個(gè)數(shù)是頁面受其他頁面推薦程度大小的標(biāo)志，入鏈越多，該頁面受其他網(wǎng)頁作者的推薦越多，其網(wǎng)頁內(nèi)容質(zhì)量高。

● 入鏈接個(gè)數(shù)越少，說明該頁面不被其他網(wǎng)頁作者推薦，意味著頁面內(nèi)容或組織形式不受歡迎。

● 鏈接文本起到對網(wǎng)頁內(nèi)容描述的作用，由于描述來自他人，通常被認(rèn)為是對網(wǎng)頁內(nèi)容更加客觀的描述。

這就在頁面質(zhì)量與超鏈接結(jié)構(gòu)圖的拓?fù)潢P(guān)系間建立了聯(lián)系，為頁面內(nèi)容質(zhì)量評價(jià)提供了一種不基于內(nèi)容的方式。

HITS 算法、PageRank 算法是依據(jù)該特性設(shè)計(jì)的。

特性2說明

● 與特性1相比，特性2的重要程度、適用性低一些；

頁面內(nèi)容相關(guān)的可能性要大于隨機(jī)抽取的兩個(gè)頁面； ● Psource 、Pdestiny

● 超鏈接表示的不僅是內(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)，對鏈接結(jié)構(gòu)分析造成了相當(dāng)?shù)睦щy。

版權(quán)、注冊鏈接

9

● 版權(quán)信息、注冊信息往往以超鏈接的形式存在，以便查閱；

● 這類超鏈接數(shù)目大；

● 不符合超鏈接應(yīng)具有的兩個(gè)特性。

相當(dāng)多超鏈接不符合超鏈接算法設(shè)計(jì)中的假設(shè)

● 各種鏈接結(jié)構(gòu)分析算法在真實(shí)環(huán)境中無法單獨(dú)被用于網(wǎng)頁質(zhì)量評估

● 改進(jìn)算法還是可以為頁面質(zhì)量評估提供參考；

● 數(shù)據(jù)清理后的近似理想環(huán)境中，還是可以發(fā)揮作用。

本章，假設(shè)萬維網(wǎng)結(jié)構(gòu)中的超鏈接滿足以上兩個(gè)特性。

8.3 HITS 算法的基本思路及實(shí)現(xiàn)

HITS 算法：

HITS 是Hyperlink-Induced Topic Search的縮寫，基于超鏈接推演的主題搜索算法。

核心思想；

● 對網(wǎng)頁的“內(nèi)容權(quán)威度”、“鏈接權(quán)威度”進(jìn)行評價(jià)；

● 內(nèi)容權(quán)威度 ( Authority Value )：網(wǎng)頁本身內(nèi)容的受歡迎程度；

：網(wǎng)頁鏈接到其他受歡迎資源的程度。 ● 鏈接權(quán)威度（Hub Value )

例：學(xué)術(shù)論文

內(nèi)容權(quán)威度：內(nèi)容質(zhì)量比較高、創(chuàng)新性較強(qiáng)、對學(xué)科發(fā)展能起到較大的推進(jìn)作用。 鏈接權(quán)威度：對某個(gè)特定領(lǐng)域進(jìn)行了較為詳盡的調(diào)研，能夠介紹相當(dāng)數(shù)目的內(nèi)容

質(zhì)量高的其他論文和研究工作。

網(wǎng)頁內(nèi)容權(quán)威度：

10