Using spam farm to boost PageRank

ABSTRACT

Nowadays web spamming has emerged to take the economic advantage of high search rankings and threatened the accuracy and fairness of those rankings. Understanding spamming techniques is essential for evaluating the strength and weakness of a ranking algorithm, and for fighting against web spamming. In this paper, we identify the optimal spam farm structure under some realistic assumptions in the single target spam farm model. Our result extends the optimal spam farm claimed by Gyöngyi and Garcia-Molina through dropping the assumption that leakage is constant. We also characterize the optimal spam farms under additional constraints, which the spammer may deploy to disguise the spam farm by deviating from the unconstrained optimal structure.

REFERENCES

• 1: T. Sarls A. Benczr, K. Csalogny and M. Uher. Spamrank - fully automatic link spam detection. In Proc. Int'l Workshop Adversarial Information Retrieval on the Web, 2005.
• 2: David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs. www.stat.berkeley.edu/aldous/RWG/book.html.
• 3: Monica Bianchini , Marco Gori , Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.92-128, February 2005 [doi>10.1145/1052934.1052938]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: Alice Cheng and Eric Friedman. Manipulability of pagerank under sybil strategies. 2006. First Workshop on the Economics of Networked Systems.
• 6: Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, and D. Sivakumar. Link evolution: Analysis and algorithms. Internet Mathematics, 1(3):277--304, 2003.
• 7: Dennis Fetterly , Mark Manasse , Marc Najork, Spam, damn spam, and statistics: using statistical analysis to locate spam web pages, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017077]
• 8: Zoltán Gyöngyi , Hector Garcia-Molina, Link spam alliances, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: Zoltan Gyongi , Hector Garcia-Molina, Spam: It's Not Just for Inboxes Anymore, Computer, v.38 n.10, p.28-34, October 2005 [doi>10.1109/MC.2005.352]
• 10: Zoltán Gyöngyi and Hector Garcia-Molina. Web spam taxonomy. In First International Workshop on Adversarial Information Retrieval on the Web, 2005.
• 11: Zoltán Gyöngyi, Hector Garcia-Molina, and Jan Pedersen. Combating web spam with TrustRank. In Proceedings of the 30th International Conference on Very Large Databases, pages 576--587. Morgan Kaufmann, 2004.
• 12: Monika R. Henzinger , Rajeev Motwani , Craig Silverstein, Challenges in web search engines, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792553]
• 13: John G. Kemeny and J Laurie Snell. Finite markov chains, 1960. D. Van Nostrand Company.
• 14: A. Langville and C. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--380, 2005.
• 15: Andrew Y. Ng, Alice X. Zheng, and Michael I. Jordan. Link analysis, eigenvectors and stability. In IJCAI, pages 903--910, 2001.
• 16: Ignacio Palacios-Huerta and Oscar Volij. The measurement of intellectual influence. Econometrica, 72(3):963--977, 2004.
• 17: Tina Liu Sibel Adali and Malik Magdon-Ismail. Optimal link bombs are uncoordinated. In Proceeding of AIRWeb, 2005.
• 18: Baoning Wu , Brian D. Davison, Identifying link farm spam pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062762]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Theory

Keywords:
Markov chain, PageRank algorithm, link spamming