1 北京大學(xué)碩士研究生學(xué)位論文 題目： 結(jié)合語(yǔ)義相似度的鏈接分析 姓 名：朱家稷 學(xué) 號(hào)： 10308194 院 系：信息科學(xué)技術(shù)學(xué)院 專(zhuān) 業(yè)：計(jì)算機(jī)軟件與理論 研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo) 師：李曉明 教授 2006 年 5 月 2 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個(gè)人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問(wèn)題，將可能承擔(dān)法律責(zé)任。 3 摘要 鏈接分析技術(shù) 作為文本分析和日志挖掘 技術(shù) 的有效補(bǔ)充， 被廣泛應(yīng)用在主題提取、網(wǎng)頁(yè)分類(lèi)、資源發(fā)現(xiàn)等諸多 息處理任務(wù)和服務(wù)中。 由于 巨大 、動(dòng)態(tài)變化 和復(fù)雜 ， 給鏈接分析技術(shù)帶來(lái)了很大的挑戰(zhàn)。 鏈接表達(dá)了網(wǎng)頁(yè) 間復(fù)雜而隱蔽的關(guān)系 。 為了更有效的進(jìn)行鏈接分析， 需要 細(xì)致的考察并 區(qū)分 對(duì)待不同的 鏈接 關(guān)系 （后面如何體現(xiàn)？） 。 在本文中 我們 研究 了 鏈接網(wǎng)頁(yè)間多種屬性，包括 網(wǎng)頁(yè)的入度、出度分布， 內(nèi)容相似度 和 鏈接相似度 等 ， 并且引入了語(yǔ)義相似度 的概念 。 語(yǔ)義相似度 描述了 網(wǎng)頁(yè) 表達(dá)的 潛在主題間的相似程度。 它與內(nèi)容相似度和鏈接相似度相關(guān)卻 又有很大差別 。它更 精 確 的 刻畫(huà) 了鏈接網(wǎng)頁(yè) 間 語(yǔ)義上的關(guān)聯(lián)程度 。 我們用 語(yǔ)義相似度作為區(qū) 分 鏈接 權(quán)重的 標(biāo)準(zhǔn)，并將它應(yīng)用在 改進(jìn)中。 在 基本框架下，我們提出了如下假設(shè)：瀏覽者在選擇鏈接瀏覽下一網(wǎng)頁(yè)時(shí)，他以更大的概率選擇與當(dāng)前網(wǎng)頁(yè)主題相似的 網(wǎng)頁(yè)鏈接；并且網(wǎng)頁(yè) 間 的語(yǔ)義相似度恰好 刻畫(huà)了網(wǎng)頁(yè)間主題間的這種 相似程度。 直接計(jì)算網(wǎng)頁(yè)間的語(yǔ)義相似度是 困難的。為此我們計(jì)算了鏈接網(wǎng)頁(yè)間的內(nèi)容相似度和鏈接相似度，并結(jié)合當(dāng)前的研究 成果 探索了 三者間的聯(lián)系。 我們 發(fā)現(xiàn) 接網(wǎng)頁(yè)間的內(nèi)容相似度和鏈接相似度 的 并 且在 實(shí)驗(yàn) 中使 用不同的函數(shù)來(lái)模擬語(yǔ)義相似度和內(nèi)容相似度之間的關(guān)系。 實(shí)驗(yàn)證明，改進(jìn)后的 序在主題提取任務(wù)中優(yōu)于改進(jìn)前的序 。 關(guān)鍵詞： 萬(wàn)維網(wǎng) ， 搜索引擎， 鏈接分析，語(yǔ)義相似度， to eb to ebs its a to It if we to In we of we of of in is to We as of it to a a he is of he is is is We of we we of to of in 5 第 1 章 引言 . 7 究背景 . 7 文研究?jī)?nèi)容 . 8 1 3 本文貢獻(xiàn) . 8 文組織 . 9 第 2 章 相關(guān)研究 . 10 掘 . 10 接分析 . 11 型 . 11 量和算法 . 15 接分析的應(yīng)用 . 19 索引擎 . 20 索引擎發(fā)展歷史 . 21 索引擎分類(lèi) . 22 于 搜索引擎基本原理 . 25 義相似度 . 26 第 3 章 鏈接結(jié)構(gòu)的特征 . 28 頁(yè)的鏈接特征 . 28 接的 性 . 28 頁(yè)的鏈入鏈出分布 . 29 頁(yè)間的內(nèi)容相似度 . 29 頁(yè)的鏈接相似度 . 30 頁(yè)的語(yǔ)義相似度 . 31 容相似度、鏈接相似度和語(yǔ)義相似度之間的聯(lián)系 . 31 6 頁(yè)的鏈接特征 . 32 接網(wǎng)頁(yè)的 征 . 33 接網(wǎng)頁(yè)的入度出度分布 . 36 接網(wǎng)頁(yè)間的 內(nèi)容相似度 . 36 接網(wǎng)頁(yè)間的鏈接相似度 . 38 接網(wǎng)頁(yè)間內(nèi)容相似度和鏈接相似度的關(guān)系 . 39 第 4 章 結(jié)合語(yǔ)義相似度的鏈接分析 . 42 缺陷 . 43 合語(yǔ)義相似度的 . 45 式 . 46 合語(yǔ)義相似度的 驗(yàn) . 49 驗(yàn)數(shù)據(jù)集和測(cè)試集 . 49 驗(yàn)步驟和設(shè)置 . 51 驗(yàn)結(jié)果 . 52 法總結(jié)和啟示 . 58 結(jié) . 60 望 . 60 參考資料 . 62 作者就讀期間參加的科研項(xiàng)目和發(fā)表的論文 . 67 致謝 . 68 7 第 1 章 引言 研究背景 萬(wàn)維網(wǎng)（ 記為 因特網(wǎng)上最成功的應(yīng)用 。 隨著信息的飛速增長(zhǎng)，針對(duì) 信息檢索已成為一個(gè)最具挑戰(zhàn)的工作。 在對(duì) 網(wǎng)頁(yè)進(jìn)行分析處理的過(guò)程中，傳統(tǒng)信息檢索領(lǐng)域的技術(shù)自然的會(huì)被引用進(jìn)來(lái)。但 網(wǎng)頁(yè)與傳統(tǒng)的文檔相比 ，人們發(fā)現(xiàn) 的網(wǎng)頁(yè)有一個(gè)極大的相異點(diǎn) 鏈接 。如果我們將每個(gè)網(wǎng)頁(yè)認(rèn)為是一個(gè)節(jié)點(diǎn)，每一條 鏈接 認(rèn)為是一條有向邊，那么整個(gè) 構(gòu)成了一個(gè)龐大的有向圖。 鏈接結(jié)構(gòu)對(duì)網(wǎng)頁(yè)分析處理提供了更多的信息和手段。 鏈接分析技術(shù)已應(yīng)用于多種目的： 衡量特定主題的網(wǎng)頁(yè)質(zhì)量。目前的搜索引擎幾乎都使用了鏈接分析技術(shù)對(duì)返回結(jié)果網(wǎng)頁(yè)進(jìn)行排序，最重要的有 法。 描述 構(gòu)特征。比如網(wǎng)頁(yè)的入度和出度分布， 徑， 區(qū)等。 網(wǎng)頁(yè)分類(lèi)。結(jié)合鏈接信息和內(nèi)容信息的網(wǎng)頁(yè)分類(lèi)的效果高于只基于內(nèi)容信息分類(lèi)算法，甚至只依據(jù)鏈接信息的分類(lèi)效果與內(nèi)容分類(lèi)效果相當(dāng)。（適當(dāng)?shù)囊?be 網(wǎng)頁(yè)搜集 。 依據(jù)鏈接信息，可以針對(duì)某個(gè)主題或特定目的，對(duì) 行高效的網(wǎng)頁(yè)搜集。 個(gè)性化。鏈接分析和用戶(hù)的 為日志結(jié)合，可以更好預(yù)測(cè)用戶(hù)意圖，以提供更好的用戶(hù)體驗(yàn)。 8 但同時(shí)我們也應(yīng)該看到目前鏈接分析的一些局限和缺點(diǎn)： 正由于鏈接分析技術(shù)的成功，使得很多網(wǎng)站為了提高自身的聲望，使用了各種 術(shù)使原有的鏈接分析算法產(chǎn)生誤差 。 (算法 缺點(diǎn)： 抵抗 性能差？ ) 鏈接有多種目的和類(lèi)型，而傳統(tǒng)的鏈接分析算法沒(méi)有區(qū)別對(duì)待不同類(lèi)型的鏈接，這使得鏈接分析的結(jié)果 與人們的期望之間產(chǎn)生差別。 鏈接分析技術(shù)沒(méi)有和其 它網(wǎng)頁(yè)分析技術(shù)很好的結(jié)合。 (s 本文相信，如果能夠改進(jìn)上述的缺點(diǎn)和局限，鏈接分析的效果 將會(huì)更加明顯。本文 的研究工作也是基于這個(gè)目標(biāo)展開(kāi)的。 文研究?jī)?nèi)容 本文的研究圍繞以下幾個(gè)方面進(jìn)行： 分析 接 網(wǎng)頁(yè)間 的特征 ， 主要包括 鏈接 網(wǎng)頁(yè)的內(nèi)容相似度、鏈接相似度和語(yǔ)義相似度 。 給出它們的定義和計(jì)算公式，并描述三者間的區(qū)別和聯(lián)系。 對(duì) 順沿鏈接的跳轉(zhuǎn)策略 進(jìn)行改進(jìn)：選擇鏈接的 網(wǎng)頁(yè)跳轉(zhuǎn) 概率不是 均等 的，而是 與 鏈接網(wǎng)頁(yè)間的語(yǔ)義相似度 相關(guān) 的。 通過(guò) 網(wǎng)頁(yè)間的內(nèi)容相似度來(lái)模擬 語(yǔ)義相似 度， 重新 評(píng)估鏈接權(quán)重 和跳轉(zhuǎn)概率， 改進(jìn) 法。 1 3 本文貢獻(xiàn) 本文 在鏈接分析中 引入 了 鏈接網(wǎng)頁(yè)間的語(yǔ)義相似度來(lái) 作為鏈接權(quán)重的評(píng)判標(biāo)準(zhǔn)，區(qū)別對(duì)待鏈接來(lái) 提高鏈接分析的效率。 本文認(rèn)為網(wǎng)頁(yè)鏈接與論文引用的很大區(qū)別是鏈接的 目的和種類(lèi)更加復(fù)雜 。 而通過(guò)語(yǔ)義相似度作為鏈接可信度的參考，在鏈接分析中，區(qū)分對(duì)待不同的鏈接，會(huì)提高鏈接分析的效率。 9 分析 鏈接 網(wǎng)頁(yè)間 的 內(nèi)容相似度、鏈接相似度和語(yǔ)義相似度 ，考查三者間的區(qū)別和聯(lián)系， 嘗試了用 幾種函數(shù) 來(lái)模擬 內(nèi)容相似度 和 語(yǔ)義相似度 之間的關(guān)系，并比較 了 它們的效果 。 利用 語(yǔ)義相似度 改 進(jìn) 法。 在 隨機(jī)游走模型中，瀏覽者沿著鏈接跳向下一個(gè)網(wǎng)頁(yè)的概率是相同的 。而我們認(rèn)為，瀏覽者跳向鏈接的概率取決 當(dāng)前網(wǎng)頁(yè) 與鏈接網(wǎng)頁(yè) 間 的語(yǔ)義相似度：瀏覽者以更大的概率跳向 相似 主題網(wǎng)頁(yè)的鏈接（即網(wǎng)頁(yè)間語(yǔ)義相似度較高的鏈接）。通過(guò) 內(nèi)容相似度來(lái)模擬語(yǔ)義相似度，并重新 評(píng)估網(wǎng)頁(yè)間跳轉(zhuǎn)的概率 來(lái)計(jì)算 實(shí)驗(yàn)證明， 改進(jìn)后的 于主題提取任務(wù)的精度 比原先提高了 5以上。 文組織 本文后面是這樣組織的，第 2 章是相關(guān)領(lǐng)域的研究；第 3 章討論網(wǎng)頁(yè)鏈接的特征 ，給出 了鏈接 網(wǎng) 頁(yè)間各種相似度的定義和計(jì)算公式，并用 為 實(shí)驗(yàn) 數(shù)據(jù) 計(jì)算和分析 這些相似度 ；第 4 章給出 結(jié)合 網(wǎng)頁(yè) 語(yǔ)義相似度的 進(jìn)算法和 實(shí)驗(yàn) 結(jié)果；第 5 章是對(duì)本文的總結(jié)和對(duì)未來(lái)工作的展望。 10 第 2章 相關(guān)研究 掘 鏈接分析本身屬于一個(gè)更大的研究領(lǐng)域的一部分 掘。 掘是應(yīng)用數(shù)據(jù)挖掘技術(shù)來(lái)從 據(jù)中抽取有用信息。用于 掘分析的數(shù)據(jù)種類(lèi)包括內(nèi)容數(shù)據(jù)、結(jié)構(gòu)數(shù)據(jù)和用 法 數(shù)據(jù) 3。 因此 掘可以根據(jù)要挖掘的數(shù)據(jù)種類(lèi)劃分為三類(lèi) 3, 4： 1 容挖掘： 容挖 掘是從 檔的內(nèi)容中抽取有用信息。內(nèi)容數(shù)據(jù)是網(wǎng)頁(yè)要傳達(dá)給用戶(hù)的事實(shí)集合。它可以包括文字、圖片、音頻、視頻、或者結(jié)構(gòu)記錄比如列表或表格等。這個(gè)領(lǐng)域的研究經(jīng)常包括其它學(xué)科的技術(shù)，比如信息檢索（ 自然語(yǔ)言處理（ 2 構(gòu)挖掘： 典型的 結(jié)構(gòu)是以網(wǎng)頁(yè)為節(jié)點(diǎn)，以連接兩個(gè)相關(guān)網(wǎng)頁(yè)的鏈接為邊的圖。 此外，網(wǎng)頁(yè)內(nèi)部也可以根據(jù)自身的 簽組織為一個(gè)樹(shù)形結(jié)構(gòu)。因此， 構(gòu)挖掘是從 發(fā)現(xiàn)結(jié)構(gòu)信息的過(guò)程。這種挖掘既可 在網(wǎng)頁(yè)的層面上（ 也可以是在鏈接的層面上（ 3 法挖掘： 法挖掘是應(yīng)用數(shù)據(jù)挖掘技術(shù)從 據(jù)中發(fā)現(xiàn)有趣的使用模式，以用來(lái)理解和更好的服務(wù)于基于 應(yīng)用需求 3。用法數(shù)據(jù)跟蹤 戶(hù)在訪(fǎng)問(wèn) 點(diǎn)時(shí)的瀏覽行為，典型的記錄包括 戶(hù)的 所 訪(fǎng)問(wèn) 的 頁(yè)面和訪(fǎng)問(wèn)時(shí)間。 圖 1 展示了 掘領(lǐng)域研究的一個(gè) 層 次 分類(lèi)。對(duì)于 構(gòu)挖掘，我們可以把這個(gè)領(lǐng)域再劃分兩個(gè)類(lèi)別，即文檔結(jié)構(gòu)分析（比如 鏈接分析（連接多個(gè)文檔的鏈接結(jié)構(gòu)）。如圖所示，鏈接分析主要專(zhuān) 11 注于文檔間的鏈接結(jié)構(gòu)所提取出的信息。但是，鏈接分析可以與文檔結(jié)構(gòu)分析，容挖掘或 法挖掘結(jié)合使用。 比如，鏈接提供的結(jié)構(gòu)信息和 容結(jié)合，可以更好的挖掘 用信息和衡量信息質(zhì)量。 圖 1. 掘分類(lèi)及鏈接分析在 構(gòu)挖掘中的 位置 (摘自 2) 接分析 根據(jù) 2的總結(jié)， 鏈接分析的研究 包括模型、度量標(biāo)準(zhǔn)及算法，以及應(yīng)用等。以下給出這些研究的描述。 型 大多數(shù)鏈接分析的 研究都會(huì)有一個(gè)基本的 構(gòu)的表示模型，各種度量和算法都基于這個(gè)模型衍生而來(lái)。 不同類(lèi)型的模型包括圖結(jié)構(gòu)模型，統(tǒng)計(jì)模型，網(wǎng)絡(luò)流模型等。 12 1. 圖結(jié)構(gòu)模型 在這一節(jié)，我們討論各種 掘中表示某種概念和信息單元的圖結(jié)構(gòu)。圖結(jié)構(gòu)包括單節(jié)點(diǎn)結(jié)構(gòu)，多節(jié)點(diǎn)結(jié)構(gòu)和圖中所有節(jié)點(diǎn)的結(jié)構(gòu)。 單節(jié)點(diǎn)結(jié)構(gòu) 單節(jié)點(diǎn)結(jié)構(gòu)模型包括一個(gè)單獨(dú)的節(jié)點(diǎn)（網(wǎng)頁(yè)），以及鏈向它或從它鏈出的鏈接。 個(gè) 頁(yè)是指被大量其它網(wǎng)頁(yè)鏈向的網(wǎng)頁(yè)。 個(gè) 頁(yè)是指鏈向大量其它網(wǎng)頁(yè)的網(wǎng)頁(yè)。 一個(gè)好的 頁(yè)會(huì)鏈向很多 好的 頁(yè)；而好的 頁(yè)會(huì)被很多好的 頁(yè)所鏈向。 概念首先在 30中被引出。單節(jié)點(diǎn)模型通常用來(lái)決定網(wǎng)頁(yè)的質(zhì)量 11, 12, 13。 多節(jié)點(diǎn)結(jié)構(gòu) 多節(jié)點(diǎn)結(jié)構(gòu)包括多個(gè)節(jié)點(diǎn)以及它們之間的鏈接。一些結(jié)構(gòu)和模式已經(jīng)在 14中討論。我們下面將描述這些模型和概念： 共同 鏈入 （ 如果節(jié)點(diǎn) A 同時(shí)鏈向節(jié)點(diǎn) B 和 C，那 么 節(jié)點(diǎn) B 和C 被 A 共同 鏈入 。在 ，共同 鏈入 直觀上表明網(wǎng)頁(yè) B 和 C 間的某種 相 似。 共同 鏈出（ 如果節(jié)點(diǎn) B 和 C 同時(shí)鏈向節(jié)點(diǎn) A，那么節(jié)點(diǎn) 共同鏈出 A。和共同鏈入一樣，共同鏈出也表明 網(wǎng)頁(yè) B 和 C 間的某種相似。 有向二分圖 (如果圖 G 可以劃分為兩個(gè)節(jié)點(diǎn)集合 ，每條有向邊都從 F 中的某個(gè)節(jié)點(diǎn) u 鏈向 C 中某個(gè)節(jié)點(diǎn) v，那么圖 G 為有向二分圖。 13 完全二分圖（ 如果二分圖 G 包含所有的從 F 鏈向 C 的邊，那么 G 為完全二分圖。 二分核（ 核 (i, j)是一個(gè)完全有向二分子圖，并且 F 中至少包含 i 個(gè)節(jié) 點(diǎn)，而 C 中至少包含 j 個(gè)節(jié)點(diǎn)。 在 中，這包含鏈接的 i 個(gè)網(wǎng)頁(yè)被稱(chēng)為“ 而被鏈向的 j 個(gè)網(wǎng)頁(yè)被稱(chēng)為“ 從概念角度來(lái)說(shuō)，二分核的“ “ 本就是 頁(yè)和 頁(yè)。 對(duì)某個(gè)主題的網(wǎng)頁(yè)集合來(lái)說(shuō)，可以尋找二分核來(lái)發(fā)現(xiàn)該主題的 頁(yè)核 頁(yè)。 頁(yè)和 頁(yè)表示了這個(gè)主題的良好的信息來(lái)源。 社區(qū)（ 社區(qū)是 被 頁(yè)共同鏈向的 頁(yè) 的核心 15。它還被定義被一組網(wǎng)頁(yè)集合，使得集合 中網(wǎng)頁(yè)在社區(qū)內(nèi)的鏈接度（任意方向）大于社區(qū)外的鏈接度 16。 整體圖結(jié)構(gòu) 領(lǐng)結(jié)模型（ 7, 17提出了 的領(lǐng)結(jié)模型，詳細(xì)描述了的各種屬性、度量和方法。領(lǐng)結(jié)結(jié)構(gòu)包含一個(gè)強(qiáng)連通部分（ 一個(gè)鏈向 部分（ 一個(gè)被 向的部分（ 還有一些不相連的部分。 2. 馬爾可夫模型（ n 階馬爾可夫鏈表示系統(tǒng)的下一狀態(tài)只由當(dāng)前狀態(tài)和前 狀態(tài)決定。 1階馬爾可夫模型通常用來(lái)模擬用戶(hù)的瀏覽行為。 1和隨機(jī) 8就使用了基于馬爾可夫模型的隨機(jī)游走過(guò)程：用戶(hù)隨機(jī)選擇跳向某個(gè)新網(wǎng)頁(yè)或跟隨鏈接到某個(gè)網(wǎng)頁(yè)（在 是正向鏈接，而在隨機(jī) 根據(jù)不同的時(shí)間步，選擇正向鏈接或反向鏈接）。 其它的方法，比如 2也引入了 14 馬爾可夫隨機(jī)游走過(guò)程。 19中使用馬爾可夫鏈為自適應(yīng)網(wǎng)站預(yù)測(cè)鏈接。 走模型， 即基于馬爾可夫模型的鏈接跳動(dòng)，被鏈接分析 大量 使用 。 3. 最大流模型（ 大流問(wèn)題可以表述如下：圖 G=(V, E)，每條邊被賦予為正數(shù)的傳輸能力， s 和 t 是 G 的兩個(gè)不同節(jié)點(diǎn)，問(wèn)題是要找到從 s 到 t 的最大流能力。 20提出最大流問(wèn)題等價(jià)于“ 題，即從圖 G 去掉最小數(shù)量的邊，使得 s和 t 分割。 已有一些算法被提出來(lái)解決這個(gè)問(wèn)題 21, 22。 17, 23中應(yīng)用這些算法來(lái)識(shí)別“ 區(qū)”，其被定義為“社區(qū)內(nèi)部鏈接度大于社區(qū)外部鏈接度的網(wǎng)頁(yè)集合”。 4. 概率關(guān)系模型（ 概率關(guān)系模型是關(guān)系模型和貝葉斯置信網(wǎng)絡(luò)的結(jié)合。 類(lèi)內(nèi)部屬性的關(guān)系合類(lèi)間屬性的關(guān)系可以 通過(guò)賦予不同的概率分布來(lái)建模。 24將網(wǎng)頁(yè)和鏈接作為實(shí)體，并賦予它們間以關(guān)系。一個(gè)網(wǎng)頁(yè)實(shí)體的屬性包括： ；而鏈接實(shí)體包含屬性 示網(wǎng)頁(yè)實(shí)體間的關(guān)系。通過(guò)預(yù)先給出的網(wǎng)頁(yè)實(shí)體 性 的概率分布，可以利用貝葉斯和置信傳播方法來(lái)進(jìn)行文檔分類(lèi)。 5. 其它模型 25提出“ 識(shí)別 頁(yè)。 26中定義頁(yè)為被多個(gè)網(wǎng)頁(yè)鏈向的網(wǎng)頁(yè)，且根據(jù) 它們的社區(qū)中排名靠前；其目的在于識(shí)別剛浮現(xiàn)出的社區(qū) 。 還有其它一些對(duì) 改進(jìn) 18, 12, 27, 28 , 29在這里不在討論。 15 量 和算法 鏈接可以用來(lái)作為單個(gè)網(wǎng)頁(yè)、一組網(wǎng)頁(yè)或整個(gè) 構(gòu)屬性的度量標(biāo)準(zhǔn)。例如，鏈接分析已被用來(lái)作為衡量主題網(wǎng)頁(yè)的權(quán)威性、網(wǎng)頁(yè)知名度和網(wǎng)頁(yè)間距離的有效工具。已有多種方法利用鏈接分析來(lái)衡量網(wǎng)頁(yè)質(zhì)量。一些標(biāo)準(zhǔn)基于 一些基于 構(gòu)的完全二分圖和二分核，還有的基于概率和隨機(jī)方法。這些度量標(biāo)準(zhǔn)還有一個(gè)區(qū)別是它 們是否與查詢(xún)相關(guān)。在本節(jié)，將給出利用鏈接信 息的一些的常用 的度量 和算法 。 鏈接在衡量單個(gè)網(wǎng)頁(yè)、一組網(wǎng)頁(yè)和整個(gè) 的屬性上非常有用。平均點(diǎn)擊度（ 利用鏈接結(jié)構(gòu)衡量網(wǎng)頁(yè)間距離的一種方法。 可以根據(jù)度量的元素是單個(gè)網(wǎng)頁(yè)、多個(gè)網(wǎng)頁(yè)和整個(gè) 這些度量標(biāo)準(zhǔn)進(jìn)行分類(lèi)。 1、 0、 2和網(wǎng)頁(yè)知名度（ 13用來(lái)衡量單個(gè)網(wǎng)頁(yè)的質(zhì)量。 對(duì)網(wǎng)頁(yè)質(zhì)量進(jìn)行 排名 的一個(gè)標(biāo)準(zhǔn)。 11使用這個(gè)度量 應(yīng)用于索引擎。其 主要思想是如果 一個(gè)網(wǎng)頁(yè)的所有鏈入網(wǎng)頁(yè)的排名總和很高，那么這個(gè)網(wǎng)頁(yè)的排名也會(huì)很高。因此一個(gè)網(wǎng)頁(yè)的排名取決于鏈向它的網(wǎng)頁(yè)的排名。排名是一個(gè)迭代的過(guò)程，直到所有網(wǎng)頁(yè)的排名穩(wěn)定。 排名的公式如下： 直觀上看， 在 上的隨機(jī)游走的分析方法。表示一個(gè)隨機(jī)沖浪的用戶(hù)直接跳轉(zhuǎn)的概率，比如通過(guò)鍵入 書(shū)簽中或特定主頁(yè)中訪(fǎng)問(wèn)某個(gè)網(wǎng)頁(yè)。 n 表示總網(wǎng)頁(yè)數(shù)。 /n 即表示隨機(jī)直接跳轉(zhuǎn)到網(wǎng)頁(yè) 概率 。對(duì)所 16 有鏈向 網(wǎng)頁(yè) 從 著鏈接跳轉(zhuǎn)到 概率是 鏈接出度的倒數(shù)，即假設(shè)跳向任意鏈接的概率是相同的。其右面的項(xiàng)則表示 通過(guò)鏈接跳轉(zhuǎn)到網(wǎng)頁(yè)概率。 而整個(gè) 即表示用戶(hù)停留在網(wǎng)頁(yè) 概率。 與查詢(xún)無(wú)關(guān)的全局值。 33給出計(jì)算 高效方法。其它排名標(biāo)準(zhǔn)的穩(wěn)定性在 18, 27, 34中討論。根據(jù) 18, 34，只要高的網(wǎng)頁(yè)的鏈接結(jié)構(gòu)沒(méi)有改變，那么修改鏈接結(jié)構(gòu)對(duì)排名的影響不大。其中的一個(gè)主要原因在于隨機(jī)直接跳轉(zhuǎn)的存在。 文提到的 可以通過(guò) 法來(lái)計(jì)算。其主要過(guò)程是，首先通過(guò)查詢(xún)得到一組相關(guān)的網(wǎng)頁(yè)集合（ 加入 鏈入鏈出網(wǎng)頁(yè)得到擴(kuò)展的 構(gòu)造 網(wǎng)頁(yè) 的 和 可以通過(guò)如下公式迭代計(jì)算： 法對(duì)主題查詢(xún)的應(yīng)用是成功的。但有時(shí)候會(huì)出現(xiàn)“主題漂移”的現(xiàn)象，即一個(gè)細(xì)節(jié)查詢(xún)的結(jié)果可能是其概括問(wèn)題的結(jié)果，或者相反。其原因是 中鏈接密集處的主題結(jié)果。 28, 29中對(duì) 的鄰接矩陣進(jìn)行了改進(jìn)。 1使用了基于 算法來(lái)進(jìn)行 集、網(wǎng)頁(yè)分類(lèi)和識(shí)別 區(qū)。 12提出。它結(jié) 17 合了隨機(jī)游走模型以及 的 樣， 是與查詢(xún)相關(guān)的。其主要思想是，在由查詢(xún)?cè)~構(gòu)成的 圖上隨機(jī)游走，游走者會(huì)以較大的概率訪(fǎng)問(wèn) 高質(zhì)量信息的網(wǎng)頁(yè)，即 較高的網(wǎng)頁(yè)；同樣，游走者會(huì)以較大的概率訪(fǎng)問(wèn)鏈向較高的 頁(yè)的網(wǎng)頁(yè)，即 較高的網(wǎng)頁(yè)。 它的查詢(xún)?cè)~網(wǎng)頁(yè)集合的構(gòu)造與 同，然后以此集合得到一個(gè)無(wú)向的二分圖 G。兩種游走方式來(lái)計(jì)算網(wǎng)頁(yè)的 。一種是游走于 G 的圖部分而生成 ，另一種游走于 G 的 圖而生成 執(zhí)行游走過(guò)程時(shí)，游走者從二分圖的一個(gè)部分開(kāi)始，每步跳躍兩條邊 第一條邊將他帶到圖 G 的另一部分，而第二條邊將他帶回原來(lái)的部分。利用馬爾可夫模型幫助即可估算出游走者訪(fǎng)問(wèn) 圖或 圖中某個(gè)節(jié)點(diǎn)的概率。 其游走過(guò)程的概率矩陣 H 和 A 表示如下： 通過(guò)計(jì)算 H 和 A 的主特征向量，即可得到網(wǎng)頁(yè)的 和 。由于引入了隨機(jī)游走， 會(huì) 出現(xiàn) “主題漂移”問(wèn)題。 13中，作者提出了網(wǎng)頁(yè)在不同主題下“聲望”的概念。與 似，它也是執(zhí)行兩階段隨機(jī)游走過(guò)程，并計(jì)算針對(duì)某個(gè)主題的網(wǎng)頁(yè)的 望和 望。其每步游走的原理是： 以概率 d0，游走者隨機(jī)直接跳向某個(gè)網(wǎng)頁(yè) ； 以概率 1走者從所在網(wǎng)頁(yè)沿著正向鏈接或反向鏈接跳向另一個(gè)網(wǎng)頁(yè)。 18 其 望和 望的定義分別是： 對(duì)某個(gè)主題，游走者正向游走訪(fǎng)問(wèn)網(wǎng)頁(yè) p 的概 率。 對(duì)某個(gè)主題，游走者反向游走訪(fǎng)問(wèn)網(wǎng)頁(yè) p 的概率。 其計(jì)算公式在這里就不在列出。 平均點(diǎn)擊度（ 在 34中提出用點(diǎn)擊度（ of 衡量網(wǎng)頁(yè)間的距離不能與人們的直覺(jué)相符。因?yàn)橛脩?hù)以較大的概率沿著鏈接數(shù)較少的網(wǎng)頁(yè)跳轉(zhuǎn)，而以較小的概率沿著鏈接數(shù)較多的網(wǎng)頁(yè)跳轉(zhuǎn)。因此，他們提出平均點(diǎn)擊度，它基于隨機(jī)游走中點(diǎn)擊某個(gè)鏈接的概率。根據(jù)這個(gè)模型，定義網(wǎng)頁(yè) p 中鏈接的長(zhǎng)度為 。因此網(wǎng)頁(yè) p 與 q 間的距離為 p 到 q 的最短路徑上的鏈接長(zhǎng)度之和。 平 均點(diǎn)擊度可以用來(lái)過(guò)濾網(wǎng)站以識(shí)別一定距離內(nèi)的 區(qū)，也可以用來(lái)衡量用戶(hù)在網(wǎng)站內(nèi)訪(fǎng)問(wèn)到需要信息的代價(jià)，以改善網(wǎng)站的友好性 和可用性 。 信息 氣味 （ 信息線(xiàn)索的概念是指利用網(wǎng)頁(yè)鏈接周?chē)男畔⑵瑪嘧鳛椤?氣味 ”來(lái)評(píng)估它鏈向的網(wǎng)頁(yè)質(zhì)量和訪(fǎng)問(wèn)該網(wǎng)頁(yè)的代價(jià) 41。 其基本思想是用戶(hù)在某個(gè)網(wǎng)頁(yè)搜尋信息時(shí)，會(huì)跟蹤“氣味”最濃的鏈接?！皻馕丁钡挠?jì)算方法是比較用戶(hù)信息需求與鏈接信息片斷的相似度。 其它 其它一些重要的概念包括網(wǎng)頁(yè)的共同入度和共同出度。 網(wǎng)頁(yè) p 和 q 的共同入度表示同時(shí)鏈向 p 和 q 的網(wǎng)頁(yè)數(shù) ，共同出度表示 p 和 q 同時(shí)鏈向的網(wǎng)頁(yè)數(shù)。 1 19 中討論了這些概念。 的屬性包括 徑，連 通 性、入度和出度分布等。 6, 7, 17給出了 徑的討論，并指出 頁(yè)的入度和出度分布遵從“ 布。在整個(gè) 構(gòu)研究中，發(fā)現(xiàn) 區(qū)是一個(gè)熱點(diǎn)。其主要方法是最大流方法17, 23。 接分析的應(yīng)用 鏈接分析技術(shù)被廣泛應(yīng)用，包括判斷主題網(wǎng)頁(yè)的質(zhì)量，網(wǎng)頁(yè)分類(lèi)，網(wǎng)頁(yè)搜集，社區(qū)發(fā)現(xiàn)，網(wǎng)站 優(yōu)化，個(gè)性化和網(wǎng)頁(yè)推薦等。本節(jié)將介紹一些應(yīng)用。 主題提?。?主題提取是從網(wǎng)頁(yè)集合中識(shí)別與主題最相關(guān)的網(wǎng)頁(yè)。在 50中它被定義為“尋找指定主題的密切聯(lián)系的 頁(yè)和 頁(yè)”。 法 30本身就是一種典型的主題提取算法?；谖臋n對(duì)象模型（ 更精細(xì)的鏈接分析算法在 50, 51中討論。 52改進(jìn) 出主題相關(guān)的法。 網(wǎng)頁(yè)分類(lèi) 網(wǎng)頁(yè)分類(lèi)是將網(wǎng)頁(yè)劃分到指定的類(lèi)別中。 53給出了 8 種網(wǎng)頁(yè)類(lèi)別和 7 種描述網(wǎng)頁(yè)特性的屬性。 54給出一種基于鏈接和上下文的自 動(dòng)網(wǎng)頁(yè)分類(lèi)方法，其主要思想是 如果一個(gè)網(wǎng)頁(yè)被其它網(wǎng)頁(yè)鏈向，其鏈接上下文會(huì)給予一定的權(quán)重，因?yàn)樗硎灸承┤送ㄟ^(guò)鏈接信息而閱讀了該網(wǎng)頁(yè)。 24將網(wǎng)頁(yè)和鏈接看作實(shí)體關(guān)系模型中的實(shí)體，并用概率關(guān)系模型來(lái)進(jìn)行網(wǎng)頁(yè)分類(lèi)。 55給出了利用主題類(lèi)別和自動(dòng)分類(lèi)器來(lái)估計(jì)整個(gè) 的主題分布。 區(qū)識(shí)別 20 整個(gè)互聯(lián)網(wǎng)存在著成千上萬(wàn)的社區(qū)。這些社區(qū)有的已經(jīng)以非常清晰的形式表現(xiàn)出來(lái) (例如，門(mén)戶(hù)網(wǎng)站中的層次目錄式結(jié)構(gòu) )。但是，在極度分散和無(wú)序的互聯(lián)網(wǎng)環(huán)境中。有理由認(rèn)為必然還存在更多潛在的未被發(fā)現(xiàn)和定義的互聯(lián)網(wǎng)社區(qū)從互聯(lián)網(wǎng)中 系統(tǒng)地抽取這些社區(qū)至少有以下 3 方面的意義： 這些社區(qū)為了解互聯(lián)網(wǎng)用戶(hù)的興趣提供了有價(jià)值的，甚至是最及時(shí)、最可靠的信息。 這些社區(qū)展現(xiàn)了互聯(lián)網(wǎng)社會(huì)學(xué) (of 研究和發(fā)現(xiàn)這些社區(qū)可以深入了解互聯(lián)網(wǎng)的進(jìn)化過(guò)程。 門(mén)戶(hù)網(wǎng)站通過(guò)識(shí)別和區(qū)分這些社區(qū)，可以更有效地組織它們的目錄層次(因?yàn)楹芏酀撛诘纳鐓^(qū)以很快的速度在增長(zhǎng)，而很多已經(jīng)清晰出現(xiàn)的社區(qū)又在逐漸消失 )。這同時(shí)意味著互聯(lián)網(wǎng)的自動(dòng)分類(lèi)成為可能。 主要的社區(qū)發(fā)現(xiàn)技術(shù)有最大流算法 17, 23的和基于 二分有向圖 算法 55。 集 “主題搜集”是一種針對(duì)特定主題的高效網(wǎng)頁(yè)搜集方法 50。 在搜集中，需要識(shí)別主題中好的 頁(yè)和 頁(yè)，還要決定是否跟蹤某個(gè)鏈接進(jìn)行搜集 50。 索引擎 人們帶來(lái)了巨大的方便，使人們可以跨越時(shí)間和空間的界限共享大量的信息。但是，面對(duì)如此大量的信息，人們同時(shí)也開(kāi)始感到無(wú)所適從。太多的信息使他們很難迅速定位到真正需要的信息，而跟隨超鏈 接 在 漫游則會(huì)浪費(fèi)大量的時(shí)間，而且很可能徒勞無(wú)功。因此，人們迫切需要有效的信息發(fā) 21 現(xiàn)工具來(lái)為他們?cè)?進(jìn)行導(dǎo)航。這種需求導(dǎo)致 了搜索引擎的問(wèn)世。搜索引擎迅速成為人們網(wǎng)上搜索的有效工具。 索引擎發(fā)展歷史 如何在 包含海量信息 的互聯(lián)網(wǎng)上獲得有價(jià)值的信息 一直是 戶(hù) 關(guān)注的焦點(diǎn) 問(wèn)題。搜索技術(shù)的出現(xiàn)為 用戶(hù) 快速 定位 所需信息帶來(lái)了福音。 1993 年，出現(xiàn)了最早的 覽器 年 出了 覽器的發(fā)展促使 到迅速推廣，同時(shí)也推動(dòng)著搜索引擎的發(fā)展。 1994 年春天 出現(xiàn)了最早的真正意義上的搜索引擎 當(dāng)時(shí) 序接入到其索引程序中 ，實(shí)現(xiàn)網(wǎng)頁(yè)的自動(dòng)發(fā)現(xiàn)和索引。隨后 , 相繼出現(xiàn)。這些搜索引擎主