蘇亞博

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

基于鏈接分析的Web站點結(jié)構(gòu)提取算法

蘇亞博

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

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，大多數(shù)站點體積龐大，結(jié)構(gòu)復雜，使得人們難以從中提取出完整、準確的信息。將鏈接分析引入到站點結(jié)構(gòu)的提取中，提出一種Web站點結(jié)構(gòu)提取算法，提高站點結(jié)構(gòu)的提取效率。

鏈接分析；站點結(jié)構(gòu)；PageRank

0 引言

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

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

1 算法描述

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

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

輸入：鏈接link

輸出：訪問鏈接link后更新的站點結(jié)構(gòu)T步驟：

①如果鏈接link已經(jīng)訪問過，直接結(jié)束。

②訪問鏈接link獲取頁面內(nèi)容content。

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

如果link0的地址是相對地址，則將link0的地址轉(zhuǎn)化為絕對地址；

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

如果link0是外鏈，忽略link0；

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

如果頁面集合V中沒有含有l(wèi)ink0，則將link0加入到V中；

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

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

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

如果source->target加入E1中不會產(chǎn)生環(huán)，則將source->target加入E1中，步驟⑤結(jié)束；

比較source與target的PageRank值：

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

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

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

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

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

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

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

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

取出page1的父節(jié)點parent1；

取出page2的父節(jié)點parent2；

如果page1是page2的祖先節(jié)點：

從E1中移除parent2->page2；

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

如果page2是page1的祖先節(jié)點：

從E1中移除parent1->page1；

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

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

本算法能夠根據(jù)當前訪問的鏈接情況，動態(tài)更新構(gòu)造的站點結(jié)構(gòu)。因此，當網(wǎng)站規(guī)模增大或結(jié)構(gòu)發(fā)生變化時，能夠及時增量更新站點結(jié)構(gòu)。

2 實驗結(jié)果及可視化

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

3 結(jié)語

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

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

[1]段宇峰,網(wǎng)絡鏈接分析與網(wǎng)站評價研究.北京:北京圖書館出版社,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-），男（漢族），河南南陽人，研究方向為數(shù)據(jù)挖掘

2016-02-23

2016-03-15