1、-1- 、實驗目的 理解搜索引擎的鏈接結構子系統的基本功能； 了解萬維網鏈接的結構圖及特性； 理解HITS算法的基本思想和原理。 二、實驗原理及基本技術路線圖（方框原理圖） 萬維網的鏈接結構通常使用有向圖的方式來描述， 在萬維網鏈接結構圖中，網頁是圖的節點; 而超鏈接則是鏈接節點的有向邊（從源網頁指向目的網頁） 。每一條從源網頁指向目的網頁的超 鏈接，既稱為源網頁的“出鏈接” ，乂稱為目的網頁的“入鏈接”。用圖表示萬維網鏈接結構，如 下圖： 關丁萬維網結構圖的規模很難給出一個準確的統計結果， 這是因為：圖中的節點存在形式紛 繁復雜，即使不考慮網頁的可訪問性問題（部分網頁會對用戶訪問加以限制，如

2、采取登錄策略等）， 只考慮能夠被自由訪問的網頁，這些網頁中既有以傳統形式存在的靜態頁面， 乂有隨用戶查詢要 求在服務器端實時生成的動態頁面，甚至還有用 AJAX技術生成的URL相同但頁面內容千差萬 別的頁面。而超鏈接的界定在當前的網絡環境下也存在諸多困難。 2008年7月，谷歌在其官方 博客上聲稱其索引量達到1萬億網頁，這一估計一定程序上反映了圖的節點集合規模。 鏈接結構信息是網絡信息環境與傳統信息媒介的最大區別之一。 對丁搜索引擎而言，與用戶 查詢需求乃至頁面內容均相對獨立的超鏈接結構是用以評價萬維網數據質量的重要依據。 在2001年SIGIR會議上，Craswell等人對鏈接結構分析算法的

3、應用方式進行了分析，提出 萬維網超鏈接應具有的兩個特性： -2- 如果存在超鏈接L從頁面Psource指向頁面Pdestiny,則Psource與Pdestiny W足： 特性1：（內容推薦特性）頁面Psource的作者推薦頁面Pdestiny的內容，且利用L的鏈接文本內 容對Pdestiny進行描述。 特性2：（主題相關特性）被超鏈接連接的兩個頁面Psource與P destiny的頁面內容涉及類似的主 題。 然而這兩個特性對于萬維網數據爆炸性增長的背景下被認為過于理想主義。 萬維網節點之間 的超鏈接關系遠比特性1和特性2描述的情況要復雜的多。但是，一方面，經過改進的鏈接分析 算法還是可以為

4、頁面質量評估提供參考； 另一方面，在經過數據活理之后的近似理想的網絡環境 中，它們還是可以發揮其挑選高質量網頁的作用，因此鏈接分析算法仍舊是當前研究的熱點之一。 HITS算法是由Jon Kleinberg在20世紀90年代提出的一種鏈接分析算法。 HITS算法是 Hyperlink-Induced Topic Search基于超鏈接推演的主題搜索算法）的簡稱，它的核心思想是對 網頁如下兩個方面的權威程度進行評價。首先，內容權威度（ Authority Value）,即網頁本身內容 的受歡迎程序；其次，鏈接權威度（Hub Value）,即網頁鏈接到其他受歡迎資源的程度。 HITS算法的實施包括兩

5、個階段，對用戶輸入的查詢主題而言，首先是通過文本搜索過程獲 取與此查詢主題內容相關的網頁集合，并適當擴充該網頁集合，以包括盡可能多的結果候選網頁， 同時使用結果集合網頁問的鏈接結構關系更加完整； 隨后則是通過一個“迭代一收斂”的過程計 算網頁集合中每個頁面對應的鏈接權威度和內容權威度數值。 算法最后輸出的是分別按照鏈接權 威度與內容權威度排序的結果列表，用戶可以根據需求不同，選擇其中的結果頁面進行瀏覽。-3- HITS ( HyperlinkHITS ( Hyperlink- -Induced T opic Search)Induced T opic Search)算法 (1) 選取網絡信息檢

