基于链接分析的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