Countering web spam with credibility-based link analysis

ABSTRACT

We introduce the concept of link credibility, identify the conflation of page quality and link credibility in popular Web link analysis algorithms, and discuss how to decouple link credibility from page quality. Our credibility-based link analysis exhibits three distinct features. First, we develop several techniques for semi-automatically assessing link credibility for all Web pages. Second, our link credibility assignment algorithms allow users to assess credibility in a personalized manner. Third, we develop a novel credibility-based Web ranking algorithm - CredibleRank - which incorporates credibility information directly into the quality assessment of each page on the Web. Our experimental study shows that our approach is significantly and consistently more spam-resilient than both PageRank and TrustRank.

REFERENCES

• 1: R. Baeza-Yates, C. Castillo, and V. Lopez. PageRank increase under different collusion topologies. In AIRWeb, 2005.
• 2: A. A. Benczur et al. SpamRank - fully automatic link spam detection. In AIRWeb, 2005.
• 3: Thomas Beth , Malte Borcherding , Birgit Klein, Valuation of Trust in Open Networks, Proceedings of the Third European Symposium on Research in Computer Security, p.3-18, November 07-09, 1994
• 4: B. Davison. Recognizing nepotistic links on the Web. In Workshop on AI for Web Search, 2000.
• 5: D. Fetterly, M. Manasse, and M. Najork. Spam, damn spam, and statistics. In WebDB, 2004.
• 6: D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel PageRank: A linear system approach. Technical report, Yahoo!, 2004.
• 7: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 8: 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
• 9: Z. Gyöngyi and H. Garcia-Molina. Web spam taxonomy. In AIRWeb, 2005.
• 10: 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
• 11: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 12: S. D. Kamvar et al. Exploiting the block structure of the Web for computing PageRank. Technical report, Stanford, 2003.
• 13: 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]
• 14: L. Page et al. The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford, 1998.
• 15: Xuanhui Wang , Azadeh Shakery , Tao Tao, Dirichlet PageRank, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076178]
• 16: Yuan Wang , David J. DeWitt, Computing pagerank in a distributed internet search system, Proceedings of the Thirtieth international conference on Very large data bases, p.420-431, August 31-September 03, 2004, Toronto, Canada
• 17: 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]
• 18: B. Wu, V. Goel, and B. Davison. Propagating trust and distrust to demote web spam. In Models of Trust for the Web (MTW), 2006.
• 19: 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]
• 20: PeerTrust: Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.843-857, July 2004 [doi>10.1109/TKDE.2004.1318566]
• 21: H. Zhang et al. Improving eigenvector-based reputation systems against collusions. In Algorithms and Models for the Web Graph, 2004.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

General Terms:
Algorithms, Experimentation

Keywords:
PageRank, credibility, link analysis, spam, web algorithms