6、索系統的結果集合 R 將R, R所指向的網頁和指向 R的網頁構成的鏈接結構圖稱為 G。 對于G中每一個節點n,設H(n)和A(n)分別是其鏈接權威度和內容權威度，向量 H和A分別為G的鏈接 權威度和內容權威度結果向量。 (2) 設定H = A=(1, 1, - , 1),即：對G中每一個節點n,設定其初始值 H(0)(n)和A(0)(n)均為1. (3) For k=1,2, 3,，N 對G中每一個節點n, A(k)(n)， H (k)m )(稱為 I 操作) 對G中每一個節點n, H (n)A(k)(mi)(稱為 O 操作) 將 H(0)(n)和 A(0)(n)(n G)作規范化處理，使A(

7、k) n) 2冒 1 , W ( H (k) n)2 且1。 n 二G n G (4)當結果向量H和A未收斂時，返回(3)；當H和A收斂時，輸出算法所計算出的 G中每一個節點 n 的 H(0)(n)和 A(0)(n)的結果。 三、所用儀器、材料(設備名稱、型號、規格等) 硬件：PC機一臺 操作系統：Windows 7 編程語言：Java IDE: eclipse 3.5.2 四、 實驗方法、步驟 實現HITS算法的主要功能模塊，并可對測試數據計算所需要內容權威度和鏈接權威度的 值。要求能夠輸出每次迭代過程的詳細信息。 五、 實驗過程原始記錄(數據、圖表、計算等) 本次實驗中沒有實現HITS算法

