摘要

随着互联网技术的应用广泛和高速发展，越来越的学者致力于网络信息技术的研究。互联网中无数的超链接信息带给了我们大量信息，超链接所构成的web拓扑结构可以反映网页间的关联性，挖掘其中的信息获得有用的知识成为了当前的研究热点。而网络更新的速度非常之快，web拓扑挖掘能够保持多长时间的时效性也让人思考。动态分析web拓扑结构，对不同类型网页的拓扑变化速度进行衡量，可获得变化速度规律，以辅助计算pagerank值等。

知网论文查重

本文主要包含以下工作：

通过阅读文献，深入了解web挖掘及web结构挖掘，包括其起源、定义、分类、难点、应用等，分析当前的国内外研究现状，并思考应用web结构挖掘的相关知识完成后续工作。知网查重检测系统

搭建python和scrapy环境，编写scrapy程序从互联网上爬取网页间的超链接关系信息，选取不同种类样本网页，筛选爬取的内容，将爬取到的链接信息以固定的格式存放到数据库中，形成网页间超链接关系数据库。

在数据库中建立节点表和边表，存储web拓扑结构图，描述超链接拓扑结构。知网查重检测系统

设计web拓扑变化衡量的模型，通过节点相似性和节点中心性两种web拓扑结构特征，建立基于节点相似性的图距离计算模型和基于节点中心性的图距离计算模型，分析模型优劣，选取合适的模型描述web拓扑变化。

根据基于节点相似性的图距离计算模型获得所爬取得根页面的动态web拓扑图差异向量，对差异向量进行持续性，波动性和周期的分析，总结web拓扑结构变化规律，获得结论。

1 绪论

1.1 课题背景及目的

随着社会经济的发展，互联网技术越来越普及，我们已经进入了信息时代，互联网已成为集金融、教育、商业、政府、新闻、消费等多种功能与一体的信息中心，而面对互联网上囤积的海量的信息数据时，其非结构化的数据存储模式，参差不齐真伪难辨的信息质量，和模糊的搜索方式都是我们获得所需内容时面临的极大阻力。如何从大批的文本、图片、视频、用户行为等信息中获取有用的信息、模式或者隐藏的信息，已经成为广大IT从业者的主要研究热点。

Web挖掘在互联网研究领域的作用越来越重要，如图1.1所示，其主要分为三个方面，侧重不同的应用，第一方面为web数据挖掘，即挖掘网页上的内容信息，通过对网页的文本、多媒体信息等数据的分类、聚类、总结、关联等分析手段获得所需的知识，可按照挖掘内容分为对文本挖掘和对多媒体挖掘两类；第二方面为web结构挖掘，即对网页间的超链接关系和网站的结构进行研究，通过分析超链接结构关系获取所需信息、知识，找到中心页面，权威页面等帮助优化搜索，从而提高搜素性能，主要包含超链接挖掘和页面结构挖掘；第三方面为web使用挖掘，即通过网页上的日志信息和相关数据来分析网页用户的行为模式，理解用户的行为，了解用户的爱好从而对网页的整体结构进行改进或满足用户的个性化需求，主要包括用户访问模式分析和定制个性化web站点。

Web结构挖掘是web挖掘中的重要分支，通过对超链接信息的挖掘，获得网页间的拓扑结构。Web拓扑结构是一个有向图结构，用户从开始页面进入，通过链接访问下一页面，如果两页面在web拓扑中相距越远说明这两页面的关联性是较低的，相反则关联性较高^[1]，通关分析web拓扑结构可以辅助相关数据的查找，根据网页间的超链接关系计算网页的权威度，从而提高搜索精度，web结构挖掘在这一领域的应用已经十分广泛。互联网是一个动态性极强的信息源，统计表明，至2014年全球互联网网站数量已突破10亿^[2]，而web服务器的数量还在以每年超过30%的速度增长，web网页数量以每年超过60%的速度增长。Web不仅以极快的速度增长，其信息同时也在不断地发生更新，新闻报道、公司企业、机构个人等都在不断的更新着自己的页面。所以web拓扑结构也是随时变化的，而根据web结构挖掘所获得的辅助搜索查询的信息也需及时更新，才能保证搜索的准确性。本文讲通过对web拓扑结构变化的分析获得一些规律，以此规律辅助确定web结构挖掘相关信息的更新频率，如PageRank值应多长时间计算一次等，从而确保搜索精度的时效性。

