1、PAGE PAGE 17超鏈接環境(hunjng)下的權威資源(zyun)1 引言(ynyn)超鏈接的網絡結構是一個有豐富資源的環境內容信息，它提供給我們一個有效的方法讓我們去理解它。在這種情況下，我們針對這種環境下的鏈接結構開發了一系列的算法工具從中分離信息，并通過在試驗中報告和說明它們在萬維網中的多種多樣內容中的有效作用。我們尤其關注它在一個廣闊的搜索主題中分析和搜集相關網頁以及發現最權威網頁時鏈接的使用。對于萬維網，當我們不缺乏技術的時候，我們發現搜索和結構分析的問題在區域上下文中尤其重要。萬維網是一個巨大而復雜的超文本資料庫，它同時在以驚人的速度持續擴展著。更甚者，它可以看做一個錯綜復

2、雜的超媒體結構。它同時有數以百萬計的在線參與者，這些參與者們有著多種多樣互相沖突的目標，同時他們還在不斷的創造超鏈接內容。所以，當每個人都在以一種極端的本地層次強制整理信息時，全局的組織已經完全的改變了上層的結構只能通過之后的分析才能浮現出來。我們的工作就是源于萬維網上的搜索問題。我們可以粗糙的定義為一個過程給出查詢，提供相關的網頁。由于相關性是主觀存在的，所以搜索方法的質量需要人類來評估。我們是從觀察萬維網上提高搜索方法的質量開始的。在現階段，一個豐富而有趣的問題是在很多方式中，它們算法的有效性和存儲性是互不相關的。尤其是現在的搜索引擎都是典型的只搜索萬維網上的一定大小的內容的搜索引擎，同時

3、響應還是秒級別的。盡管可以提高響應時間來換取對于用戶來說更重要的結果，但是對于搜索工具來說，用額外的時間來進行計算，這是非常不可行的。準確的說，我們缺乏一種具體定義的功能，這種功能客觀上應滿足我們想要搜索到的頁面的質量。查詢和權威資源。我們認為搜索是開始于用戶提供的查詢的。它不需要查詢的統一概念性的視圖；且它不止是一種查詢，它需要運用不同的技術來處理。思考一下，比如說，有下面幾種查詢：特定查詢，如“網景是否支持JDK 1.1代碼簽名的API（應用程序接口）？”廣泛主題(zht)查詢，如“找到關于(guny)JAVA編程語言的信息”相似(xin s)頁面查詢，如“找到與相似的頁面”我們現在專注前

4、兩種類型的查詢，我們可以看到它們現在又很多不同種類的障礙。處理特定查詢時的困難是集中的，粗略地說，是圍繞所說的稀缺問題的。有極少的頁面包含這些所需的信息，并且通常很難確定這些頁面的真正來源。對于廣泛主題查詢，另一方面，我們期待在萬維網上找到數以千計的相關頁面。這樣的一組頁面可能通過標引項匹配（如輸入一個字符串“Gates”，“search engines”，“censorship”到搜索引擎AltaVista17），或者更復雜的方式產生。因此，這并不是一個稀缺問題，相反，其基本困難在于豐度問題：可以作為相關頁面合理地返回的頁面數目太大，以至于人們很難消化。在這些條件下，為了提供有效的搜索方法，

5、就需要一種方法，從巨大的相關網頁集合中篩選出最“權威”或“徹底”的那些。我們對于廣泛主題的查詢，可以將權威這一概念，作為我們工作中的中心焦點。我們在處理這一問題所面臨的基本障礙之一是準確地模型化在特定的查詢主題上下文中的權威網頁。鑒于某一網頁，我們如何辨別其權威？討論一些在這里出現的復雜難懂的問題是很有用的。首先，考慮報告的自然目標，即哈佛大學主頁為查詢“哈佛”的最權威頁面之一。不幸的是，在萬維網上有超過 100 萬的網頁使用了目標詞 “Harvard”。同時 不是最常使用的，或者使用最突出的，或者以任何其他方式支持一種基于文本的排序函數。事實上，一個疑問是，是否存在一個純粹的內源性措施去適當

6、地評估一個頁面的權威。第二個問題是找到主要的www 搜索引擎的主頁。我們可以從查詢“搜索引擎”開始，但是這存在一個困難，事實上很多權威網站（雅虎，Excite，AltaVista） 都沒有在其頁面上使用這個詞。這是一個基本的和重復出現的現象 另一個例子，我們就沒有理由指望本田或豐田的主頁包含術語“汽車制造商”。鏈接結構分析。萬維網的網頁之間的超鏈接結構分析，給了我們一個方式來處理許多上文討論過的困難。超鏈接隱含了大量潛在的人為判斷，我們認為這種類型的判斷正是我們制定一個權威的概念所需要的。具體來說，萬維網上鏈接的建立是以下判斷類型的具體表現：頁 p，通過包括頁面 q的鏈接，就可以在在某種程度上

7、賦予 頁面q 的權威性。此外，鏈接通過指向它們頁面，讓我們完全有機會找到潛在的權威性的東西 ；針對很多突出的頁面沒有充足地自我描述的網頁，這種方式圍繞著以上的問題提供了一種方法。當然(dngrn)，這種情況下，有大量的鏈接(lin ji)的應用程序(chngx)中有很多的潛在缺陷。首先，針對各種各樣的原因創建的鏈接，其中有很多與權威性無關。例如，主要用于導航目的而創建大量的鏈接（ “點擊此處返回到主菜單”） ；其他表示的付費的廣告。另一個問題是很難找到相關性和流行性標準之間的適當的平衡，而這兩個都有助于權威這個直覺概念的判斷。這對在下面這個簡單的啟發式算法定位權威頁面所固有的嚴重問題的思考具有

8、指導性作用：包含查詢字符串的所有頁，都返回導入鏈接的最大數目。我們之前已經討論的許多查詢 （搜索引擎、汽車制造商，)，其中的一些查詢的最權威頁面不包含相關的查詢字符串。反之，這啟發式算法會考慮普遍受歡迎的網頁，如 或 所包含的任何查詢字符串，它極具權威性。在這項工作中，我們針對權威的授予，提出了一個基于鏈接的模型，并提出它是如何統一標識與廣泛搜索主題相關的、 權威的 www 頁面的方法。我們的模型基于權威性的主題與這些權威性頁面所鏈接到的許多有關權威性頁面之間所存在的關系我們把后面的這一種類型的頁面叫做樞紐。我們觀察到樞紐和由鏈接結構定義在圖中權值之間存在的某種自然的平衡，我們利用這一點開發算

9、法，能同時識別兩種類型的頁面。這種算法操作于我們構建的基于文本的 www 搜索引擎輸出中的子圖 ；我們構建這些子圖的技術是設計產生一個小的可能包含一個給定的主題最權威頁面集合。概述(i sh)。我們(w men)發現權威萬維網資源(zyun)的方法必須要具有全球性質： 我們希望確定萬維網中廣泛搜索主題的最中央頁作為一個整體。全局辦法涉及到了表示和過濾大容量的信息的基本問題，因為所有的與主題有關的廣泛主題查詢的頁面有數以百萬計。這與查詢本地的方法不同，理解萬維網中的頁面的相互連接屬于單個邏輯站點或內聯網； 在這種情況下，本地方法數據量小得多，經常考慮不同組的主導地位。注意到我們主要關心的這個是一

10、個從根本上與聚類問題不同的問題也是很重要的。聚類問題剖析了異構遷入子圖，在某種程度上這更有凝聚力 ；在萬維網的背景下，這可能涉及到要區分不同含義或感覺的被查詢詞相關的網頁。因此，聚類的本質上是不同于那些通過權威性而發現提取出廣泛主題的問題，雖然后面的部分將表明某些聯系。即使我們完全能夠分析含糊不清的查詢詞 （如Windows或Gates） 的多個意義，我們將仍然留下一個潛在問題，那就是表示和過濾掉與每個查詢詞主要意思相關的大量頁面。本文的結構如下。第二部分討論的是通過廣泛主題搜索來構建萬維網上的子圖從而產生一系列豐富而理想的相關權威頁面的方法。第三部分和第四部分討論在這樣的一個子圖上識別樞紐和

