Formalization of Link Farm Structure Using Graph Grammar

A link farm is a set of web pages constructed to mislead the importance of target pages in search engine results by boosting their link-based ranking scores. In this paper, we introduce a new graph grammar model for expressing the structure of a link farm. Supervised graph grammar induction created by an expert is modified to fit the training data to explain the behavior and the properties of link farms. In the experiments, graph grammar can effectively recognize link farms from Yahoo´s web spam dataset. The comparison among the number of applying production rules of spam and normal hosts indicates that graph grammar seem to be a good mechanism for detecting link spam.