反搜索引擎作弊中种子集合自动扩展算法研究

摘要

随着搜索引擎和万维网的飞速发展，快速增长的网络信息在供人们分享和获取的同时，也催生了大量的搜索引擎作弊行为。搜索引擎作弊是指利用各种手段欺骗搜索引擎排序算法，从而让一些页面获得比它们应得的页面排名更靠前的排名。搜索引擎作弊会造成增加搜索服务提供商的运营成本，降低用户使用搜索引擎的满意程度等问题。
　　 传统的基于启发式规则的反作弊算法难以广泛的对抗搜索引擎作弊行为，而且容易被作弊者攻破。基于信任传播的反作弊算法对作弊者的攻击具有较高的鲁棒性，能广泛的抵抗作弊行为。但由于这类反作弊算法有效性依赖于可信的种子节点，因此种子节点集合的数量和质量会约束算法在抵抗作弊行为上的效率。传统的获取种子集合的方法依赖于人工评测。这不仅从成本上限制了种子集合不会太大，而且难以保证选取的种子节点的质量。因此，如何选取或扩展种子节点集合来满足基于信任传播反作弊算法的需要，成为了反搜索引擎作弊算法中值得研究的问题。
　　 本文提出的ASE算法(Automatic Seed Expansion)，引入了节点间的可信支持度的概念，并结合领域知识和网络节点共引用的拓扑结构，能够将一个小规模的种子节点集合扩展成为一个大规模的，高质量的，具有较小领域偏向性的种子节点集合，从而满足了基于信任传播的反作弊算法的对种子节点集合质量和数量的需要。同时，本文还进一步分析了如何为ASE算法选取初始的小规模种子节点集合，分别给出了适用于不同情况的两个启发式算法combineSelection和thresholdSeleetion，并分析了它们的算法效率和优缺点。在WEBSPAM-2007数据集上的实验证明了应用ASE的TrustRank排序算法与原始TrustRank算法相比在可信节点提升和作弊节点降级的效率上分别提高了27.2％和49.5％，显示了ASE在提高反作弊算法在抵抗作弊行为上的有效性。

目录

文摘

英文文摘

声明

1 绪论

1.1选题背景与意义

1.1.1搜索引擎作弊的背景知识

1.1.2搜索引擎作弊的危害

1.1.3搜索引擎作弊的特点

1.2研究动机

1.3主要工作

1.4文章的组织结构

2相关工作

2.1搜索引擎基础

2.1.1 搜索引擎主要组成部分

2.1.2网络拓扑结构表示

2.2搜索排序常用算法

2.2.1 TF/IDF

2.2.2 向量空间模型

2.2.3 PageRank算法

2.2.4 HITS算法

2.3搜索引擎作弊

2.3.1基于内容的作弊

2.3.2基于链接结构的作弊

2.3.3其他的常见作弊方法

2.4常见反搜索引擎作弊算法

3种子节点集合自动扩展算法ASE

3.1 种子节点集合在TrustRank算法中的影响

3.1.1 可信节点的数量影响

3.1.2领域偏向性影响

3.1.3从可信节点到作弊节点的影响

3.2 ASE算法的直观解释

3.3 ASE算法的描述与分析

3.4初始种子节点选择算法

3.4.1基于入链出链结合的方法

3.4.2基于类似二分图的方法

3.4.3算法适用性和效率分析

4实验与结果分析

4.1实验说明和参数设定

4.2 ASE算法节点扩展数量实验与分析

4.3 ASE算法节点扩展质量实验与分析

4.4 ASE算法节点领域偏向性实验与分析

4.5 ASE算法同基线算法的对比实验与分析

4.5.1 可信节点提升的对比实验与结果分析

4.5.2作弊节点降级的对比实验与结果分析

4.5.3初始节点降级的对比实验与结果分析

4.5.4作弊节点提升的对比实验与结果分析

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