【畢業(yè)學(xué)位論文】（Word原稿）結(jié)合語義相似度的鏈接分析-計算機系統(tǒng)結(jié)構(gòu)計算機網(wǎng)絡(luò)與分布式系統(tǒng)

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