1000-9825/2003/14(10)17682003 Journal of Software 软 件 学 报Vol.14, No.10万维网的链接结构分析及其应用综述
王晓宇, 周傲英+
(复旦大学 计算机科学与工程系,上海 200433)
(复旦大学 智能信息处理开放实验室,上海 200433)∗
Linkage Analysis for the World Wide Web and Its Application: A Survey
WANG Xiao-Yu, ZHOU Ao-Ying+
(Department of Computer Science and Engineering, Fudan University, Shanghai 200433, China)
(Intelligent Information Processing Laboratory, Fudan University, Shanghai 200433, China)
+ Corresponding author: Phn: 86-21-65643503, Fax: 86-21-65643503, E-mail: [email protected]
http://www.cs.fudan.edu.cn
Received 2002-08-22; Accepted 2003-04-21
Wang XY, Zhou AY. Linkage analysis for the World Wide Web and its application: A survey. Journal ofSoftware, 2003,14(10):1768~1780.Abstract:Up to now, the World Wide Web (WWW) grows into a large hyperlinked corpus with more than 800million pages and 5 600 million hyperlinks. Moreover, it is obviously impossible that any global ‘planning’ can beimposed on the creation of such a corpus. This brings some challenges to many research fields on the World WideWeb. On the other hand, the hyperlinked Web pages in the networking environment can be a very rich informationsource for daily or business use, provided people have effective means for understanding the Web. Linkage analysisis playing more and more significant role in many fields on the World Wide Web. Recent advances about therelevant research and application of linkage analysis of World Wide Web are presented in this paper. In particular,some results and achievements about linkage analysis and its applications on Web searching, Web communitydiscovery and the Web modeling are surveyed here.
Key words:
摘 要:linkage analysis; World Wide Web; Web searching; knowledge discovery当今万维网的规模已经快速发展到包含大约80亿个网页和560亿个超链接.此外,对万维网的创建进行全局规划显然是不可能的.这些都对万维网的相关研究提出了挑战.另一方面,互联网环境下通过超链连接起来的网页,为人们的日常和商务用途提供了非常丰富的信息资源,但前提是必须掌握有效的办法来理解万维网.链接结构分析在万维网的很多研究领域起着越来越重要的作用.全面介绍了万维网链接分析方面的最新研究进展和应用情况,对链接分析在Web信息搜索
），男,安徽濉溪人,博士,主要研究领域为人工智能,互联网环境下的数据搜索.
王晓宇 等:万维网的链接结构分析及其应用综述
关键词:链接分析;互联网;Web搜索;知识发现
文献标识码: A1769中图法分类号:TP393
随着互联网的不断发展,人们越来越多地在互联网上发布和获取信息.Web已经成为信息制造
着密切的联系.但是,互联网中特有的许多问题,诸如超大规模的非结构化文档数量
库技术在互联网环境中很难有效地应用.加包工和处理的主要平台.传统的互联网应用技术大多是基于文档内容的,与经典的信息检索技术和数据库技术有含在文档中的大量多媒体信息,甚至相当含糊或不规范的用户查询表示等,都使得经典的信息检索技术和数据
另一方面,互联网又包含了传统数据环境所没有的另一种丰富信息,即互联网的超链接拓扑结构.网页间的超链接一方面引导网页浏览的过程,另一方面也反映了网页创建者的一种判断,即有理由认为,如果网页A存在一条超链接指向网页B,那么网页A的作者是认为网页B包含了有价值的信息.因此,充分利用互联网的链接结构信息对互联网应用技术的研究将具有极为重要的意义.事实上,越来越多的学者已经开始致力于这方面的研究,总体来说主要包括以下3个方向:
• 链接结构分析在Web信息搜索中的应用;
• 链接结构特征与互联网中出现的潜在社区之间的关联;
• 链接结构在理解互联网自身属性特点和成长模式方面所处的地位和作用.
本文第1节较为详细地介绍已有的一些基于链接分析的主题提取算法.这部分内容不仅包括了经典的HITS算法和Google中的PageRank算法,同时还介绍了一些重要的衍生算法,并从理论和应用的角度对这些算法进行了比较.第2节介绍互联网社区研究的意义以及已有的两种互联网社区发现技术.第3节展示了在互联网结构图分析与建模研究方面正在进行的一些初步探索.第4节简要介绍链接分析在其他超文本检索研究及网页智能爬取方面的一些应用现状.第5节探讨链接结构研究将来可能的研究方向.
1 主题提取的模型与算法
通过搜索引擎查找与某个主题相关的网页非常容易,但是,假如查询是一个相对比较广泛的主题,那么搜索引擎通常会返回成千上万的条目.尽管从某种意义上说,这些内容大多是和主题相关的,但是它们的价值程度却千差万别.而且,对网页的价值判断本身又是一个非常主观的过程,许多因素都会影响这种价值的判断,诸如站点或网页的组织和形式
Compaq系统研究中心的Web Archaeology项目以及我们提出的STED算法.
1.1 PageRank算法
PageRank算法[9]是最早并且最成功地将链接分析技术应用到商业搜索引擎中的算法.它的基本出发点是试图为搜索引擎所涵盖的所有网页赋予一个量化的价值度.每个网页被量化的价值通过一种递归的方式来定义,由所有链接向它的网页的价值程度所决定.显然,一个被很多高价值网页所指向的网页也应该具有很高的价值.这种规则可以用一种随机网上冲浪(surfer)的模型来描述.具体来说,如果假设冲浪者跟随链接进行了若干步的浏览后转向一个随机的起点网页又重新跟随链接浏览,那么一个网页的价值程度值就由该网页被这个随机冲浪者所访问的频率所决定.
这个过程也可以理解成一个Markovian过程,每个网页是一个状态,从一个网页跟随链接浏览到另一个网页可以被看作是一个状态的迁跃,所有这种迁跃的概率是相同的.但是,考虑如果存在一类网页,这类网页中不包含任何指向其他网页的链接,那么这种网页将成为沉积(sink)网页,并使得上述这种迁跃的过程在沉积网页上
1770Journal of Software 软件学报 2003,14(10) 永远终止.解决这个问题的方法很简单,假如一个随机冲浪者遇到了这种沉积网页,那么他可以随机地挑选另一个网页并继续他的浏览.为了对那些不是沉积的网页也一视同仁,这种类型的随机迁跃应该能以相同的概率在任何一个网页上发生.下面是整个过程的形式化表达,并由此可以为每一个网页计算其价值度PR:
PR(i)=d⋅D(i)+(1−d)∑j
1000-9825/2003/14(10)17682003 Journal of Software 软 件 学 报Vol.14, No.10万维网的链接结构分析及其应用综述
王晓宇, 周傲英+
(复旦大学 计算机科学与工程系,上海 200433)
(复旦大学 智能信息处理开放实验室,上海 200433)∗
Linkage Analysis for the World Wide Web and Its Application: A Survey
WANG Xiao-Yu, ZHOU Ao-Ying+
(Department of Computer Science and Engineering, Fudan University, Shanghai 200433, China)
(Intelligent Information Processing Laboratory, Fudan University, Shanghai 200433, China)
+ Corresponding author: Phn: 86-21-65643503, Fax: 86-21-65643503, E-mail: [email protected]
http://www.cs.fudan.edu.cn
Received 2002-08-22; Accepted 2003-04-21
Wang XY, Zhou AY. Linkage analysis for the World Wide Web and its application: A survey. Journal ofSoftware, 2003,14(10):1768~1780.Abstract:Up to now, the World Wide Web (WWW) grows into a large hyperlinked corpus with more than 800million pages and 5 600 million hyperlinks. Moreover, it is obviously impossible that any global ‘planning’ can beimposed on the creation of such a corpus. This brings some challenges to many research fields on the World WideWeb. On the other hand, the hyperlinked Web pages in the networking environment can be a very rich informationsource for daily or business use, provided people have effective means for understanding the Web. Linkage analysisis playing more and more significant role in many fields on the World Wide Web. Recent advances about therelevant research and application of linkage analysis of World Wide Web are presented in this paper. In particular,some results and achievements about linkage analysis and its applications on Web searching, Web communitydiscovery and the Web modeling are surveyed here.
Key words:
摘 要:linkage analysis; World Wide Web; Web searching; knowledge discovery当今万维网的规模已经快速发展到包含大约80亿个网页和560亿个超链接.此外,对万维网的创建进行全局规划显然是不可能的.这些都对万维网的相关研究提出了挑战.另一方面,互联网环境下通过超链连接起来的网页,为人们的日常和商务用途提供了非常丰富的信息资源,但前提是必须掌握有效的办法来理解万维网.链接结构分析在万维网的很多研究领域起着越来越重要的作用.全面介绍了万维网链接分析方面的最新研究进展和应用情况,对链接分析在Web信息搜索
），男,安徽濉溪人,博士,主要研究领域为人工智能,互联网环境下的数据搜索.
王晓宇 等:万维网的链接结构分析及其应用综述
关键词:链接分析;互联网;Web搜索;知识发现
文献标识码: A1769中图法分类号:TP393
随着互联网的不断发展,人们越来越多地在互联网上发布和获取信息.Web已经成为信息制造
着密切的联系.但是,互联网中特有的许多问题,诸如超大规模的非结构化文档数量
库技术在互联网环境中很难有效地应用.加包工和处理的主要平台.传统的互联网应用技术大多是基于文档内容的,与经典的信息检索技术和数据库技术有含在文档中的大量多媒体信息,甚至相当含糊或不规范的用户查询表示等,都使得经典的信息检索技术和数据
另一方面,互联网又包含了传统数据环境所没有的另一种丰富信息,即互联网的超链接拓扑结构.网页间的超链接一方面引导网页浏览的过程,另一方面也反映了网页创建者的一种判断,即有理由认为,如果网页A存在一条超链接指向网页B,那么网页A的作者是认为网页B包含了有价值的信息.因此,充分利用互联网的链接结构信息对互联网应用技术的研究将具有极为重要的意义.事实上,越来越多的学者已经开始致力于这方面的研究,总体来说主要包括以下3个方向:
• 链接结构分析在Web信息搜索中的应用;
• 链接结构特征与互联网中出现的潜在社区之间的关联;
• 链接结构在理解互联网自身属性特点和成长模式方面所处的地位和作用.
本文第1节较为详细地介绍已有的一些基于链接分析的主题提取算法.这部分内容不仅包括了经典的HITS算法和Google中的PageRank算法,同时还介绍了一些重要的衍生算法,并从理论和应用的角度对这些算法进行了比较.第2节介绍互联网社区研究的意义以及已有的两种互联网社区发现技术.第3节展示了在互联网结构图分析与建模研究方面正在进行的一些初步探索.第4节简要介绍链接分析在其他超文本检索研究及网页智能爬取方面的一些应用现状.第5节探讨链接结构研究将来可能的研究方向.
1 主题提取的模型与算法
通过搜索引擎查找与某个主题相关的网页非常容易,但是,假如查询是一个相对比较广泛的主题,那么搜索引擎通常会返回成千上万的条目.尽管从某种意义上说,这些内容大多是和主题相关的,但是它们的价值程度却千差万别.而且,对网页的价值判断本身又是一个非常主观的过程,许多因素都会影响这种价值的判断,诸如站点或网页的组织和形式
Compaq系统研究中心的Web Archaeology项目以及我们提出的STED算法.
1.1 PageRank算法
PageRank算法[9]是最早并且最成功地将链接分析技术应用到商业搜索引擎中的算法.它的基本出发点是试图为搜索引擎所涵盖的所有网页赋予一个量化的价值度.每个网页被量化的价值通过一种递归的方式来定义,由所有链接向它的网页的价值程度所决定.显然,一个被很多高价值网页所指向的网页也应该具有很高的价值.这种规则可以用一种随机网上冲浪(surfer)的模型来描述.具体来说,如果假设冲浪者跟随链接进行了若干步的浏览后转向一个随机的起点网页又重新跟随链接浏览,那么一个网页的价值程度值就由该网页被这个随机冲浪者所访问的频率所决定.
这个过程也可以理解成一个Markovian过程,每个网页是一个状态,从一个网页跟随链接浏览到另一个网页可以被看作是一个状态的迁跃,所有这种迁跃的概率是相同的.但是,考虑如果存在一类网页,这类网页中不包含任何指向其他网页的链接,那么这种网页将成为沉积(sink)网页,并使得上述这种迁跃的过程在沉积网页上
1770Journal of Software 软件学报 2003,14(10) 永远终止.解决这个问题的方法很简单,假如一个随机冲浪者遇到了这种沉积网页,那么他可以随机地挑选另一个网页并继续他的浏览.为了对那些不是沉积的网页也一视同仁,这种类型的随机迁跃应该能以相同的概率在任何一个网页上发生.下面是整个过程的形式化表达,并由此可以为每一个网页计算其价值度PR:
PR(i)=d⋅D(i)+(1−d)∑j