Article Preview
TopIntroduction
The Web has grown so big (Alpert & Hajhaj, 2008) that users cannot afford the patience to go all over it, or even through a rather small part of it. Except for their favorites sites they have to (and they do) use search engines that answer to billions of requests per day. Search engines are thus facing the issue of providing their users with good results as quick as they can, results being web pages taken from a huge index (billions of web pages) and under a tremendous load (billions of requests each day).
To ensure good results to a particular request, search engines mostly use a relevance metric for web pages and requests. Being relevant regarding a certain query does not ensure being in the first places of a search engine result list. To arbitrate between equally relevant pages, search engines have to use other metrics. One of them is popularity. Most search engines are using a popularity mechanism that is not content related. Indeed, with a popularity independent of the content of webpages, computational issues linked to ranking web pages are less prevalent. Thus, popularity often depends on the links a webpage receive from other web pages. The Google’s PageRank algorithm (Brin, Page, Motwani & Winograd, 1999) compute the popularity of all pages independently of the query while Kleinberg HITS algorithm (Kleinberg, 1999) has a query dependent version of the popularity called the authority score.
The economic model sustaining most websites is such that webmasters want their sites to appear on the first places of a search engines regarding specific requests. Indeed, the income of a website is directly correlated to unique visitors a website receives. Since search engines are the major sources of visitors on the web, to attract as many visitors as possible one has to maximize its exposure on them. Being close to the top will redirect a huge amount of traffic if the targeted request is wisely chosen.
Artificially increasing the relevance towards a request without quickly using spamming techniques and being spotted by search engines is almost impossible. Plus spammers often want to boost a legitimate page so they don’t need to manipulate its relevance. So spammers aim to increase their popularity to move to the top of the list. The most effective way to increase the popularity of a given webpage is to create a set of dull pages organized in a specific architecture whose goal is to boost the target page. This is a borderline technique, which is far beyond the guidelines of most search engines. Structures intending to maximize the pagerank of one specific page are well known (Gyongyi & Garcia-Molina, 2005). Those structures can no longer be use efficiently since it is hard for them to avoid automatic detection. Webspammers then slightly modify those structures to increase their rank while avoiding automatic detection.
There is thus a weapon race between search engines and spammers. It is really important for the first ones to deal with Webspam since it can pollute their results, then without fair results they will lose the users’ confidence and visits. Having less visitors search engines will then lose their income due to advertising and sponsored links. Fighting spam is then an economic necessity for the search engines. For spammers this is the same problem: their income is correlated to their exposure in the SERPs (Search Engines Results Pages). So each time a search engine adapts itself to lower the incidence of Webspam, they have to renew their techniques to stay one step ahead.
In this paper we present a method whose goal is to identify malicious structures amongst web pages. The intuition behind our method is that spammers use specific pages architecture to route the PageRank around the target page in order to maximize its score while avoiding automatic detection. Since the PageRank can be seen as related to the behavior of a random surfer, it seems that using random walks to reproduce the behavior of this random surfer we will be able to expose paths created by spammers in order to manipulate and increase their pagerank.
The main results of this paper are: