基于链接相似度的Web社区发现算法研究

论文摘要

Web在发展过程中存在着大量的社区,这些社区是Web组织中非常重要的信息,反映了Web中普遍存在的、复杂的聚团关系和层次关系,可以为用户提供可靠、及时的信息。人工发现和维护社区成本较高,修改困难,而且还存在着许多无法通过人工来发现的潜在的社区。因此,许多研究都在致力于社区的自动或半自动发现技术。链接分析是发现Web潜在社区的重要方法。本文分析了Web链接结构的特点,研究了传统最大流算法和基于HITS算法的边容量分配的最大流算法。重点研究了传统最大流算法和基于HITS的边容量分配最大流算法在社区挖掘中存在的问题。传统最大流算法虽然能较好地解决主题漂移问题,但对社区的质量带来许多不利的影响。而基于HITS的边容量分配算法采用以两个节点的中心值和权威值的平均值作为边容量,就是针对传统最大流存在的问题的,但仍然存在不足。本文在分析已有的链接相似度定义基础上,提出了新的链接相似度与主题相异度定义,以更好地描述链接的页面间关系,并根据链接相似度和主题相异度来衡量页面的相似性,从而给出了更合理有效的最大流边容量分配方案。网页的相似性与链接相似度成正比,与主题相异度成反比;网页之间的相似程度越高,相应边分配的边容量越大。通过24个主题的社区发现表明本文提出的利用链接相似度和主题相异度模型分配边容量的最大流算法能较好的解决已有算法存在的问题,显著提高了Web社区质量。本文对页面相似度衡量提出了新的方法和思路,为改进基于链接分析的Web社区发现算法提供了新的策略。因此,本文的研究具有一定的理论和实践意义。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 课题研究意义
• 1.4 本文结构
• 2 Web资源挖掘及技术
• 2.1 Web挖掘分类
• 2.1.1 Web内容挖掘
• 2.1.2 Web结构挖掘
• 2.1.3 Web使用挖掘
• 2.2 Web挖掘步骤
• 2.3 Web挖掘在搜索引擎中的应用
• 2.3.1 Web内容挖掘在搜索引擎中的应用
• 2.3.2 Web结构挖掘在搜索引擎中的应用
• 2.3.3 Web日志挖掘在搜索引擎中的应用
• 2.4 Web挖掘的前景
• 3 Web的超链接分析和Web社区发现算法研究
• 3.1 Web的超链接分析
• 3.1.1 超链接节点的度的分布
• 3.1.2 超链接节点对的平均最短距离
• 3.1.3 超链接节点的聚集系数
• 3.1.4 基于超链接分析的Web拓扑结构
• 3.1.5 Web超链接结构的形成
• 3.2 Web社区发现算法研究
• 3.2.1 基于HITS算法的Web社区发现
• 3.2.2 基于二分有向图的Web社区发现
• 3.2.3 基于最大流的社区发现
• 4 基于相似度的最大流社区发现算法
• 4.1 最大流算法
• 4.2 原始最大流社区发现算法存在的问题
• 4.3 基于HITS的最大流的社区发现算法缺点
• 4.4 相似度的定义
• 4.5 原始超链接相似度介绍
• 4.5.1 利用两个网页最短路径的长度计算相似度
• 4.5.2 利用共同祖先计算相似度
• 4.5.3 利用共同子孙计算相似度
• 4.5.4 完整的链接相似度计算
• 4.5.5 原始链接相似度的缺点
• 4.6 改进的链接相似度
• 4.7 主题相异度
• 4.7.1 编辑距离
• 4.7.2 计算距离
• 4.7.3 主题相异度
• 4.8 基于相似度的边的容量计算
• 4.9 改进的最大流发现社区算法
• 5 实验和评价
• 5.1 实验体系结构
• 5.2 开发环境
• 5.3 构建Web图
• 5.4 实验结果分析
• 结论
• 参考文献
• 附录A 核心代码
• 攻读硕士学位期间发表学术论文情况
• 致谢