互联网社区核及完整社区提取策略

论文摘要

大连理工大学硕士学位论文摘要Web是现代人类共享数据和信息最重要的平台。挖掘Web自身的特性对理解和获得Web上的信息是至关重要的。Web最引人瞩目的特性在于它的自组织性：与同一主题相关的页面通过超链接紧密连接,在结构上体现为Web图上的稠密子图,又被称作社区。Web社区被定义为一组由兴趣小组创建的主题相关的页面集合。社区信息对Web研究是非常有价值：首先,社区反映了Web用户的社会行为、Web的演化历史以及Web上不同主题的相互联系；其次,社区是Web上中粒度的信息单元,为用户提供了关于一个主题最可靠的信息资源；在此,社区体现了Web上主题分布的特征,是利用Web结构信息提高Web搜索效率最有效的途径；最后,对Web自组织性的深入认识,结合语义Web的开发,可以使明天的Web更好地为人类服务。因此,能够自动识别并组织这些社区在分析Web的复杂结构中充当着重要的角色。此外,这些社区会大大地改善互联网用户获得信息的途径及效率。Web社区结构可以由稠密二分子图来表征。每一个Web社区都至少会包含一个社区核。一个社区核是一个完全二分图。为了克服现在社区核发现技术存在的参数难以确定的缺陷,本文基于组合合并技术,提出了一种新的社区核提取算法—C&C(Combination and consolidation)。实验表明该算法相对于现有算法,能更有效地提取社区核。首先,可以提取出Web中所有潜在的最大二分核；其次,提取所有不同大小的社区核只需要执行一次算法即可；此外,该算法不需要用户指定参数。基于已有的社区核,本文又提出了两步启发式策略从这些社区核获得完整的社区。首先,通过合并重叠的社区核获得社区的一个大致轮廓；其次,通过扩展包含被高度引用的结点逐步完善社区。真实数据集上的实验表明,最终得到的结果社区满足：社区成员之间的链接紧密；社区间链接稀疏。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 论文组织结构
• 2 信息检索及Web数据挖掘相关研究
• 2.1 信息检索
• 2.1.1 信息检索概述
• 2.1.2 Web信息处理
• 2.1.3 信息检索评价
• 2.2 Web数据挖掘
• 2.2.1 Web数据挖掘综述
• 2.2.2 Web数据挖掘分类
• 2.2.3 Web数据挖掘在搜索中的应用
• 2.3 链接分析
• 2.3.1 链接分析的必要性
• 2.3.2 超链接的结构特征
• 2.3.3 Web的宏观介绍
• 2.3.4 链接分析模型
• 2.4 社区发现
• 2.4.1 社区的定量定义
• 2.4.2 社区识别算法
• 2.4.3 社区发现算法
• 2.4.4 社区相关技术分析
• 3 C&C社区发现算法
• 3.1 提取单位核
• 3.2 合并单位核
• 4 从社区核到社区
• 4.1 勾勒雏形社区
• 4.2 完善社区结构
• 4.3 人工数据集分析
• 5 算法平台设计及分析
• 5.1 实验设计流程
• 5.2 实验平台及数据预处理
• 5.2.1 数据预处理
• 5.2.2 数据结构
• 5.3 Trawling算法实验设计
• 5.4 社区核发现算法C&C的实验结果及分析
• 5.5 社区核到社区的实验结果及分析
• 5.6 评价最终社区
• 5.6.1 社区主题相关性
• 5.6.2 社区的传导率
• 5.6.3 社区的模块度
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