8、中要求的Web圖的擴展功能，而是將圖的結點和邊的信息存 儲在文件中，由程序讀入并計算各自內容權威度和鏈接權威度， 并能夠指定最大迭代次數和輸出 迭代過程的詳細信息。 Web圖的構造過程的主要代碼: /* * Web圖類的構造方法 -4- *參數文件中每一行存儲一條邊的信息 *該方法將掃描文件中的每一行，將所有的邊及結點信息讀入并構造整個圖 * 注：程序設計思想參考 http:/ * * param file 存儲了圖中邊及結點信息的文件 * throws lOException */ public WebGraph(File file) throws lOException ( this ()

9、; / 初始化相關變量 BufferedReader reader = new BufferedReader( new FileReader(file); String line; int urllndex = 0; /讀入文件，解析并存儲結點及邊的信息 while (line = reader.readLine() != null ) ( int index = line.indexOf( -); if (index 0) ( String urlFrom = line.substring(0, index).trim(); String urlTo = line.substring(ind

10、ex + 2).trim(); int urllndexFrom = -1; int urllndexTo = -1; / 存儲URL到lD的映射 if ( urlTold .containsKey(urlFrom) ( urllndexFrom = urlTold .get(urlFrom); ) else ( idToURL .put(urllndex, urlFrom.trim(); urlTold .put(urlFrom.trim(), urllndex); urllndex+; urllndexFrom = urlTold .get(urlFrom); ) / 存儲lD到URL的映

11、射 if ( urlTold .containsKey(urlTo) ( urllndexTo = urlTold .get(urlTo); ) else ( idToURL .put(urllndex, urlTo.trim(); urlTold .put(urlTo.trim(), urllndex); urllndex+; urllndexTo = urlTold .get(urlTo); ) / 存儲邊 Map tedge = new HashMap(); tedge.put(urllndexFrom, urllndexTo); edge .add(tedge.entrySet().i

12、terator().next(); ) ) this . nodeCount = idToURL .size(); / 結點數量 / 填充邊到對應的鄰接矩陣 this . matrix = new int nodeCount nodeCount ; for ( int i = 0; i edge .size(); i+) ( Entry entry = edge .get(i); ,格式如下：url1 - url2 -5- int from = entry.getKey(); int to = entry.getValue(); matrix fromto = 1; ) ) HITS算法內容權

13、威度和鏈接權威度的計算: /* * HITS 類構造方法 * param webGraph web 圖 */ public HITS(WebGraph webGraph) ( this . webGraph = webGraph; this . authorityScores = new HashMap(); this . hubScores = new HashMap(); this . nodeCount = webGraph.getNodeCount(); /初始的內容權威度和鏈接權威度均設為 1 for ( int i = 0; i webGraph.getNodeCount(); i

14、+) ( this . authorityScores .put(i, 1.0); this . hubScores .put(i, 1.0); ) /計算結點的內容權威度和鏈接權威度 ，指定最大迭代次數為 25 computeHITS(25); ) *計算結點的內容權威度和鏈接權威度 * param numIterations 最大迭代次數 */ private void computeHITS( int numIterations) ( / 迭代次數 int iterNum = numIterations; / 上一次迭代的內容權威度和鏈接權威度 ,初始值均設為0 Map preAutho

15、rityScore = new HashMap(); Map preHubScore = new HashMap(); for ( int i = 0; i 0 & !isConvergence(preAuthorityScore, authorityScores preHubScore, hubScores ) ( /存儲計算所得的內容權威度和鏈接權威度值 ，用于下次迭代之前的收斂判斷 copyAtoB( authorityScores , preAuthorityScore);-6- WebGraph webGraphHITS = new WebGraph(fileHITS); S

16、ystem. out .println( HITS 算法示例：); System. out .println( nweb 圖所對應的矩陣:); webGraphHITS.printMatrix(); System. out .println( nHITS 算法的執行過程:); hits = new HITS(webGraphHITS); copyAtoB( hubScores ,preHubScore); System. out .println( 第+ (iterNum - numIterations) + for ( int i = 0; i nodeCount ; i+) List in

17、Links = webGraph .getInLinks(i); / 入鏈接集 double authorityScore = 0; / 內容權威度 for (Integer in : inLinks) /內容權威度等于所有入鏈接的鏈接權威度之和 authorityScore += hubScores .get(in).doubleValue(); authorityScores .put(i, authorityScore); for ( int i = 0; i nodeCount ; i+) List outLinks = webGraph .getOutLinks(i); / 出鏈接集

18、 double hubScore = 0; / 鏈接權威度 for (Integer out : outLinks) /鏈接權威度等于所有出鏈接的內容權威度之和 hubScore += authorityScores .get(out).doubleValue(); hubScores .put(i, hubScore); /歸一化(使用最大值) double aMax = getMaxValue( authorityScores ); double hMax = getMaxValue( hubScores ); for ( int i = 0; i 2A - 戲 5B 6C 測試數據以上圖

19、（左）為例，將結點和邊信息存入文件 hits.txt，如上圖（右），將輸入設為 文件hits.txt,然后運行以上測試程序，得運行結果如下: HITSW法示例：法示例： s*s*圖圖所對應所對應的鄰接拒陣的鄰接拒陣: : ABC A 1 1 1 B 1 0 1 C 0 1 0 HITSM法的執行過程法的執行過程: : 第。次迭代第。次迭代： aA = 1.0 aB = 0.732 ac = 1.0 hA = 1.0 hB = 0.732 hc = 0.2679 六、實驗結果分析、經驗總結或結論（例如對實驗獲取數據的誤差分析、數據處理、成果 等。其中，繪制曲線圖時必須用標準計算紙，不得隨意用普通白紙繪畫） 通過本次實驗我們理解了 HIT S算法的基本思想和方法，并編程實現了一個簡單的HITS 算法的程序，對鏈接結構分析子系統的作用和功能有了一個較為直觀的認識。另外，這里 所得的鏈接結構分析結果，可A(A =1.0 AB：=1.0 AC=1.0 第第1次次迭代：迭代： AA=1.0 AC-1.0 第第2次次迭代：迭代： AA=1.0 AC =1.0 第第3次次迭代：迭代： AA=1.0 AB-0.7S AC=1.0 第第9次次迭代：迭代： AA=i.a AE=0.73S 第第5次