Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Seed sets are of significant importance for trust propagation based anti-spamming algorithms, e.g., TrustRank. Conventional approaches require manual evaluation to construct a seed set, which restricts the seed set to be small in size, since it would cost too much and may even be impossible to construct a very large seed set manually. The small-sized seed set can cause detrimental effect on the final ranking results. Thus, it is desirable to automatically expand an initial seed set to a much larger one. In this paper, we propose the first automatic seed set expansion algorithm (ASE), which expands a small seed set by selecting reputable seeds that are found and guaranteed to be reputable through a joint recommendation link structure. Experimental results on the WEBSPAM-2007 dataset show that with the same manual evaluation efforts, ASE can automatically obtain a large number of reputable seeds with high precision, thus significantly improving the performance of the baseline algorithm in terms of both reputable site promotion and spam site demotion.

REFERENCES

• 1: L. Adamic and E. Adar. Friends and neighbors on the web. Social Networks, 25(3): 211--230. 2003.
• 2: L. Becchetti, C. Castillo, D. Donatol, S. Leonardi, and R. Baeza-Yates. Using rank propagation and probabilistic counting for link-based spam detection. In Proc. of WebKDD, 2006.
• 3: A. A. Benczur, K. Csalogany, T. Sarlos, and M. Uher. SpamRank-fully automatic link spam detection. In Workshop of AIRWeb, pages 25--38, 2005.
• 4: P. Berkhin. A survey on PageRank computing. Internet Mathematics, 2(1): 73--120, 2005.
• 5: Paul-Alexandru Chirita , Jörg Diederich , Wolfgang Nejdl, MailRank: using ranking for spam detection, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099671]
• 6: Na Dai , Brian D. Davison , Xiaoguang Qi, Looking into the past to better classify web spam, Proceedings of the 5th International Workshop on Adversarial Information Retrieval on the Web, April 21-21, 2009, Madrid, Spain [doi>10.1145/1531914.1531916]
• 7: Zoltan Gyongyi , Pavel Berkhin , Hector Garcia-Molina , Jan Pedersen, Link spam detection based on mass estimation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: Z. Gyongyi, H. Garcia-Molina. Web spam taxonomy. In Workshop of AIRWeb, pages 39--47, 2005.
• 9: Zoltán Gyöngyi , Hector Garcia-Molina , Jan Pedersen, Combating web spam with trustrank, Proceedings of the Thirtieth international conference on Very large data bases, p.576-587, August 31-September 03, 2004, Toronto, Canada
• 10: 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]
• 11: Qiancheng Jiang , Lei Zhang , Yizhen Zhu , Yan Zhang, Larger is better: seed selection in link-based anti-spamming algorithms, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367658]
• 12: V. Krishnan and R. Raj. Web spam detection with anti-trust rank. In Workshop of AIRWeb, pages 37--40, 2006.
• 13: Yuting Liu , Bin Gao , Tie-Yan Liu , Ying Zhang , Zhiming Ma , Shuyuan He , Hang Li, BrowseRank: letting web users vote for page importance, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390412]
• 14: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: bringing order to the web. Technical Report, Stanford University, 1998.
• 15: Baoning Wu , Vinay Goel , Brian D. Davison, Topical TrustRank: using topicality to combat web spam, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135792]
• 16: 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]
• 17: Baoning Wu , Kumar Chellapilla, Extracting link spam using biased random walks from spam seed sets, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada [doi>10.1145/1244408.1244416]
• 18: B. N. Wu, V. Goel, and B. D. Davison. Propagating trust and distrust to demote web spam. In Proc. of MTW, 2006.
• 19: Haixuan Yang , Irwin King , Michael R. Lyu, DiffusionRank: a possible penicillin for web spamming, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277815]
• 20: B. Zhou, J. Pei, and Z. Tang. A spamicity approach to web spam detection. In Proc. of SDM, pages 24--26, 2008.
• 21: Yahoo! Research: "Web Spam Collections". http://barcelona.research.yahoo.net/WEBSPAM-2007/datasets/ Crawled by the Laboratory of Web Algorithmics, University of Milan, http://law.dsi.unimi.it/. URLs retrieved 05, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
link analysis, seed expansion, seed selection, spam, trustrank