北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 1 搜索引擎的信息覆蓋率評(píng)測(cè)模型研究 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 ， 100871 摘 要 本文從 向圖結(jié)構(gòu)出發(fā)，總結(jié)分析了搜索引擎搜集子系統(tǒng)網(wǎng)頁(yè)搜集不完全性的若干因素，指出信息覆蓋率這一概念的研究意義，由此提出了三類比較重要的信息覆蓋率概念。在對(duì)信息覆蓋率建立量化研究模型之后，本文以北大天網(wǎng) 臺(tái)為考察對(duì)象，以不同的方式對(duì)中國(guó) 行取樣，用 兩類典型的權(quán)值算法計(jì)算出其中的重要網(wǎng)頁(yè)作為樣本，從量和質(zhì)的角度上考察 信息覆蓋率，得到合理的數(shù)量覆蓋率和質(zhì)量覆蓋率實(shí)驗(yàn)數(shù)據(jù)，從而驗(yàn)證了 息覆蓋率結(jié)論的合理性和信息覆蓋率評(píng)測(cè)模型的可靠性。 關(guān)鍵詞 搜索引擎，信息覆蓋率，取樣，權(quán)值計(jì)算，驗(yàn)證，數(shù)量覆蓋率，質(zhì)量覆蓋率 1 研究背景 1989 年誕生并于次年開(kāi)始運(yùn)行以來(lái) ,在迄今為止的十多年里發(fā)展迅猛，已逐漸成為人類社會(huì)信息資源中的一個(gè)重要組成部分。它以超文本和超媒體為核心技術(shù)，將文本、圖形、圖像、音頻和視頻等信息有機(jī)結(jié)合起來(lái)，給人們以豐富的信息表示空間。隨著 術(shù) 和應(yīng)用的不斷發(fā)展，社會(huì)的信息化進(jìn)程不斷加快，越來(lái)越多的社會(huì)信息資源開(kāi)始選擇 為其載體。 當(dāng)前， 大約有 8,745,000 個(gè)網(wǎng)站，約 2,500,000,000 網(wǎng)頁(yè)，包含了至少 19且這些網(wǎng)頁(yè)正以每天凈增 7,500,000 的速度膨脹 1 2 。而在中國(guó)，根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)中心（ 2002 年 1 月進(jìn)行的互聯(lián)網(wǎng)統(tǒng)計(jì)報(bào)告 3， 注冊(cè)的域名數(shù)為 127,319 個(gè)，共有 277,100 個(gè) 點(diǎn)。到 2002 年為止，中國(guó)境內(nèi)的 點(diǎn)共有 53,432,598 個(gè)網(wǎng)頁(yè)，主要分布在 約 49,146 個(gè)網(wǎng)站中 4。 面對(duì)浩瀚的互聯(lián)網(wǎng)絡(luò)資源，人們?nèi)舨唤柚渌ぞ吆茈y快速的查找到自己所需要的信息，這帶來(lái)了搜索引擎的誕生。從 1994 年誕生的第一代搜索引擎 展到當(dāng)前流行的 系統(tǒng)，它們已逐漸成為人們進(jìn)行網(wǎng)際沖浪的重要工具之一。根據(jù)弗吉尼亞理工大學(xué) 心的調(diào)查報(bào)告 5 ，全世界有 戶通過(guò)搜索引擎獲得自己所需網(wǎng)頁(yè)，足見(jiàn)搜索引擎功用之一斑。 我們將每一條獨(dú)立的 息稱為一個(gè)網(wǎng)頁(yè)，它有一個(gè)唯一的資源定位地址稱為搜索引擎便是利用 間的連接關(guān)系，搜集其對(duì)應(yīng)的網(wǎng)頁(yè)信息，建立索引，供用戶查詢。因此，搜索引擎搜集的網(wǎng)頁(yè)集合便是用戶所能得到查詢結(jié)果的最大范圍；這個(gè)范圍越接近 索引擎越優(yōu)秀。事實(shí)上，沒(méi)有任何一個(gè)搜索引擎能搜集完 所有網(wǎng)頁(yè)。著名的搜索引擎 統(tǒng)和 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 2 統(tǒng)，搜集到并提供給用戶查詢的網(wǎng)頁(yè)數(shù)量分別是 2,073,418,204 個(gè) 6和 1,571,413,2077個(gè)，最多不過(guò)靜態(tài)網(wǎng)頁(yè)總數(shù)的 80%。而根據(jù) 200？年 3 月發(fā)表的搜索引擎統(tǒng)計(jì)數(shù)據(jù) 8？ ，這兩個(gè)系統(tǒng)的網(wǎng)頁(yè)數(shù)據(jù)量是最大的。 網(wǎng)絡(luò)上的信息數(shù)量巨大而且種類繁多，任何一個(gè)實(shí)際運(yùn)行的搜集系統(tǒng)都不可能將其全部搜盡。優(yōu)秀的搜索引擎總會(huì)搜集盡量多的網(wǎng)頁(yè)，更好的滿足用戶的查詢要求?？疾焖阉饕鎸?duì) 息資源的搜集覆蓋程度，可作為不斷改進(jìn)搜集系統(tǒng)的根據(jù)，對(duì)評(píng)價(jià)搜索引擎的性能好壞具有積極的作用。 另一方面，隨著社會(huì)信息化程度的不斷提高， 是該階段人類社會(huì)信息資源在網(wǎng)絡(luò)上的投影，記錄著人類社會(huì)的歷史發(fā)展進(jìn)程?；谒阉饕婕夹g(shù)開(kāi)發(fā)的網(wǎng)絡(luò)信息博物館正以 此為目的，力圖通過(guò)搜索引擎的網(wǎng)頁(yè)搜集系統(tǒng)不斷搜集 的所有網(wǎng)頁(yè)，若干年后能夠同時(shí)在時(shí)間和空間上展示 每一個(gè)角落。因此，研究搜索引擎的信息覆蓋率對(duì)驗(yàn)證網(wǎng)絡(luò)信息博物館網(wǎng)頁(yè)資源的有效性也有著十分重大的意義。 本文的研究工作基于上述目的，針對(duì)北京大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室開(kāi)發(fā)的 索引擎 8及以此為基礎(chǔ)開(kāi)發(fā)的網(wǎng)上信息博物館 ，采取多種方法從多個(gè)角度計(jì)算其信息覆蓋率，證明了該網(wǎng)頁(yè)搜集系統(tǒng)獲得的中國(guó)網(wǎng)絡(luò)信息資源是基本有效的。 2 模型概述 頁(yè)搜集的不完全性 如果把 的每一個(gè)網(wǎng)頁(yè)看作一個(gè)頂點(diǎn)，則這個(gè)頂點(diǎn)以 為它的唯一標(biāo)記；又由于網(wǎng)頁(yè)中存在其它網(wǎng)頁(yè)的 以把這種網(wǎng)頁(yè)間的鏈接看作連接頂點(diǎn)的邊，則整個(gè) 成了一張有向圖，如圖 1 示。相應(yīng)的，每一個(gè)頂點(diǎn)的入度和出度對(duì)應(yīng)著鏈向該網(wǎng)頁(yè)的網(wǎng)頁(yè)數(shù)量和該網(wǎng)頁(yè)鏈向其他網(wǎng)頁(yè)的數(shù)量。顯然， 這是一張不完全圖，因?yàn)槔锩娲嬖诤芏嗳攵然虺龆葹?0 的頂點(diǎn)。 當(dāng)前的網(wǎng)頁(yè)搜集系統(tǒng)都是基于對(duì)這種 接結(jié)構(gòu)的理解， 依據(jù)網(wǎng)頁(yè)之間的鏈接關(guān)系，從某一個(gè)種子 始，不斷的從新搜到的網(wǎng)頁(yè)中提取出 而到達(dá)其它的網(wǎng)頁(yè)。搜集過(guò)程中，通常需要對(duì)網(wǎng)頁(yè) 重要性作初步的判斷，優(yōu)先搜集相對(duì)有價(jià)值的網(wǎng)頁(yè)。在這種搜集機(jī)制里面，存在著下列問(wèn)題，導(dǎo)致無(wú)法遍歷所有的網(wǎng)頁(yè)。 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 3 部分網(wǎng)頁(yè)的入度為 0，即從任何一個(gè)網(wǎng)頁(yè)開(kāi)始，都不存在到它的路徑，這類網(wǎng)頁(yè)的數(shù)量約占全體網(wǎng)頁(yè)數(shù)量的 10%10 。 選擇的種子 合中，任何一個(gè)網(wǎng)頁(yè)都不存在到該網(wǎng)頁(yè)的路徑。 的有向圖結(jié)構(gòu)中，只有約 頂點(diǎn)能被選取作為起始點(diǎn)去遍歷剩下的約 90%的頂點(diǎn) 10。 由于在網(wǎng)頁(yè)搜集的過(guò)程中出現(xiàn)了優(yōu)先排序，搜集系統(tǒng)資源本身的限制（磁盤(pán)容量和時(shí)間限量）導(dǎo)致部分網(wǎng)頁(yè)直到搜集過(guò)程中止都沒(méi)有被搜集，出現(xiàn) 情況 11。 身處于不斷的膨脹過(guò)程之中，大量新出現(xiàn)的網(wǎng)頁(yè)來(lái)不及搜集。搜集系統(tǒng)自身一般都有搜集周期，而某些網(wǎng)頁(yè)（如實(shí)時(shí)新聞網(wǎng)頁(yè)）的更新頻率遠(yuǎn)大于搜集頻率。 從廣義的角度而言，凡是 的信息都應(yīng)該被搜集，而現(xiàn)在的搜索引擎一般只搜集了部分格式的網(wǎng)頁(yè)信息。當(dāng)前搜集的一般都是靜態(tài)網(wǎng)頁(yè)中類似于檔的信息資源，沒(méi)有考慮到包括動(dòng)態(tài)網(wǎng)頁(yè)在內(nèi)的巨量深層網(wǎng)絡(luò)文檔。據(jù)估計(jì)，當(dāng)前 的所有網(wǎng)頁(yè)（包括深層網(wǎng)頁(yè)）約有 5500 億之多，搜索引擎所覆蓋的不到其百分之一 12！ 因此，可以肯定任何一個(gè)實(shí) 際運(yùn)行的網(wǎng)頁(yè)搜集系統(tǒng)都不可能將當(dāng)前 的所有網(wǎng)頁(yè)全部抓盡。這種搜集性能越優(yōu)異，意味著它所獲得網(wǎng)頁(yè)集合在數(shù)量和質(zhì)量上越接近于實(shí)際的 頁(yè)之間的鏈接關(guān)系也越逼近實(shí)際的 向圖結(jié)構(gòu)。搜索引擎的信息覆蓋率正是對(duì)這種接近程度的衡量，它體現(xiàn)了一個(gè)網(wǎng)頁(yè)搜集系統(tǒng)所獲得的網(wǎng)頁(yè)集合及鏈接關(guān)系所占實(shí)際 比例。 類重要的覆蓋率 廣義的信息資源，應(yīng)該定義為互聯(lián)網(wǎng)上的一切信息，即所有存在于 的文檔。這些文檔有些能通過(guò)瀏覽器瀏覽，有些則不能；有些存在于網(wǎng)站的數(shù)據(jù)庫(kù)中，經(jīng)過(guò)動(dòng)態(tài)的請(qǐng)求方能生成，有些則是靜態(tài)存在的 且被其它網(wǎng)頁(yè)鏈接到。搜索引擎當(dāng)前所能搜集的絕大多數(shù)就是這種靜態(tài)的網(wǎng)頁(yè)，且在處理過(guò)程中進(jìn)一步過(guò)濾掉了某些不可瀏覽的部分如可執(zhí)行文件等。在這里，我們所研究的搜集系統(tǒng)覆蓋目標(biāo)是 的所有靜態(tài)網(wǎng)頁(yè)，它們通?？赏ㄟ^(guò)瀏覽器顯示內(nèi)容，且其 般靜態(tài)存在于其它網(wǎng)頁(yè)中。我們可以從多個(gè)角度來(lái)考慮搜索引擎對(duì) 息資源的覆蓋程度。 搜集系統(tǒng)應(yīng)該力圖遍歷 所有網(wǎng)頁(yè)，在數(shù)量這一角度上達(dá)到完全覆蓋的程度。這提供一個(gè)衡量搜集系統(tǒng)覆蓋 息能力的全局標(biāo)準(zhǔn)。例如當(dāng)前 的網(wǎng)頁(yè)估計(jì)約為 2,500,000,000 個(gè) 2 ， 統(tǒng)的網(wǎng)頁(yè)搜集數(shù)量是 2,073,418,204 個(gè) 6 ，因此可以估計(jì)其數(shù)量覆蓋率為百分之八十左右。如果系統(tǒng)的數(shù)量覆蓋率足夠高，我們就可以認(rèn)為它基本上覆蓋了 的所有信息資源。高的數(shù)量覆蓋率應(yīng)該是任何一個(gè)搜集系統(tǒng)及以此為基礎(chǔ)的網(wǎng)上信息博物館的首要目標(biāo)。 網(wǎng)上信息資源極為豐富，但也存在不少冗余，大量的廣告頁(yè)面和內(nèi)容重復(fù)頁(yè)面便是北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 4 此例。即使去除這些冗余后，用戶感興趣的網(wǎng)頁(yè)通常也只是數(shù)以十億計(jì)的數(shù)量中的極少數(shù)。因此，考慮搜集系統(tǒng)在質(zhì)量上對(duì) 頁(yè)的覆蓋程度顯得尤為重要。這一指標(biāo)可以告訴我們，對(duì) 那些用戶會(huì)感興趣的重要的網(wǎng)頁(yè)，系統(tǒng)覆蓋了其中的百分之幾。從更深的層次來(lái)說(shuō)，如果搜集系統(tǒng)覆蓋了絕大多數(shù)的“重要”網(wǎng)頁(yè)，它也就覆蓋了當(dāng)前社會(huì)信息在每一個(gè)重要主題上映射到 的部分，成為它的一個(gè)有效特征子集。類似于系統(tǒng)如果將這些重要網(wǎng)頁(yè)全部記錄下來(lái)，以后就能通過(guò)歷史網(wǎng)頁(yè)回放來(lái)重現(xiàn)人類社會(huì)信息資源在時(shí)間和空間兩維上的每一個(gè)角落。 從信息的表現(xiàn)形式來(lái)看，搜集系統(tǒng)當(dāng)前存儲(chǔ)的信息中相當(dāng)一部分日后將是不可見(jiàn)的。這一方面是由于存儲(chǔ)系統(tǒng)的資源所限，未能搜集類似于圖片影音之類的大文檔；另一方面是因?yàn)樗?集技術(shù)的不成熟，無(wú)法獲得類似于 格式的網(wǎng)頁(yè)。因此，考察搜集系統(tǒng)對(duì)可視網(wǎng)上信息資源的覆蓋率，也有著積極的意義。它可以告訴我們當(dāng)前所搜集到的網(wǎng)頁(yè)當(dāng)中，多大比例的一部分能夠在若干年后通過(guò)瀏覽器重新瀏覽。 在本文的研究中，將對(duì)前面的兩種進(jìn)行詳細(xì)的討論和量化分析。 息覆蓋率評(píng)測(cè)模型 我們定義搜集系統(tǒng)的信息覆蓋率為它所收集的網(wǎng)頁(yè)集合在 所占的比例?？紤]到 鏈接結(jié)構(gòu)，將其視為一張有向圖 G=（ V ， E），則搜集系統(tǒng)所獲得的網(wǎng)頁(yè)集合是 G 的強(qiáng)連通子圖？（不一定是強(qiáng)連通圖） G=（ V， E），每一個(gè)頂點(diǎn)都有唯一的標(biāo)記 信息覆蓋率的表達(dá)式為： C=| | G的相關(guān)屬性在搜集過(guò)程中已得到，但是因?yàn)樗阉饕嫠鸭W(wǎng)頁(yè)的不完全性， G 的相關(guān)屬性卻只能去估計(jì)。為了得到準(zhǔn)確的信息覆蓋率數(shù)據(jù)，我們采取對(duì) 樣的方法，即采取隨機(jī)的方式從中獲得一張子圖0G=（ 考察 V中的頂點(diǎn)落在 0的比例 的近似值。如果0 則 。此時(shí)的 我們可以用類似的思想去計(jì)算搜集系統(tǒng)的質(zhì)量覆蓋率。考慮 的所有重要網(wǎng)頁(yè)構(gòu)成的連通子圖 們可以用隨機(jī)的辦法獲得某些重要網(wǎng)頁(yè)組成的集合 S 作為樣本，來(lái)考察搜集系統(tǒng)覆蓋 S 中的子集 為近似的質(zhì)量覆蓋率此質(zhì)量覆蓋率的表達(dá)式為：（為什么用雙豎線？） |S| | 0S 因此，我們需要通過(guò)對(duì) 機(jī)取樣獲得網(wǎng)頁(yè)樣本；需要采取某些方法得到隨機(jī)的重要網(wǎng)頁(yè)集合，這通常要利用網(wǎng)頁(yè)之間的鏈接關(guān)系來(lái)對(duì)網(wǎng) 頁(yè)進(jìn)行權(quán)值估算；在得到網(wǎng)頁(yè)樣本之后，再檢查搜集系統(tǒng)的網(wǎng)頁(yè)覆蓋其中的比例，在檢查過(guò)程中，必須對(duì)網(wǎng)頁(yè)過(guò)濾，扔掉無(wú)法連接到的網(wǎng)頁(yè)。總體的工作流程大致如下圖所示： 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 5 3 數(shù)量覆蓋率 我們可以從不同的角度來(lái)對(duì) 進(jìn)行采樣。如果不考慮頂點(diǎn)之間的鏈接關(guān)系，僅從頂點(diǎn)的標(biāo)記 對(duì)應(yīng)的 址出發(fā)，可以采取隨機(jī)產(chǎn)生 方法來(lái)獲得一個(gè)網(wǎng)頁(yè)集合，從而得到樣本，這種考慮基于全局的視點(diǎn)；如果考慮到頂點(diǎn)之間的鏈接關(guān)系，則可以模仿搜索引擎搜集系統(tǒng)的工作方式，采取絕對(duì)廣度優(yōu)先的辦法，從某一個(gè)頂點(diǎn)（種子 發(fā)，逐漸擴(kuò)展遍歷，得到 一個(gè)網(wǎng)頁(yè)集合作為樣本，這是一種從局部來(lái)進(jìn)行取樣的辦法。 機(jī) 在 和 工作 13中，他們提出了通過(guò)隨機(jī)產(chǎn)生 行取樣的方法。首先獲得 已經(jīng)分配使用的所有 址，假設(shè)共有 M 個(gè)?？梢岳?分段將它們一一映射到 0 到 間的某個(gè)整數(shù)作為唯一標(biāo)記。這樣，我們可以利用隨機(jī)算法產(chǎn)生小于 M 的整數(shù)，得到一個(gè) 記集合，再逆映射回到 址，即得到一組隨機(jī) 本。如果搜集系統(tǒng)以域名標(biāo)志網(wǎng)站地址，還需要將其轉(zhuǎn)換為域名。這種取樣原理如圖 3 所示： 樣 我們?cè)谘芯抗ぷ髦蝎@得了中國(guó)國(guó)內(nèi)已分配的所有 址分段 4322 個(gè)， 其中一個(gè)分段，被分配給北京大學(xué)使用。如果統(tǒng)一用點(diǎn)北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 6 分十進(jìn)制表示所有網(wǎng)絡(luò)地址，則所有的 段可以表示如下 12 n其中， 為 0 到 255 之間的整數(shù)?？梢?jiàn)這些分段不相交，統(tǒng)計(jì)出每一個(gè)分段中的 址數(shù)量 則可以找到一一映射 F 使得 址 t）的函數(shù)值為： F(10（ * 3256 +(* 2256 + (*256 + (于是我們將每一個(gè) 對(duì)應(yīng)到一個(gè)整數(shù)，便可以用隨機(jī)算法在其中選取若干，逆映射 轉(zhuǎn)變?yōu)?址，便得到一個(gè) 址集合。去掉此集合中不提供 務(wù)（包括與網(wǎng)絡(luò)無(wú)連接）的元素，就得到了一個(gè)網(wǎng)站樣本。由于大約 14的網(wǎng)站通過(guò) 80 端口提供 務(wù)，我們可以順次掃描這些網(wǎng)絡(luò)地址上的 80 端口。得到的存在 務(wù)的址集合經(jīng)反向域名解析便可得到樣本 合。 通過(guò)對(duì)中國(guó)國(guó)內(nèi)的 行隨機(jī)取樣并進(jìn)行掃描，我們得到了如下結(jié)果： 編號(hào) 1 2 3 4 5 6 7 8 9 10 隨機(jī) 100K 200K 300K 400K 500K 600K 700K 800K 900K 1M 存在 95 172 252 336 418 478 570 652 717 817 表格中間線太粗，而且第三條應(yīng)該是不可見(jiàn)的 在上面的統(tǒng)計(jì)中，我們選取了多組不同數(shù)量的隨機(jī) 到的存在 務(wù)的 明選出的 址具有很好的隨機(jī)性。 證 由于搜集系統(tǒng)一般以包含域名的 記錄網(wǎng)頁(yè)，我們要檢驗(yàn)這些網(wǎng)頁(yè)是否已被覆蓋，應(yīng)該將其轉(zhuǎn)化為相應(yīng)的域名。由于網(wǎng)絡(luò)中 務(wù)器提供的 向解析功能有限，而搜集系統(tǒng)在搜集過(guò)程中通常記錄了搜到的網(wǎng)頁(yè) 域名與 址的對(duì)應(yīng)關(guān)系，我們可以由此直接檢驗(yàn)被覆蓋的 址數(shù)量。 我們的目的是對(duì)所有的 址進(jìn)行建模，接下來(lái)的問(wèn)題應(yīng)該是該用多少數(shù)據(jù)才能滿足要求使得樣本有效。盡管我們就這一問(wèn)題無(wú)法給出精確的數(shù)量，但是可以從少量的數(shù)據(jù)開(kāi)始，然后逐步增加數(shù)據(jù)量。如果我們這種通過(guò)隨機(jī)產(chǎn)生 樣的辦法是正確的，在原先樣本的基礎(chǔ)上逐步增加數(shù)據(jù)集將不會(huì)影響信息覆蓋率的結(jié)果。因此，我們可以對(duì)樣本容量從小到大的各組數(shù)據(jù)統(tǒng)計(jì)得到的覆蓋率進(jìn)行分析，看是否滿足以上條件。 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 7 下表是在各組隨機(jī) 址樣本中，被搜集系統(tǒng)覆蓋的 址所 占比例。 編號(hào) 1 2 3 4 5 6 7 8 9 10 存在 95 172 252 336 418 478 570 652 717 817 覆蓋 4 7 9 13 16 21 28 36 43 47 可以通過(guò)最小二乘法對(duì)結(jié)果進(jìn)行線性擬合，得到以下的二維圖像。其中，橫軸代表隨機(jī) 址樣本容量，縱軸代表搜集系統(tǒng)覆蓋樣本的數(shù)量，直線的斜率則表示信息覆蓋率。從圖中可知，自變量和因變量之間存在很好的一次函數(shù)關(guān)系，右。由此可以推斷，當(dāng)樣本擴(kuò)展到所有的 址時(shí)， 覆蓋率將會(huì)保持在這個(gè)數(shù)量左右。 型修正和結(jié)果分析 隨機(jī) 產(chǎn)生了大量的隨機(jī) 址，用這種方法可以很好的對(duì) 的所有提供 務(wù)的 務(wù)器進(jìn)行取樣；隨著樣本容量的增加，樣本的精確性也會(huì)增加。但是，這種采樣方法存在一些不足，導(dǎo)致信息覆蓋率具有較大偏差。 首先， 址標(biāo)記的是 務(wù)器的網(wǎng)絡(luò)地址，在大多數(shù)情況下，它等同于該服務(wù)器上運(yùn)行的網(wǎng)站首頁(yè)。這使得我們最終得到的網(wǎng)頁(yè)集合實(shí)際上是 網(wǎng)站首頁(yè)的一個(gè)樣本。使用 址將使得我們對(duì)所有的網(wǎng)站一視同仁，忽 略了網(wǎng)站的大小之別。一個(gè)只有三五個(gè)網(wǎng)頁(yè)的個(gè)人小網(wǎng)站（ 如 ）和一個(gè)有著上千網(wǎng)頁(yè)的大商業(yè)網(wǎng)站（ 如 ，為 ）是不等同的，然而這種區(qū)別在隨機(jī) 址取樣中無(wú)法體現(xiàn)。 另外，大量存在 務(wù)的服務(wù)器并非是實(shí)際意義上的網(wǎng)站。大多數(shù) 列操作系統(tǒng)自帶的 務(wù)器軟件， 統(tǒng)自帶安裝的 件，如此眾多，都會(huì)在缺省條件下提供 務(wù)，而這些“網(wǎng)站首頁(yè)”是沒(méi)有實(shí)際意義的測(cè)試網(wǎng)頁(yè)。類似的，也有大量的在某個(gè) 址短暫出現(xiàn)的網(wǎng)頁(yè)（例如臨時(shí)通過(guò) 務(wù)共享文件等等）。北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 8 在上述隨機(jī) 樣方法中，這些基本無(wú)效的網(wǎng)頁(yè)都被簡(jiǎn)單的等同于重要網(wǎng)站首頁(yè)加入了樣本之中。 因此，我們有必要對(duì)此模型作出修正。既要利用隨機(jī) 法具有的優(yōu)異的隨機(jī)性和全局性，又要保證通 過(guò)隨機(jī) 址獲得的網(wǎng)頁(yè)的有效性。解決辦法是利用網(wǎng)頁(yè)之間的鏈接關(guān)系，不再將各個(gè)網(wǎng)頁(yè)看作獨(dú)立的點(diǎn)，通過(guò)發(fā)現(xiàn)網(wǎng)頁(yè)中的 進(jìn)行適當(dāng)擴(kuò)展。我們?cè)谘芯恐袑⒌玫降乃须S機(jī) 址視為基本集合 R ，通過(guò) 議取得這些 取出其中的鏈接，加入 R，作為 頁(yè)樣本，如下圖所示： 為了將無(wú)效網(wǎng)頁(yè)的影響降至最低，還可以對(duì)鏈接作多級(jí)擴(kuò)展。經(jīng)過(guò)這種處理后，上述第一種情況可以得到修正，因?yàn)榇缶W(wǎng)站的首頁(yè)通常存在較大的出度；第二種情況中默認(rèn)網(wǎng)頁(yè)鏈出的網(wǎng)頁(yè)一般指向該軟件生產(chǎn)廠家的首頁(yè)，頁(yè)面相同且數(shù) 量少，且因其通常在國(guó)外故可在研究 過(guò)濾掉。我們從上述的隨機(jī)樣本中抽取了 5 組，經(jīng)過(guò)擴(kuò)展以后的網(wǎng)頁(yè)樣本數(shù)量以及覆蓋數(shù)量如下： 編號(hào) 1 3 5 7 10 存在 95 252 418 570 817 擴(kuò)展樣本容量 1084 2584 3859 5484 8094 覆蓋 174 596 841 1204 1899 在驗(yàn)證的過(guò)程中，我們將用 址表示的 化成域名 便搜集系統(tǒng)的驗(yàn)證。這種轉(zhuǎn)換經(jīng)過(guò)了兩級(jí)反向解析，第一步是通過(guò)網(wǎng)上 務(wù)器的解析，第二步 是通過(guò)搜集系統(tǒng)保存的域名與 應(yīng)數(shù)據(jù)。對(duì)得到的結(jié)果作線性擬合，得到的圖幾（沒(méi)有標(biāo)）如下，從擬合結(jié)果可得到信息覆蓋率約為 可見(jiàn)，在對(duì)模型作修正之后，覆蓋率有很大的增幅；如果考慮到域名與 間的動(dòng)態(tài)關(guān)系（即大量域名的 可變的， 統(tǒng)每隔幾分鐘更新一次），我們?nèi)コ魳颖局幸?示的 量覆蓋率數(shù)據(jù)將還會(huì)有小幅度的提高，這才是真正的數(shù)量覆蓋率大小。 通過(guò)隨機(jī) 產(chǎn)生的網(wǎng)頁(yè)樣本很好的考察了搜集系統(tǒng)對(duì) 向圖某些入度為 0或是從出發(fā)頂點(diǎn)無(wú)法達(dá)到頂點(diǎn)的覆蓋情況。這啟示我們?cè)谒鸭W(wǎng)頁(yè)過(guò)程 中，選取適當(dāng)數(shù)量的以隨機(jī) 產(chǎn)生的 為起始頂點(diǎn)集合的一部分，能提高搜集系統(tǒng)的數(shù)量信息北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 9 覆蓋率和 網(wǎng)頁(yè)信息的有效性。 度優(yōu)先法 隨機(jī) 雖然具有較好的隨機(jī)性和全局性，但在使用過(guò)程中發(fā)現(xiàn)許多有待改進(jìn)之處；為了使對(duì) 取樣在邏輯結(jié)構(gòu)上與實(shí)際情況更加接近，考慮到對(duì)隨機(jī) 作修正時(shí)對(duì)邏輯鏈接關(guān)系的利用，我們提出了絕對(duì)廣度優(yōu)先搜集取樣的辦法。這種方法實(shí)現(xiàn)的實(shí)際就是一個(gè)最原始的搜集系統(tǒng)的工作過(guò)程，只是在搜集過(guò)程中按照絕對(duì)廣度優(yōu)先的方式一級(jí)級(jí)的擴(kuò)展開(kāi)去。這種取樣是從局部的角度來(lái)進(jìn)行 的，原理如下圖所示。 樣 我們選取了五個(gè) 為起始點(diǎn)，采取上述絕對(duì)廣度優(yōu)先搜集網(wǎng)頁(yè)的辦法分別獲得五組 頁(yè)樣本，樣本容量從幾萬(wàn)到數(shù)十萬(wàn)不等。算法如下： （ 1）選取某個(gè)網(wǎng)頁(yè) S 作為起始 （ 2）創(chuàng)建隊(duì)列 Q 存儲(chǔ)未搜集的網(wǎng)頁(yè)， S 入隊(duì)列；創(chuàng)建結(jié)構(gòu)數(shù)組 A 存儲(chǔ)已經(jīng)搜集過(guò)的網(wǎng)頁(yè)，按照 符串排序； （ 3）取得隊(duì)列頭元素，通過(guò) 議獲取 H 的源文件，提取出其中包含的的全部 接，并記錄鏈接關(guān)系； 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 10 （ 4）在 A 中用二分法尋找（ 3）中得到的 否已被搜集，如果沒(méi)有搜集，則使其進(jìn)入 隊(duì)列 Q； （ 5）判斷 A 中的網(wǎng)頁(yè)數(shù)量是否已達(dá)到要求，若沒(méi)有繼續(xù)（ 3）。 得到的結(jié)果列表如下： 樣本編組 1 2 3 4 5 種子 展 66891 211629 154314 723866 174078 證和分析 得到網(wǎng)頁(yè)樣本之后，我們可以在 網(wǎng)頁(yè)數(shù)據(jù)庫(kù)中驗(yàn)證被覆蓋的比例。為了快速的檢驗(yàn)數(shù)據(jù)，達(dá)到磁盤(pán)性能的極限，我們啟動(dòng)了數(shù)百個(gè)進(jìn)程從 表中讀取并通過(guò) 法從庫(kù)中查找。得到的覆蓋率數(shù)據(jù)如下表所示。 對(duì)于這組離散的覆蓋率值，我們 計(jì)算均值和方差分別為 者即為通過(guò)絕對(duì)廣度優(yōu)先法得到的數(shù)量覆蓋率。 樣本編組 1 2 3 4 5 擴(kuò)展 66891 211629 154314 723866 174078 覆蓋數(shù)量 26732 87562 67178 273066 74370 數(shù)量覆蓋率 對(duì)于使用這種采樣方法得到的數(shù)量覆蓋率 較之采用隨機(jī) 具有較高的覆蓋率值是可以理解的。因?yàn)檫@兩批數(shù)據(jù)是從兩個(gè)不同的方面說(shuō)明搜集系統(tǒng)的信息覆蓋 情況：隨機(jī) 著眼于全局，而絕對(duì)廣度優(yōu)先法著眼于局部，更類似于搜索引擎的搜集過(guò)程。 通常搜集系統(tǒng)是在 的最大連通子圖內(nèi)遍歷，絕對(duì)廣度優(yōu)先法恰好反映了搜集系統(tǒng)對(duì)這一最大連通子圖的覆蓋比例。由于這一最大連通子圖占據(jù)了 90%10左右的網(wǎng)頁(yè)，而且我們選取的起始 落在這一子圖之內(nèi)，故絕對(duì)廣度優(yōu)先法得到的結(jié)論應(yīng)該修正為乘以 90%這一參數(shù)才能在全局角度上反映搜集系統(tǒng)的覆蓋率，因此準(zhǔn)確的數(shù)量覆蓋率應(yīng)該是 當(dāng)樣本容量越大 ,覆蓋率就應(yīng)該約逼近此值 ,這從我們采用的大容量樣本 (第 4 組 )結(jié)果中已經(jīng) 得到了驗(yàn)證。 隨機(jī) 反映的是搜集系統(tǒng)對(duì) 所有點(diǎn)的覆蓋情況，因此這種采樣更容易采集到入度為 0 或由于其他原因?qū)е滤鸭到y(tǒng)無(wú)法遍歷到的網(wǎng)頁(yè)（稱為不可到達(dá)網(wǎng)頁(yè)）。由于不可到達(dá)網(wǎng)頁(yè)中大量的點(diǎn)是孤立點(diǎn)，在沒(méi)有很好的區(qū)分這些 址上所存在的網(wǎng)頁(yè)數(shù)據(jù)量的情況下，這種樣本需要經(jīng)過(guò)多級(jí)鏈接擴(kuò)展才能全面的反映真實(shí)的 就是說(shuō)，如果對(duì)初始 斷作鏈接擴(kuò)展，最后的數(shù)據(jù)會(huì)不斷接近 這在我們作第北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 11 一級(jí)擴(kuò)展之后已經(jīng)有了好的反映。 我們可以預(yù)測(cè)到，如果將兩種采樣方法的優(yōu)點(diǎn)結(jié)合起來(lái)，通過(guò)隨機(jī) 產(chǎn)生 絕對(duì)廣度優(yōu)先法取樣的種子集合再進(jìn)行擴(kuò)展，在樣本容量足夠大之后，最后的數(shù)量覆蓋率數(shù)據(jù)應(yīng)該與通過(guò)文獻(xiàn) 10 的工作做的估計(jì)相符，在 近。 4 質(zhì)量覆蓋率 考察搜集系統(tǒng)在質(zhì)量上對(duì) 信息覆蓋率，需要通過(guò)有效的網(wǎng)頁(yè)重要性評(píng)測(cè)方法找到一組重要網(wǎng)頁(yè)樣本。盡管通?？梢酝ㄟ^(guò)用戶評(píng)選提交的方式得到他們?cè)跒g覽網(wǎng)頁(yè)過(guò)程中發(fā)現(xiàn)的重要網(wǎng)頁(yè)集合作為樣本，但在本文研究中，為了保證樣本的隨機(jī)性和客觀性，我們采用兩類基于對(duì) 接結(jié)構(gòu)的分析而對(duì) 重要網(wǎng)頁(yè)進(jìn)行取樣的有效方法。 這些方法的基本思想都是找到一組具有較強(qiáng)鏈接關(guān) 系的網(wǎng)頁(yè)（初始取樣），通過(guò)基于鏈接分析的網(wǎng)頁(yè)權(quán)值算法，求出其中所有網(wǎng)頁(yè)的相對(duì)重要性值，從而可以對(duì)網(wǎng)頁(yè)進(jìn)行排序取出前若干位作為重要網(wǎng)頁(yè)的樣本。這些經(jīng)典的權(quán)值算法包括斯坦福大學(xué)開(kāi)發(fā) 法 15和 究院開(kāi)發(fā) 統(tǒng)提出的 法 16 （ 它們都是基于對(duì) 向圖鏈接結(jié)構(gòu)的理解提出的。 頁(yè)重要性評(píng)測(cè)方法 的信息資源數(shù)量如此之大，無(wú)論是搜集系統(tǒng)本身還是接受返回結(jié)果的查詢用戶，都要求有好的方法對(duì)網(wǎng)頁(yè)集合按照重要性進(jìn)行排序，因?yàn)橄到y(tǒng)搜集的和用戶關(guān)心的一般都只是其中的某一子集。準(zhǔn)確的辨別出重要的網(wǎng)頁(yè)加以優(yōu)先搜集，準(zhǔn)確的計(jì)算出重要的網(wǎng)頁(yè)返回給用戶優(yōu)先瀏覽，要做到這些，我們需要合適的網(wǎng)頁(yè)重要性評(píng)定方法。這里，網(wǎng)頁(yè)的重要性用權(quán)值來(lái)衡量，權(quán)值越高表示網(wǎng)頁(yè)越重要。 我們可以從三個(gè)角度來(lái)分析網(wǎng)頁(yè)的權(quán)值，討論它的相關(guān)因素。 從網(wǎng)頁(yè)本身的唯一屬性 發(fā)來(lái)考慮：網(wǎng)頁(yè)的權(quán)值可以從 屬性中得到反映。一般而言， 在 網(wǎng)站的域名越短，所在網(wǎng)站上相對(duì)于根目錄的層次越淺，網(wǎng)頁(yè)的權(quán)值越大。例如， 北京大學(xué)的網(wǎng)站首頁(yè) ；而 。這一原理可以在網(wǎng)頁(yè)搜集過(guò)程中加以利用。 從網(wǎng)頁(yè)作為 向圖的一個(gè)節(jié)點(diǎn)來(lái)考慮：網(wǎng)頁(yè)的權(quán)值可以根據(jù)它的認(rèn)可度來(lái)判斷，由于網(wǎng)頁(yè)間的鏈接通常代表著認(rèn)可度的傳遞，我們可以統(tǒng)計(jì)網(wǎng)頁(yè)的入度來(lái)評(píng)判其重要性。如果網(wǎng)頁(yè) A 上存在網(wǎng)頁(yè) B 的 除掉純粹導(dǎo) 航的因素，表示著網(wǎng)頁(yè) A 的作者存在對(duì)網(wǎng)頁(yè) B 的認(rèn)可；而這種認(rèn)可的增多則意味著網(wǎng)頁(yè) B 權(quán)值的上升。因此，入度越大，權(quán)值通常越高。 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 12 從網(wǎng)頁(yè)本身的內(nèi)容出發(fā)來(lái)考慮：在搜索引擎搜集網(wǎng)頁(yè)的過(guò)程中，通常都要保存網(wǎng)頁(yè)的關(guān)鍵詞或全文信息，以便建立索引。由于網(wǎng)頁(yè)的重要性一般又對(duì)應(yīng)著用戶較高的關(guān)心程度，我們可以通過(guò)對(duì)用戶遞交給搜索引擎的查詢?cè)~與網(wǎng)頁(yè)的內(nèi)容（全文或關(guān)鍵詞）進(jìn)行匹配，匹配程度越高意味著網(wǎng)頁(yè)的權(quán)值越高。當(dāng)然，這要求用戶遞交的查詢是希望得到大量相關(guān)網(wǎng)頁(yè)的寬主題查詢。該情況在論文 18中有詳細(xì)討論。 當(dāng)前大 多數(shù)搜索引擎所采用的網(wǎng)頁(yè)權(quán)值計(jì)算方法正是上面提到的的 法和 法兩種，它們分別利用了上述中的后兩種原理，而且對(duì)其間的網(wǎng)頁(yè)鏈接關(guān)系作了更深層次的挖掘。 法 15是一種利用網(wǎng)頁(yè)間鏈接關(guān)系進(jìn)行權(quán)值計(jì)算的典型方法，它是學(xué)術(shù)論文引用統(tǒng)計(jì)原理在 的推廣，它統(tǒng)計(jì)每個(gè)網(wǎng)頁(yè)被引用的次數(shù)，但每一次引用又因引用者權(quán)值的不同而不同；而 法 17 將網(wǎng)頁(yè)的權(quán)值分為目錄型權(quán)值和權(quán)威型權(quán)值分別進(jìn)行計(jì)算，目錄型權(quán)值高表示它鏈向很多權(quán)威型權(quán)值高的網(wǎng)頁(yè)，而權(quán)威型權(quán)值高則表示它被很多目錄 型權(quán)值高的網(wǎng)頁(yè)所鏈接到。（目錄型、權(quán)威型沒(méi)有解釋） 基于這兩種權(quán)值算法，我們提出了下面的兩類質(zhì)量覆蓋率確定方法。 度優(yōu)先法 樣 法根據(jù)網(wǎng)頁(yè)間的鏈接關(guān)系來(lái)評(píng)判網(wǎng)頁(yè)的重要性，因此我們選取的初始網(wǎng)頁(yè)集合必須和 著大致相同的鏈接結(jié)構(gòu)，保證初始樣本中每個(gè)網(wǎng)頁(yè)的入度與實(shí)際互聯(lián)網(wǎng)絡(luò)相差不大，或者網(wǎng)頁(yè)入度的相對(duì)大小變化不大。這樣才能使得初始樣本中的相對(duì)網(wǎng)頁(yè)權(quán)值保持不變。 我們可以利用絕對(duì)廣度優(yōu)先的辦法，從初始 始向外遍歷。隨著初始樣本容量的加大，每個(gè)樣本網(wǎng)頁(yè)的入度越來(lái)越接近于它 在 的實(shí)際入度，樣本網(wǎng)頁(yè)的入度相對(duì)大小也越來(lái)越固定。我們以數(shù)量覆蓋率研究中的廣度優(yōu)先法所獲樣本作為初始樣本，它們的數(shù)量一般在數(shù)十萬(wàn)，已能基本保證其中相當(dāng)數(shù)量網(wǎng)頁(yè)的相對(duì)入度大小。用法從中計(jì)算選出權(quán)值在前 M 位的網(wǎng)頁(yè)集合作為樣本。顯然， M 值越小，樣本的有效性越容易得到保證。 法 假定網(wǎng)頁(yè) A 在 面被網(wǎng)頁(yè) 鏈到， C(A)表示從 A 鏈出去的網(wǎng)頁(yè)數(shù)量（即出度），則 A 的權(quán)值可以表示如下： )=)( 17 這種基本思想可以從下圖中體現(xiàn)： 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 13 考慮到用戶從 發(fā)只有 d（ 0的形式存入關(guān)系數(shù)據(jù)庫(kù)。當(dāng)網(wǎng)頁(yè)的數(shù)量足夠大時(shí)，所有的網(wǎng)頁(yè)及其鏈接屬性無(wú)法一次全部存入內(nèi)存中，故需要分塊對(duì)矩陣進(jìn)行迭代。 具體的實(shí)現(xiàn)算法如下： （ 1） 創(chuàng)建數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)網(wǎng)頁(yè)的整數(shù) 值、出度、入度以及所有鏈入網(wǎng)頁(yè)的此作為矢量 W 的單元； （ 2） 根據(jù)網(wǎng)頁(yè)的平均入度 2估計(jì)系統(tǒng)內(nèi)存一次能存放的 量 N，在我們的系統(tǒng)中，估計(jì)約為 1 （ 3） 從數(shù)據(jù)庫(kù)中導(dǎo)出 N 個(gè) 內(nèi)存，按 序；再將全部的鏈接關(guān)系導(dǎo)入，對(duì)于上述 N 中的每一個(gè)，填充進(jìn)它的鏈接屬性； （ 4） 對(duì)于 N 中的每一個(gè)，用二分法找到它的鏈入 數(shù)組下標(biāo)，如果不在當(dāng)前內(nèi)存中則其權(quán)值以平均值計(jì)算，運(yùn)用 法計(jì)算其權(quán)值； 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 14 （ 5） 如果全部的 已經(jīng)導(dǎo)入計(jì)算過(guò)，則對(duì)該矢量進(jìn)行處理使得所有 權(quán)值之和為 1；否則繼續(xù)（ 4）； （ 6） 如果先后兩次計(jì)算的 W 距離足夠小，則對(duì)權(quán)值排序選取前 M 個(gè)輸出到文件；否則繼續(xù)（ 3）。 （ 7） 將輸出文件中的所有 數(shù) 換為 符串。 實(shí)驗(yàn)在 統(tǒng)上運(yùn)行，主要硬件指標(biāo)是 1存 ， P 50 們以數(shù)量覆蓋率計(jì)算中得到的五組樣本作為初始樣本，如果選擇權(quán)值排序位于前面約 5%左右的網(wǎng)頁(yè)作為重要網(wǎng)頁(yè)的標(biāo)準(zhǔn)，得到了如下結(jié)果： 樣本編組 1 2 3 4 5 種子 始擴(kuò)展數(shù)量 66891 211629 154314 723866 174078 數(shù) 3523 8497 8702 33436 8408 占前百分之幾 覆蓋 1542 4032 4754 17717 3456 質(zhì)量覆蓋率 取前 M 個(gè) ,為什么每組 占前百分之幾不相同。 對(duì)五組樣本檢驗(yàn)得到的質(zhì)量覆蓋率計(jì)算均值和方差分別是 為了保證所求樣本網(wǎng)頁(yè)的重要性有效，我們選取了上述樣本中的第 2 組和第 4 組，改變判斷重要性的標(biāo)準(zhǔn)，質(zhì)量覆蓋率隨此而變化的情形如下表所示。 對(duì)于第二組網(wǎng)頁(yè)樣本： 重要網(wǎng)頁(yè)個(gè)數(shù) 1811 3434 5117 6808 8497 占前百分之幾 覆蓋網(wǎng)頁(yè)數(shù) 1145 2068 2788 3363 4032 質(zhì)量覆蓋率 下圖是隨著重要性標(biāo)準(zhǔn)的放松，質(zhì)量覆蓋率的變化情況： 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 15 對(duì)于第四組網(wǎng)頁(yè)樣本： 重要網(wǎng)頁(yè)個(gè)數(shù) 17321 33436 49198 64450 79155 占前百分之幾 覆蓋網(wǎng)頁(yè)數(shù) 9903 17717 24718 31126 36780 質(zhì)量覆蓋率 下圖是隨著重要性標(biāo)準(zhǔn)的放松，質(zhì)量覆 蓋率的變化情況： 從這兩張圖中可以看出，當(dāng)重要標(biāo)準(zhǔn)很苛刻時(shí)重要網(wǎng)頁(yè)樣本容量很小，此時(shí)搜集系統(tǒng)的覆蓋率很高；但隨著重要標(biāo)準(zhǔn)的放松導(dǎo)致樣本容量的增大，搜集系統(tǒng)的質(zhì)量覆蓋率會(huì)越來(lái)越低；當(dāng)重要性的標(biāo)準(zhǔn)放至最低，即所有網(wǎng)頁(yè)的地位平等時(shí)，質(zhì)量覆蓋率變?yōu)樽钚?，為?shù)量覆蓋率值。這兩張圖中都顯示，當(dāng)重要標(biāo)準(zhǔn)降至約 5%左右時(shí)，曲線開(kāi)始逐漸變得平緩，因此此點(diǎn)的覆蓋率數(shù)據(jù) 疑最適合作為我們所測(cè)的的搜集系統(tǒng)質(zhì)量覆蓋率。 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 16 題查詢法 網(wǎng)頁(yè)具有作為 向圖結(jié)構(gòu)中一個(gè)頂點(diǎn)的相關(guān)邏輯屬性，它又可根據(jù)其內(nèi)容本身而屬于人類社 會(huì)信息資源的某一主題類別。例如，網(wǎng)頁(yè)可以根據(jù)其內(nèi)容分為屬于社會(huì)、人文或休閑娛樂(lè)等類別以及它們的子類的網(wǎng)頁(yè)?；谶@一點(diǎn)的考慮，我們的研究工作中采取了通過(guò)主題查詢獲得 要網(wǎng)頁(yè)樣本的方法。這類似于文獻(xiàn) 19 的工作中 于 同一主題的網(wǎng)頁(yè)之間具有較強(qiáng)的鏈接關(guān)系 19，我們可用 法對(duì)此網(wǎng)頁(yè)集合進(jìn)行權(quán)值計(jì)算，進(jìn)行排序后得到前若干網(wǎng)頁(yè)作為 這一主題類別的重要網(wǎng)頁(yè)樣本。 樣 假設(shè)我們希望得到 于主題 T 的重要網(wǎng)頁(yè)樣本，我們一般會(huì)通過(guò)遞交 若干與T 相關(guān)的查詢?cè)~ Q 提交給搜索引擎，它返回的網(wǎng)頁(yè)集合為 R。對(duì)于通常的搜索引擎， 較高的相關(guān)度，因?yàn)椴樵冎型ǔＪ褂米址ヅ?，使得返回的網(wǎng)頁(yè)中大多含有 Q 之類的字樣。但是，也有大量的重要網(wǎng)頁(yè)不適合這種情況，例如天網(wǎng)系統(tǒng)的主頁(yè)并沒(méi)有搜索引擎的字樣供匹配。出于對(duì)這種特殊現(xiàn)象的考慮，需要對(duì) R 以適當(dāng)?shù)臄U(kuò)展，加入 R 網(wǎng)頁(yè)鏈出去的網(wǎng)頁(yè)和鏈向 R 元素的網(wǎng)頁(yè)得到初始樣本 S ，如圖示： 我們選擇了八個(gè)主題的查詢?cè)~遞交給天網(wǎng)搜索引擎，在用以上的方式對(duì)返回結(jié)果進(jìn)行擴(kuò)展之后，得到了八組初始網(wǎng)頁(yè)樣本如下： 樣本編 組 1 2 3 4 5 6 7 8 查詢?cè)~ 北京大學(xué) 考研 股票 江澤民 程 聯(lián)想集團(tuán) 三個(gè)代表 世界杯 返回?cái)?shù)量 1802 1802 1802 1802 1355 1802 1802 1802 擴(kuò)展數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 法 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 17 上圖中的 S 正是我們用 法進(jìn)行權(quán)值計(jì)算的對(duì)象。對(duì)于 S 中的任意一個(gè)元素P ，設(shè) H(P)表示其目錄型權(quán)值（ A(P)表示其權(quán)威型權(quán)值（ 2, ,鏈到 P 的網(wǎng)頁(yè)， 2, ,從 P 鏈出的網(wǎng)頁(yè)，則 A(P)和 H(P)可以從下面的式子計(jì)算： A(P)= H(P)= 同 法類似，我們可以將所有的網(wǎng)頁(yè)的目錄型權(quán)值看作矢量 H，將所有網(wǎng)頁(yè)的權(quán)威型權(quán)值看作矢量 A，設(shè)樣本中所有網(wǎng)頁(yè)及鏈接關(guān)系構(gòu)成的有向圖的鄰接矩陣為 M，考慮到兩個(gè) 間最多有一個(gè)鏈接使得若存在網(wǎng)頁(yè) i 到網(wǎng)頁(yè) j 的鏈接則 Mi,j=1否 則 Mi,j=0，那么上面的式子可以寫(xiě)成： A= H H=M A 由此兩式可得 A= M A，即實(shí)際上 A 是 M 的特征向量；同理 H 是M 特征向量，我們因此也可以用冪法或 法等來(lái)通過(guò)迭代來(lái)求得 A 和 H 的值。但考慮到系統(tǒng)內(nèi)存對(duì)初始樣本容量的限制，若數(shù)量很大的時(shí)候需要分塊對(duì)兩個(gè)矩陣進(jìn)行迭代。 驗(yàn)結(jié)果 在我們 的研究工作中，我們沒(méi)有通過(guò)計(jì)算特征向量而采取了根據(jù)前一組公式直接進(jìn)行迭代計(jì)算 A 和 H 值的辦法，具體的實(shí)現(xiàn)算法如下： （ 1） 采集初始樣本時(shí)將所有的 號(hào)存入數(shù)據(jù)庫(kù)，同時(shí)存入 間的鏈接關(guān)系； （ 2） 創(chuàng)建相關(guān)的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)每個(gè) 值及鏈接關(guān)系，從數(shù)據(jù)庫(kù)中導(dǎo)出所有 性并填充到數(shù)據(jù)結(jié)構(gòu)中； （ 3） 給予 H 和 A 某個(gè)初始值，分別計(jì)算 A（ i+1） = H（ i）和 H(i+1)=M A(i)，直至 A(i+1)和 A(i)的距離足夠小為止； （ 4） 分別對(duì) 進(jìn)行 冒泡排序，輸出前若干個(gè) 文件中。 在確定重要網(wǎng)頁(yè)的界限時(shí)，我們選取的是初始網(wǎng)頁(yè)樣本中權(quán)值排在前面約 15%左右的部分，大致與搜索引擎響應(yīng)查詢?cè)~返回的網(wǎng)頁(yè)數(shù)量相當(dāng)。即搜索引擎就此主題返回 們經(jīng)過(guò)計(jì)算后也給出 X 個(gè)“真正”重要的網(wǎng)頁(yè)，檢查搜集系統(tǒng)覆蓋其中的比例作為質(zhì)量覆蓋率。 對(duì)于具有較高 值的重要網(wǎng)頁(yè)，實(shí)驗(yàn)的數(shù)據(jù)如下： 樣本編組 1 2 3 4 5 6 7 8 北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室 孟濤學(xué)士論文 18 查詢?cè)~ 北京大學(xué) 考研 股票 江澤民 程 聯(lián)想集團(tuán) 三個(gè)代表 世界杯 初始數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 數(shù) 1671 1701 1532 1040 1508 1428 1859 1961 覆蓋數(shù)量 958 956 578 312 772 514 793 651 覆蓋率 30% 八組樣本所得的質(zhì)量覆蓋率分別為表幾所示，它們的均值和方差分別為 者即為搜集系統(tǒng)對(duì) 重要網(wǎng)頁(yè)的覆蓋率。 對(duì)于具有較高 值的重要網(wǎng)頁(yè)，實(shí) 驗(yàn)的數(shù)據(jù)如下： 樣本編組 1 2 3 4 5 6 7 8 查詢?cè)~ 北京大學(xué) 考研 股票 江澤民 程 聯(lián)想集團(tuán) 三個(gè)代表 世界杯 初始數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 數(shù) 1400 1572