基于链接分析的Web社区发现技术研究

摘要

WWW已经成为一个巨大的、分布广泛的全球信息服务中心，且以惊人的速度在不断扩大。目前Web上数据具有海量和无组织等特征，如何快速、有效地利用Web上的数据成为研究热点。Web中存在大量的社区，这些社区是Web组织中非常重要的信息。社区可以为用户提供有价值的、及时的信息。社区反映了Web中普遍存在的复杂聚团关系和层次关系，对社区的深入研究可以了解Web中知识信息及其组织结构的发展状况。可将Web社区发现算法应用于搜索引擎有助于提高Web信息搜索的精确度，进而实现垂直搜索引擎。
　　Web页面间的链接关系为Web社区发现研究提供了极其丰富的信息线索。链接分析是Web社区发现主要技术之一。
　　本文在分析当前Web及其数据特征、Web社区的定义、链接分析技术、Web拓扑结构模型等理论基础上，对基于链接分析的Web社区发现技术：基于重要度分析的PageRank算法、基于共引用与共耦合关系的HITS算法、基于有向二分图的Trawling算法、基于流量的算法进行了详细的分析。并重点研究了基于共引用与共耦合关系的HITS算法实现过程及其在社区发现中存在的问题针对HITS算法本身只考虑Web页面间超链接而忽略Web页面内容信息，对链接不加区分，对所有的链接赋予相等权重，结果常常把与主题无关的页面赋予较高的权重，导致了社区结果网页出现了主题漂移现象。本文提出了基于链接价值度和页面语义主题相似度的改进HITS算法，该算法将链接权威度和页面语义主题相似度这两个不同角度的属性融合到链接权重分配中，突出了链接的差异性。从而极大地减少了主题漂移现象，提高了查询的效率和质量。
　　本文最后提出了验证算法的有效性实验方案并设计了一个Web社区发现系统，该系统利用本文提出的改进算法进行了Web社区发现。经过大量实验证明，本文提出的改进算法能够进一步提高所发现Web社区的质量，具有重要的理论和实际应用价值。

目录

独创性声明

学位论文使用授权声明

目录

1 前言

1.1 课题研究背景、目的与意义

1.1.1 课题研究背景

1.1.2 课题研究目的与意义

1.2 课题研究现状

1.2.1 国外发展现状

1.2.2 国内发展现状

1.3 课题主要研究内容

2 链接分析及基于链接分析的Web社区发现技术

2.1 链接分析的理论基础

2.1.1 链接分析的思想起源

2.1.2 链接分析及其Web图表示

2.1.3 链接和引文分析的异同

2.1.4 链接的类型

2.1.5 链接的应用

2.2 基于链接分析的Web宏观拓扑建模

2.2.1 链接节点度的分布

2.2.2 网络的小世界特性和无标度特性

2.3 社区与Web链接结构的研究

2.4 基于链接分析的Web社区发现技术

2.4.1 基于重要度分析的PageRank算法

2.4.2 基于共引用与共耦合关系的HITS算法

2.4.3 基于有向二分图的Trawling算法

2.4.4 基于流量的算法

2.5 本章小结

3 相关的基于共引用与共耦合关系的算法分析

3.1 HITS算法分析

3.2 HITS的改进算法

3.2.1 ARC算法

3.2.2 Monika R.Henzinger和Krishna Bharat对HITS的改进

3.3 本章小结

4 基于链接权威度和页面语义主题相似度的HITS改进算法

4.1 链接价值度

4.2 页面语义主题相似度

4.3 改进的算法描述

4.4 本章小结

5 实验及评价

5.1 评价方法

5.2 实验系统设计

5.2.1 系统设计目标

5.2.2 系统结构

5.3 系统实现

5.3.1 开发环境与工具

5.3.2 核心模块实现

5.3.3 系统界面

5.4 实验结果比对

5.5 本章小结

6 总结与展望

6.1 论文总结

6.2 展望

致谢

参考文献

硕士期间发表论文及获奖情况