Link analysis for Web spam detection

ABSTRACT

We propose link-based techniques for automatic detection of Web spam, a term referring to pages which use deceptive techniques to obtain undeservedly high scores in search engines. The use of Web spam is widespread and difficult to solve, mostly due to the large size of the Web which means that, in practice, many algorithms are infeasible.

We perform a statistical analysis of a large collection of Web pages. In particular, we compute statistics of the links in the vicinity of every Web page applying rank propagation and probabilistic counting over the entire Web graph in a scalable way. These statistical features are used to build Web spam classifiers which only consider the link structure of the Web, regardless of page contents. We then present a study of the performance of each of the classifiers alone, as well as their combined performance, by testing them over a large collection of Web link spam. After tenfold cross-validation, our best classifiers have a performance comparable to that of state-of-the-art spam classifiers that use content attributes, but are orthogonal to content-based methods.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: Ralitsa Angelova , Gerhard Weikum, Graph-based text classification: learn from your neighbors, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148254]
• 3: Ricardo Baeza-Yates , Paolo Boldi , Carlos Castillo, Generalizing PageRank: damping functions for link-based ranking algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148225]
• 4: Baeza-Yates, R., Castillo, C., and López, V. 2005. Pagerank increase under different collusion topologies. In 1st International Workshop on Adversarial Information Retrieval on the Web.
• 5: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: Becchetti, L., Castillo, C., Donato, D., Leonardi, S., and Baeza-Yates, R. 2006a. Link-based characterization and detection of Web Spam. In 2nd International Workshop on Adversarial Information Retrieval on the Web (AIRWeb). Seattle, WA.
• 7: Becchetti, L., Castillo, C., Donato, D., Leonardi, S., and Baeza-Yates, R. 2006b. Using rank propagation and probabilistic counting for link-based spam detection. In Proceedings of the Workshop on Web Mining and Web Usage Analysis (WebKDD). ACM Press.
• 8: Benczúr, A. A., Csalogány, K., Sarlós, T., and Uher, M. 2005. Spamrank: Fully automatic link spam detection. In Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web. Chiba, Japan.
• 9: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 10: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 11: Broder, A. and Mitzenmacher, M. 2003. Network applications of Bloom filters: A survey. Internet Math. 1, 4, 485--509.
• 12: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 13: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 14: Carlos Castillo , Debora Donato , Aristides Gionis , Vanessa Murdock , Fabrizio Silvestri, Know your neighbors: web spam detection using the web topology, 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.1277814]
• 15: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 16: Costa, L., Rodrigues, F. A., Travieso, G., and Villas. 2005. Characterization of complex networks: A survey of measurements. URL: http://arxiv.org/abs/cond-mat/0505185.
• 17: André Luiz da Costa Carvalho , Paul - Alexandru Chirita , Edleno Silva de Moura , Pável Calado , Wolfgang Nejdl, Site level noise removal for search engines, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135793]
• 18: Davison, B. D. 2000a. Recognizing nepotistic links on the Web. In Artificial Intelligence for Web Search. AAAI Press, TX, 23--28.
• 19: Brian D. Davison, Topical locality in the Web, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.272-279, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345597]
• 20: Camil Demetrescu , Irene Finocchi , Andrea Ribichini, Trading off space for passes in graph streaming problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.714-723, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109635]
• 21: Drost, I. and Scheffer, T. 2005. Thwarting the nigritude ultramarine: learning to identify link spam. In Proceedings of the 16th European Conference on Machine Learning (ECML). Lecture Notes in Artificial Intelligence, vol. 3720. Springer, 233--243.
• 22: Durand, M. and Flajolet, P. 2003. Loglog counting of large cardinalities (extended abstract). In Proceedings of 11th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2832. Springer, 605--617.
• 23: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 24: Feigenbaum, J., Kannan, S., Gregor, M. A., Suri, S., and Zhang, J. 2004. On graph problems in a semi-streaming model. In 31st International Colloquium on Automata, Languages and Programming.
• 25: 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]
• 26: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 27: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 28: Gomes, L. H., Almeida, R. B., Bettencourt, L. M. A., Almeida, V., and Almeida, J. M. 2005. Comparative graph theoretical characterization of networks of spam and legitimate email. URL: http://www.ceas.cc/papers-2005/131.pdf.
• 29: Marco Gori , Ian Witten, The bubble of web visibility, Communications of the ACM, v.48 n.3, March 2005 [doi>10.1145/1047671.1047715]
• 30: A. Gulli , A. Signorini, The indexable web is more than 11.5 billion 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.1062789]
• 31: Gupta, S., Anderson, R. M., and May, R. M. 1989. Networks of sexual contacts: implications for the pattern of spread of hiv. AIDS 3, 12, 807--817.
• 32: 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
• 33: Gyöngyi, Z. and Garcia-Molina, H. 2005. Web spam taxonomy. In Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web.
• 34: 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
• 35: Haveliwala, T. 1999. Efficient computation of pagerank. Tech. rep., Stanford University.
• 36: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 37: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 38: R. J. Lipton , J. F. Naughton, Estimating the size of generalized transitive closures, Proceedings of the 15th international conference on Very large data bases, p.165-171, July 1989, Amsterdam, The Netherlands
• 39: Lu, Q. and Getoor, L. 2003. Link-based classification. In Proceedings of the International Conference on Machine Learning.
• 40: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 41: Robert Morris, Counting large numbers of events in small registers, Communications of the ACM, v.21 n.10, p.840-842, Oct. 1978 [doi>10.1145/359619.359627]
• 42: Alexandros Ntoulas , Marc Najork , Mark Manasse , Dennis Fetterly, Detecting spam web pages through content analysis, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135794]
• 43: Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank citation ranking: bringing order to the Web. Tech. rep., Stanford Digital Library Technologies Project.
• 44: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 45: Perkins, A. 2001. The classification of search engine spam. http://www.silverdisc.co.uk/articles/spam-classification/.
• 46: Xiaoguang Qi , Brian D. Davison, Knowing a web page by the company it keeps, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183650]
• 47: Guoyang Shen , Bin Gao , Tie-Yan Liu , Guang Feng , Shiji Song , Hang Li, Detecting Link Spam Using Temporal Information, Proceedings of the Sixth International Conference on Data Mining, p.1049-1053, December 18-22, 2006 [doi>10.1109/ICDM.2006.51]
• 48: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 49: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 50: 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]
• 51: Zhang, H., Goel, A., Govindan, R., Mason, K., and Van Roy, B. 2004. Making eigenvector-based reputation systems robust to collusion. In Proceedings of the 3rd Workshop on Web Graphs (WAW). Lecture Notes in Computer Science, vol. 3243. Springer, 92--104.
• 52: Tong Zhang , Alexandrin Popescul , Byron Dom, Linear prediction models with graph regularization for web-page categorization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150510]

INDEX TERMS

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

General Terms:
Algorithms, Measurement

Keywords:
Link analysis, adversarial information retrieval