基于鏈接分析的Web站點結構提取算法

蘇亞博

（四川大學計算機學院，成都 610065)

基于鏈接分析的Web站點結構提取算法

蘇亞博

（四川大學計算機學院，成都 610065)

隨著互聯網技術的發展，大多數站點體積龐大，結構復雜，使得人們難以從中提取出完整、準確的信息。將鏈接分析引入到站點結構的提取中，提出一種Web站點結構提取算法，提高站點結構的提取效率。

鏈接分析；站點結構；PageRank

0 引言

近年來，隨著互聯網的快速發展和普及，網絡信息資源呈現爆炸式的增長。大量的網絡信息資源極大地滿足人們獲取信息的需要，但也給人們有效查找信息和獲取信息帶來了困難。萬維網由一系列互相鏈接的超文本組成，即網頁，用戶通過點擊鏈接來訪問網頁，獲取相應的信息。萬維網中通過鏈接的信息組織方式，靈活性強，鏈接將資源有機的聯系在一起，用戶可以通過點擊鏈接來跳轉到感興趣的內容。鏈接不僅有線性關系的上下翻頁，還有非線性的跳轉，鏈接之間關系錯綜復雜，用戶很容易迷失在鏈接之中，具體表現為用戶不知道當前瀏覽網頁所在的具體位置，較難返回原來的鏈接和找到興趣鏈接，特別是在站點信息量大、用戶不了解站點的導航設施時。鏈接的非線性跳轉，還容易使用戶跳過重要的內容，目標分散，影響信息獲取的效率。站點結構的提取不僅能夠提高用戶信息瀏覽的效率，也有助于站點的管理者判斷站點的信息組織是否高效和結構是否合理，從而優化站點結構。

網絡鏈接是利用超鏈接和超文本技術表現網絡中兩個或多個事物（服務器、網站、網頁地址、文件、程序、文字、圖像、聲音等）之間的關系[1]。鏈接分析研究大約開始于1995年，分布于多個學科領域中，包括計算機科學領域的搜索引擎開發、數學領域的結構和復雜性分析、社會學領域的社交關系網絡分析和信息管理領域的網絡信息計量研究等[2]。Google搜索引擎創始人Sergey Brain和Larry Page等提出“PageRank”算法[3]，根據網頁中鏈入和鏈出的鏈接數量和質量判斷一個網頁的質量和權威性，賦予網頁相應的權重并進行排序，取得了巨大的成功。站點將所要表現的信息以特定的鏈接結構按照某種邏輯方式進行有序、分層次的組織起來，形成一種高級的網絡信息組織形式。本文基于PageRank算法，分析頁面間的鏈接關系，提取站點結構。

1 算法描述

Web站點可以使用圖抽象表示：website=（V，E），其中V表示站點的頁面集合，E表示站點頁面間的鏈接關系。站點結構是一棵樹T=（V，E1），其中E1哿E。樹T的根節點root表示站點的首頁，對于任意節點v∈V，v所代表的頁面包含的有意義的超鏈接的個數表示v的出度。出度為0的節點為葉子結點，代表站點的內容頁面；出度大于0的節點為非葉子節點，非葉子結點有2種情況：一種情況是該頁面在站點中只用于導航而不包含訪問的內容，即純導航節點（目錄頁面）；另一種情況是該頁面既包含導航內容，又包含訪問的內容，即復合節點。站點結構提取算法需要識別出頁面的類型及頁面間的關系，從而構造除出實際的站點結構。

站點結構T=（V，E1），V初始化為含有頁面根節點的集合，E和E1初始化為空的集合。站點結構提取算法偽代碼如下：

輸入：鏈接link

輸出：訪問鏈接link后更新的站點結構T步驟：

①如果鏈接link已經訪問過，直接結束。

②訪問鏈接link獲取頁面內容content。

③遍歷content中的每一個鏈接link0：

如果link0的地址是相對地址，則將link0的地址轉化為絕對地址；

如果link0的地址中含有自指向標記，則去掉link0中的自指向標記；

如果link0是外鏈，忽略link0；

如果link0與link相同，忽略link0；

如果頁面集合V中沒有含有link0，則將link0加入到V中；

將link->link0的指向關系加入到E中。

④根據新的鏈接關系集合E，計算頁面集合V中所有頁面的PageRank值。

⑤遍歷E中新加入的鏈接關系（source->target）：

如果source->target加入E1中不會產生環，則將source->target加入E1中，步驟⑤結束；

比較source與target的PageRank值：

如果page1的PageRank值大于page2的PageR-ank值得2倍：

如果page1是page2的祖先節點，步驟⑤結束。

從E1中移除parent->page2（parent是page2在T中的父節點）；

將page1->page2加入到E1中，步驟⑤結束。

如果page2的PageRank值大于page1的PageR-ank值得2倍：

如果page2是page1的祖先節點，步驟⑤結束。

從E中移除parent->page1（parent是page1在T中的父節點）；

將page2->page1加入到E1中，步驟⑤結束。

取出page1的父節點parent1；

取出page2的父節點parent2；

如果page1是page2的祖先節點：

從E1中移除parent2->page2；

將parent1->page2加入到E中，步驟⑤結束。

如果page2是page1的祖先節點：

從E1中移除parent1->page1；

將parent2->page1加入到E中，步驟⑤結束。

⑥將鏈接link標記為已訪問過。

本算法能夠根據當前訪問的鏈接情況，動態更新構造的站點結構。因此，當網站規模增大或結構發生變化時，能夠及時增量更新站點結構。

2 實驗結果及可視化

如圖1，將本文的算法應用于獲取川大網站（www. scu.edu.cn）的站點結構。為了展示提取的站點結構，本文基于Prefuse[4]工具庫，使用力導引布局算法，可視化提取出的站點結構。圖中節點的顏色表示該頁面是否已被訪問，節點的內容表示頁面的標題，為了簡潔，如果頁面的標題大于4個字，則以省略號（…）代表標題。從運行結果觀察，本算法能夠較好地提取站點結構。

3 結語

本文使用PageRank算法區分鏈接的層次，過濾掉頁面間冗余的鏈接關系，從Web站點的連接關系中提取站點結構。通過訪問實際站點驗證效果，本算法能夠較好的分析站點頁面間的層次關系，展示出站點的組織結構。

然而，站點中鏈接不僅會靜態存在于頁面之中，還會動態的由JavaScript代碼創建，本文算法并未考慮這種鏈接關系，因此作為下一步工作進行完善。

[1]段宇峰,網絡鏈接分析與網站評價研究.北京:北京圖書館出版社,2005.

[2][英]邁克·塞沃爾著;孫建軍,李江,張煦等譯.鏈接分析:信息科學的研究方法.南京:東南大學出版社,2009.

[3]Brin S,Page L.The Anatomy of a Large-Scale Hypertextual Web Search Engine.In:Thistlewaite P,et al.,eds.Proceedings of the 7th ACM-WWW International Conference.Brisbane:ACM Press,1998：107-117.

[4]Prefuse,http://prefuse.org,2016.

A Website Structure Extract Algorithm Based on Link Analysis

SU Ya-bo

（College of Computer Science,Sichuan University,Chengdu 610065）

With the development of Internet technology,most websites are bulky,and its complex structure makes it difficult for people to extract complete and accurate information.Propose an algorithm based on link analysis to exact the website structure,which improves the effec-tiveness of structure extraction.

Link Analysis;Website Structure;PageRank

1007-1423（2016）08-0054-03

10.3969/j.issn.1007-1423.2016.08.011

蘇亞博（1990-），男（漢族），河南南陽人，研究方向為數據挖掘

2016-02-23

2016-03-15