（一种限制性标记传播的反链接作弊方法#牟南，张宪超，梁文新**（大连理工大学软件学院，辽宁大连116600）5101520摘要：从种子集合出发向整个互联网传播信任值和作弊值标记的方法已被广泛运用于发现搜索引擎链接作弊这一领域，并取得了一定成效。然而，这类方法仍然存在值得改进之处。其中最重要的一点是，这种传播是不加限制的，即信任值标记可以传播到作弊网站，作弊值标记也可能传播到正常网站。本文提出了一种对标记进行限制性传播的方法，根据由种子集合发现的作弊社区群信息对标记的传播加以限制。实验结果表明限制性标记传播的方法在反链接作弊中能够比一般的标记传播方法取得更好的效果。关键词：信息检索；链接作弊；标记传播；社区发现：G354CombatingLinkSpamUsingLimitedLabelPropagationMOUNan,ZHANGXianchao,LIANGWenxin(SchoolofSoftware,DalianUniversityofTechnology,LiaoNingDaLian116600)Abstract:Thetechniqueofpropagatingtrustanddistrustlabelsfromexistinggoodandspamseedstotheentirewebgraphhasbeenwidelyusedincombatingwebspam.However,thereisstillmuchspaceforimprovement.Oneimportantissueisthatthepropagationisnotlimited,namelyspamsitescangettrustlabelsandnormalsitescanalsogetdistrustlabels.Inthispaper,anintegratedframeworklimitingthepropagationprocessisproposed.Thelimitsareaddedaccordingtospamcommunitiesextractedfromtheseedset.Experimentalresultsshowthatthelimitedalgorithmsoutperformsthebaselinesforspamdemotiontaskes.Keywords:informationretrieval;linkspam;labelpropagation;communityrecognition250引言随着互联网技术的发展，人们每天都在接触海量的信息。其中，获取信息最直接的方式就是使用搜索引擎。通常情况下，搜索引擎的使用者只对排名在最前面的若干结果感兴趣。这意味着在搜索结果中具有较高的排名将为网站带来更多的访问量，而更多的访问量通常意303540味着网站的所有者能够得到更大的收益。因此，在商业利益的驱动下，采用非道德的方式使网站获得本不应该得到的较高排名的行为开始萌芽。这种伪造排名的行为被称为“作弊行为”。发生在搜索引擎中的作弊行为叫做“搜索引擎作弊”[1]。在过去的几年中，对于搜索引擎反作弊的研究已经有了很大的进展。专家们提出了各种方法和技术，其中一种具有代表性的方法就是标记传播的方法。已有的标记传播的反作弊方法，例如TrustRank[2]和Anti-TrustRank[3]算法，其核心思想是从种子集合出发，将信任标记沿着链接的方向，作弊标记沿着链接相反的方向传播到整个网络。由于知名网站很少有链接指向作弊网站，使用这类标记传播的方法可以使得作弊网站得到很低的信任值。然而，作弊者可能使用大量低分值的作弊页面堆砌出一个相对较高得分的目标页面，同时，该页面的作弊值也不会很高，因为该页面链向很少或者根本不链向其他的作弊页面。这种情况下，基于信任值/作弊值标记传播的方法就不能有效地发现作弊网站。在本文中，我们提出一种更有效的反作弊方法。我们注意到，作弊者的目标页面通常被基金项目：教育部博士点基金（20120041110046）；高等学校博士学科点专项科研基金（新教师类）项目（20100041120033）作者简介：牟南，（1988-），男，硕士研究生，主要研究方向：搜索引擎反作弊。通信联系人：张宪超，1971-），男，教授，博士生导师，主要研究方向：数据挖掘。E-mail:xczhang@dlut.edu-1-大量其他的作弊网页所指向，这一部分作弊网页通常在内部是紧密相连的。因此，把这些作弊网页看做一个社区是合理的。我们使用Anderson等人于2006年提出的方法[4]，从一些作弊页面组成的种子集出发，寻找一定数量的由作弊页面组成的社区。在信任值/作弊值标记4550传播的阶段，我们对于跨越社区边界的传播进行限制。这样，作弊者的目标页面的得分将会间接减少。1限制性标记传播1.1传统标记传播方法及其缺陷传统的标记传播方法的共同点是，将专家对于部分网页的人工评测结果（可信任或作弊）作为初始种子集合信息，然后通过链接或者反向链接在整个互联网上传播。Gyongyi等人在...