11、權威性的資源的主要算法，以及該算法的一些應用。第五部分討論萬維網的搜索、 文獻計量學，和社會網絡研究領域的相關工作和聯系。第六部分描述了如何擴展我們基本的算法，進而去搜集多個樞紐頁面和相同鏈接結構內的權威頁面。最后，第七部分研究為了讓我們的技術更有效，我們應該如何定義所搜索的主題的“廣泛性”。第八部分針對在這里提出的方法的調查工作，我們進行了一些評價的問題。2 萬維網中構造一個集中性的子圖我們可以將任何集合 V 的超鏈接的頁面作為一個有向圖 G = （V ；E）： 節點對應于頁面，一個有向的邊 （p，q） E 表示的從 p 到 q 的一個鏈接。我們知道一個節點 p 出度是其所鏈接到其他的節點的

12、數目。而 p 的入度是其它的節點鏈接到P的數目。在一個圖 G中，我們可以通過以下方式隔離小區域或子圖。假設W V是一些頁面的子集，我們使用 G W 來表示圖中的W： 其節點是在W中的頁面，且它的邊對應于 W.在頁面之間的所有鏈接。假設(jish)我們針對字符串進行(jnxng)廣泛主題查詢。我們希望通過鏈接結構的分析找到權威性高的頁面(y min)；但首先我們應該找到我們算法所操作的在萬維網中的那個子圖。在這里我們主要是關注在相關頁面上的計算量。因此，在這里我們舉個例子，我們可以將分析限制在集合Q（），此處Q（）是包含所查詢字符串的所有頁面，但這有兩個明顯的弊端。首先，這個集合可能會包含超過百

13、萬的頁面，因此需要大量的計算成本；第二，我們發現部分或大部分最適合主題的資源可能不屬于這一集合。理想情況下，我們關注于具有以下屬性的頁面的集合S（）。（ = 1 * ROMAN I）S（）相對小。（ = 2 * ROMAN II）S（）是具有很多相關的頁面。（ = 3 * ROMAN III）S（） 包含大部分 （或許多） 最權威的資源。通過保持集合 S（） 小，我們就能夠負擔得起應用非平凡算法的計算開銷 ； 通過確保S（）具有很多相關的頁面，我們能容易找到好的權威資源，因為這些頁面很可能需要大量引用。我們怎樣才能找到這樣的一個集合呢？對于參數t（通常設置其值為200），我們首先從一個基于文本

14、的搜索引擎 AltaVista 17 或Hotbot 57 搜索查詢字符串 ，并從中收集 t 個排名最高的頁面。我們將這t個頁面作為根集合R（）。根集合滿足前面所需要的（）和（）兩條性質。但它一般是不滿足 (iii)的。我們看一下這個，最上層的 t個 頁面由我們使用的基于文本的搜索引擎所返回返回的，它們包含所查詢的字符串 。因此 R() 顯然是集合Q()的子集，且Q()是所有包含的頁面。我們爭論的是 Q() 往往不滿足條件 (iii)。它觀察在 Q()也是很有趣的，R()頁面之間通常鏈接是極少的，這通常是無結構的。例如，在我們的實驗中，查詢詞java的根集在不同域中的頁面之間包含15個鏈接；查

