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

蘇亞博

（四川大學(xué)計算機(jī)學(xué)院，成都 610065)

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

蘇亞博

（四川大學(xué)計算機(jī)學(xué)院，成都 610065)

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

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

0 引言

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

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

1 算法描述

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

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

輸入：鏈接link

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

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

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

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

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

如果link0的地址中含有自指向標(biāo)記，則去掉link0中的自指向標(biāo)記；

如果link0是外鏈，忽略link0；

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

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

將link->link0的指向關(guān)系加入到E中。

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

⑤遍歷E中新加入的鏈接關(guān)系（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é)點(diǎn)，步驟⑤結(jié)束。

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

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

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

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

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

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

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

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

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

從E1中移除parent2->page2；

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

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

從E1中移除parent1->page1；

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

⑥將鏈接link標(biāo)記為已訪問過。

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

2 實(shí)驗(yàn)結(jié)果及可視化

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

3 結(jié)語

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

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

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

[2][英]邁克·塞沃爾著;孫建軍,李江,張煦等譯.鏈接分析:信息科學(xué)的研究方法.南京:東南大學(xué)出版社,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-），男（漢族），河南南陽人，研究方向?yàn)閿?shù)據(jù)挖掘

2016-02-23

2016-03-15