Extracting link spam using biased random walks from spam seed sets

ABSTRACT

Link spam deliberately manipulates hyperlinks between web pages in order to unduly boost the search engine ranking of one or more target pages. Link based ranking algorithms such as PageRank, HITS, and other derivatives are especially vulnerable to link spam. Link farms and link exchanges are two common instances of link spam that produce spam communities -- i.e., clusters in the web graph. In this paper, we present a directed approach to extracting link spam communities when given one or more members of the community. In contrast to previous completely automated approaches to finding link spam, our method is specifically designed to be used interactively. Our approach starts with a small spam seed set provided by the user and simulates a random walk on the web graph. The random walk is biased to explore the local neighborhood around the seed set through the use of decay probabilities. Truncation is used to retain only the most frequently visited nodes. After termination, the nodes are sorted in decreasing order of their final probabilities and presented to the user. Experiments using manually labeled link spam data sets and random walks from a single seed domain show that the approach achieves over 95.12% precision in extracting large link farms and 80.46% precision in extracting link exchange centroids.

REFERENCES

• 1: C. Chekuri, M. H. Goldwasser, P. Raghavan, and E. Upfal. "Web search using automatic classification." In Proceedings of the 6th International World Wide Web Conference (WWW), San Jose, US, 1997.
• 2: The Word Spy - Spamdexing. http://www.wordspy.com/words/spamdexing.asp.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: http://en.wikipedia.org/wiki/Spamdexing
• 5: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 7: 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]
• 8: Z. Gyöngyi and H. Garcia-Molina. "Web spam taxonomy." In Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2005.
• 9: 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
• 10: Ye Du , Yaoyun Shi , Xin Zhao, Using spam farm to boost PageRank, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada [doi>10.1145/1244408.1244415]
• 11: H. Zhang, A. Goel, R. Govindan, K. Mason, and B. V. Roy. "Making eigenvector-based reputation systems robust to collusion." In Proceedings of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW), Rome, Italy, October 2004. Full version to appear in Internet Mathematics.
• 12: R. Baeza-Yates, C. Castillo, and V. López. "PageRank increase under different collusion topologies." In Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2005.
• 13: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 14: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 15: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 16: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 17: Reid Andersen , Kevin J. Lang, Communities from seed sets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135814]
• 18: A. A. Benczur, K. Csalogany, T. Sarlos, and M. Uher. "SpamRank - Fully automatic link spam detection." In Proceedings of the First International Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2005.
• 19: Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. "Combating web spam with TrustRank." In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, Canada, 2004.
• 20: 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]
• 21: R. Raj, V. Krishnan. "Web Spam Detection with Anti-Trust Rank." Second International Workshop on Adversarial Information Retrieval on the Web (At the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval).
• 22: 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]
• 23: BadRank as the opposite of PageRank. http://en.pr10.info/pagerank0-badrank/.
• 24: 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]
• 25: B. D. Davison. "Recognizing nepotistic links on the web." In AAAI-2000 Workshop on Artificial Intelligence for Web Search, Austin, TX, pages 23--28, July 30 2000.
• 26: Einat Amitay , David Carmel , Adam Darlow , Ronny Lempel , Aya Soffer, The connectivity sonar: detecting site functionality by structural patterns, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900060]
• 27: 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, Experimentation, Performance

Keywords:
link spam, random walks, search engine, seed sets, web spam