15、詢詞 censorship 的根集在不同域中的頁面之間包含28個鏈接. 這些數字都是典型的多種查詢嘗試 ；他們應與根集頁面之間存在的200*199 = 39800個潛在鏈接進行比較。然而，我們可以(ky)使用根集 S()，來產生(chnshng)一組頁面集合(jh)S()，它將滿足我們一直在尋找的那些條件。考慮針對查詢主題，那些強有力的權威資源盡管它不在集合 R()，但是很可能會在 R() 所指向的鏈接中的至少一個頁面中。因此，我們可以通過擴大 R() ，在子圖中增加權威資源的權值，并沿著鏈接，進入和離開它。具體而言，我們定義了下面的過程。即：對于(duy)子圖(,E,t,d): 所查詢(ch

16、xn)字符串.E : 基于(jy)文本的搜索引擎T， d : 自然數R（）：針對字符串，搜索引擎E的結果中的前t 個排名最高的頁面使 S（）:= R（）對于每個頁面 p （）使T+(p) 表示p指向的所有的頁面使T(p) 指向p的所有頁面將T+(p)中的所有頁面添加到 S()中如果T(p)的絕對值 d 則：將T(p)中的所有(suyu)頁面添加到 S()中.否則(fuz)從T(p)中添加(tin ji)d個頁面中到 S()中.結束返回S()因此，我們通過與日俱增的 R()，獲得 S()。其中包括了R()中的一個頁面所指向的任意頁面，以及其他指向R()的任意頁面。限制條件是我們允許R()中單個頁

17、面所指向的最多d個頁面加入到 S()中。后一點至關重要，因為一些萬維網上的的網頁由數十萬個頁面指向它，但如果我們想要保持S()相對小，S() 中就不能完全包括所有的這些頁面。我們提到了 S() 是 的基本集合 ；在我們的實驗中，我們通過在搜索引擎 AltaVista中調用子圖過程，設置t = 200 和 d = 50來構建它。我們發現S()通常滿足上面多提到的（），（）和（）它的大小通常是在10005000范圍內；而且，如上所述，權威的資源只能被根集 R() 中的 200 個頁面中的任何一個進行添加，才能被添加到 S()中。在下一部分，我們將描述我們計算樞紐以及計算基本集合S()中權威資源的算

18、法。在談到這之前, 我們討論一個提供純粹導航功能的啟發式算法，它對于消除鏈接的影響非常有用。首先，讓 GS() 表示上面所說的，在 S() 頁面上所引導出來的子圖。我們將GS()中的兩種鏈接區分開來。如果是鏈接不同域名之間的頁面，則該鏈接是橫向鏈接，如果是相同域名之間的鏈接，則稱它為內部鏈接。這里的“域名”，我們指的是在與網頁關聯的 URL 字符串的第一級。由于內部鏈接往往是一個網頁基礎結構的導航，他們比橫向鏈接所指向的頁面傳送的權威信息少。因此，我們從GS()中刪除所有的內部鏈接，保持只留下對應于橫向鏈接的邊緣部分 ；最終產生了圖 G()。這是一個(y )非常簡單的啟發法，但我們(w men

19、)發現它有效避免了許多(xdu)如其他鏈接同樣的方式所產生的異常狀態。還有其他簡單的啟發式算法，可以用于消除那些看起來并不直觀的鏈接，以此來產生權威資源。其中值得一提的是我們基于以下的觀察。假設同一個域名中的大量頁面指向同一個頁面p。很多時候，在這些引用頁頁中，這對應于很多的代言、 廣告或一些其他類型的的“合謀” 例如這句話“此站點設計的”和相應的鏈接，在給定域中的每一頁的底部。要消除這種現象，我們可以設置參數 m （通常為m 4-8 ），并僅允許來自單個域最多m頁可以指向任何給定的頁面 p。再次，在某些情況下，這將是一個有效的啟發式算法，盡管我們做接下來的實驗時并沒有使用它。3 計算樞紐及權

20、威資源上一節的方法提供了一個比較集中的查詢主題的小的子圖G()它有許多相關的頁面和很權威的資源。現在我們單純地通過 G() 的鏈接結構分析，來從頁面的整體集合中提取這些很權威的資源。最簡單的方法，可以說，通過他們的入度指向在 G()它們的鏈接的數量來進行排序。早些時候，當它被應用到包含所查詢目標字符串 中搜集頁面的時候，我們沒有考慮這種想法。 但是現在我們明顯需要構建一個相關頁面的小集合，而這個集合是包含我們想要找的大部分的權威資源的。因此，這些權威資源既屬于 G()，也被G()中的頁面大量引用。事實上，純粹由入度的排序方法通常在G() 的上下文中所起的效果比我們之前所預想的要好 ；在某些情況

