Improvements of HITS Algorithms for Spam Links
Improvements of HITS Algorithms for Spam Links
复制标题
DOI：
10.1093/ietisy/e91-d.2.200
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Yasuhito Asano;Yuuichi Tezuka;Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Yasuhito Asano;Yuuichi Tezuka;Takao Nishizeki
Kleinberg提出的HITS算法是利用超链接对网页进行评分的代表性方法之一。在该算法提出的日子里，大多数被该算法赋予高分的页面确实与给定的主题相关，因此该算法可以用于查找相关页面。然而，由于垃圾链接的增加，Bharat和Henzinger提出的算法及其变体（包括BHITS）不能再用于在当今的Web上查找相关页面。在本文中，我们首先提出了三种方法来找到“链接农场”，即垃圾邮件链接集形成一个密集连接的子图的Web图。然后，我们提出了一个算法，称为信任分数算法，给高分的网页，这不是垃圾邮件的网页具有很高的概率。将这三种方法与信任评分算法和BHITS算法相结合，得到了HITS算法的几种变体。我们确定通过实验，其中之一，命名为TaN+BHITS使用的信任分数算法和使用名称服务器找到链接农场的方法，是最适合在今天的Web上找到相关的页面。我们的算法所需的时间和内存不超过原来的HITS算法所需的，并可以在PC上执行少量的主存储器。
The HITS algorithm proposed by Kleinberg is one of the representative methods of scoring Web pages by using hyperlinks. In the days when the algorithm was proposed, most of the pages given high score by the algorithm were really related to a given topic, and hence the algorithm could be used to find related pages. However, the algorithm and the variants including BHITS proposed by Bharat and Henzinger cannot be used to find related pages any more on today's Web, due to an increase of spam links. In this paper, we first propose three methods to find "linkfarms," that is, sets of spam links forming a densely connected subgraph of a Web graph. We then present an algorithm, called a trust-score algorithm, to give high scores to pages which are not spam pages with a high probability. Combining the three methods and the trust-score algorithm with BHITS, we obtain several variants of the HITS algorithm. We ascertain by experiments that one of them, named TaN+BHITS using the trust-score algorithm and the method of finding linkfarm by employing name servers, is most suitable for finding related pages on today's Web. Our algorithms take time and memory no more than those required by the original HITS algorithm, and can be executed on a PC with a small amount of main memory.