1.2 国内外研究状况

1.2.1 国内研究现状

Web挖掘指使用数据挖掘技术在互联网上进行信息和结构的挖掘，从而获得有用的知识，潜在的信息和可利用的规律等。通过阅读文献，可以看到目前在世界范围内对web挖掘的研究已经有些成就，而国内的研究现状还处在刚刚起步的状态，主要是学习和实践阶段^[5]。目前国内进行相关研究的多为高等院校和研究所，如“九五”计划、863计划等科研项目，北京大学、南京大学等进行了web数据挖掘方面的相关研究 ^[6]。

Web结构挖掘对于信息检索的价值也被充分认可，很多学者在国外web结构挖掘算法的基础上进行了深入研究和优化处理。2004年张岭和马范援使用加速评估算法对PageRank算法进行了改进以提高web结构挖掘质量^[7]。2010年范聪贤，徐汀荣，范强贤对web结构挖掘中HITS算法进行了改进研究^[8]。Web结构挖掘是一个相对较新的研究领域，通过对网页间超链接结构的挖掘获得网页关联性或权威值等信息，以此指导网页采集，帮助结果排序，资源结果聚类，查找相关网页等^[9]，目前根据web结构挖掘辅助搜索已有很多优秀成果。但对与web拓扑变化的分析却并不多见，基于web结构挖掘的网络拓扑结构变化研究还有许多问题有待于进一步研究和深化，本文将就这一问题进行探讨。

1.2.2 国外研究现状

国外在web结构挖掘领域已有一些成熟的算法及应用。网页间的超链接数据是极为宝贵的信息资源，通过web结构挖掘，获取网页间的超链接关系，分析网页间关联性或网页权威性，以此优化搜素，可以提高搜索引擎的效率和效果。当前在web结构挖掘领域，最为突出且广泛应用的算法有两种：一是由Larry Page和Sergey Brin于1998年提出的PageRank算法；二是在1999年由Jon Kleinberg提出的经典的主题提取算法HITs(Hyperlink-Induced Topic Search)。

M.R.Henzinger提出两条关于网页间超链接关系的假设，这两条假设是web结构忘挖掘的基础：

假设1：如果有一个超链接从网页A指向网页B，我们可以看做是网页A的作者提出了对网页B的推荐。

假设2：如果在网页A和网页B之间存在超链接关系，我们可以认为网页A和网页B可能存在共同主题，讨论内容相关。

PageRank算法^[10][11]

Larry Page和Sergey Brin提出了页面权威性计算算法，其中心思想是衡量一个网页是否重要，或者指向这个网页的链接多，或者指向这个网页的页面重要，或者二者兼得。

其中代表指向页面i的页面集合。表示页面j指向页面i以外的超链接数目。表示为页面j的权威度。表示为页面i的权威度。c为阻尼系数，取值在0~1之间，一般取0.85。

HITs算法^[12]

HITs算法是通过挖掘网页间超链接数据信息，找出网页中的权威性网页集合和中心网页集合。权威性网页是那些与搜索内容相关度高且较多人认同具有一定信服度的网页，这些信息也是最为用户关心的准确有效的信息；而中心网页则是那些本身所包含的信息未必有权威性和信服度，但包含很多指向权威页面的超链接的网页。算法主要通过两大步骤：1.web邻接图的构造；2.链接分析与Authority值和Hub值的计算。Authority值和Hub值的计算公式如(1.2)和(1.3)：

目前这两种算法是web结构挖掘领域较为经典的算法，同时应用于实际搜索引擎领域，PageRank算法是Google搜索引擎采用的算法，效果突出，HITs算法则在clever系统中得到了应用。世界上还有科研团体对web结构挖掘进行深入研究，通过分析网页间的超链接关系来辅助搜索，提高搜索精度是很多人的研究重点^[13]。