21、下，它可以產生一律的高質量的結果。然而，該方法還保留著幾個重大問題。例如，查詢“java”，具有最大的入度的頁面包括 和 ，以及廣告加勒比海度假，和亞馬遜書主頁的頁面。這樣的混雜是從這個簡單排序方案產生問題的類型所產生的代表： 雖然這些頁面的前兩個當然是“好”的答案，其他與查詢主題無關 ；它們雖然入度較大但缺乏主題統一性。這表明基本的困難是在子圖G()的入度最具權威性的和簡單“普遍流行”的網頁之間存在的內在的張力；我們最后需要的網頁是入度較大，且符合我們的查詢主題。你也許(yx)會疑惑是否需要(xyo)圍繞這些(zhxi)問題，針對基礎集合，進一步利用頁面的文本內容，而不僅僅是利用G() 的鏈

22、接結構。我們現在表明情況并非如此它其實可以更有效地從鏈接提取信息我們開始以下的觀察。和權威網頁內容相關的初始查詢不僅要查詢入度較大的 ；更因為它們共同話題中的所有權威資源，所以也應該考慮是否與指向它們的頁面集重疊。因此，除了極具權威性的頁面之外，我們也期望找到所謂的樞紐頁：這些是鏈接到多個相關權威頁面的的頁面。這些樞紐頁“齊心協力”圍繞一個共同的主題，并使我們能夠從入度較大的頁面中拋棄不相關的頁面。（如圖 2 所示，這是一個梗概性的例子； 當然，在現實中，這幅畫并不是如此簡單的）樞紐頁面和權威頁面表現出相輔相成的關系： 一個良好的樞紐頁是指向許多好的權威性資源的頁面 ； 同時一個好的權威性頁面

23、是許多的樞紐頁所指向的網頁。顯然，如果我們想要在子圖 G（）內確定樞紐頁和權威性頁面，我們需要一種方法來打破這種循環。一種(y zhn)迭代算法。我們通過迭代(di di)算法，利用集樞紐頁和權威頁面之間的關系，來保持和更新每個頁面的權重(qun zhn)數值。對于每一個頁面P,我們賦予一個非負的代表權威程度的權值x(p)，也賦予一個代表樞紐程度的一個權值y(p)。我們把權重的每種類型都進行歸一化，保持其平方的總和為 1不變： 我們將有最大的x和y的值的頁面分別作為最好的權威頁面和樞紐頁面。數值，它自然地表達了樞紐頁面與權威頁面之間相輔相成的關系，如接下來所示：如果具有較大的 x 值的頁面p

24、指向許多頁面，那么它就應該獲得較大的 y 值 ；如果頁面 p被許多頁具有較大的 y值的頁面所指，那么它就應該獲得較大的 x 值。我們用I和 O定義了以下兩個關于權重的操作，給出權重 x(p),y(p)，I操作可更新 x 權重如下所示：而O操作可以更新y的權重：因此 I 和 O 操作是樞紐頁面和權威頁面加強彼此的基本手段。（參見圖 3）。現在(xinzi)，若要查找所需的“平衡(pnghng)”值權重(qun zhn)，一個是可以交替使用I和 O 操作中，看看是否到達了一個固定的點。事實上，我們現在可以說明我們基本的算法的一個描述。我們將權重 x(p)的集合作為一個向量集 x，它是 G()中每個頁面的一個坐標 ；類似地，我們將權重 y(p) 的集合作為一個向量 y。此過程可用于以下(yxi)簡單方法(fngf)來篩選出前c個權威(qunwi)頁面和前 c 個樞紐頁面。我們將在與G()等價的集合G 上應用篩選過程，通常與 c 5-10，。要解決如何最好地選擇 k的問題，我們首先申明，將一個任意大的 k 值作為迭代次數使用迭代，數列x(k)和y(k