Tag spam creates large non-giant connected components

ABSTRACT

Spammers in social bookmarking systems try to mimick bookmarking behaviour of real users to gain the attention of other users or search engines. Several methods have been proposed for the detection of such spam, including domain-specific features (like URL terms) or similarity of users to previously identified spammers. However, as shown in our previous work, it is possible to identify a large fraction of spam users based on purely structural features. The hypergraph connecting documents, users, and tags can be decomposed into connected components, and any large, but non-giant components turned out to be almost entirely inhabitated by spam users in the examined dataset. Here, we test to what degree the decomposition of the complete hypergraph is really necessary, examining the component structure of the induced user/document and user/tag graphs. While the user/tag graph's connectivity does not help in classifying spammers, the user/document graph's connectivity is already highly informative. It can however be augmented with connectivity information from the hypergraph. In our view, spam detection based on structural features, like the one proposed here, requires complex adaptation strategies from spammers and may complement other, more traditional detection approaches.

REFERENCES

• 1: P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17--61, 1960.
• 2: A. Gkanogiannis and T. Kalamboukis. A novel supervised learning algorithm and its use for spam detection in social bookmarking systems. In ECML PKDD Discovery Challenge 2008 (RSDC'08), 2008.
• 3: Paul Heymann , Georgia Koutrika , Hector Garcia-Molina, Fighting Spam on Social Web Sites: A Survey of Approaches and Future Challenges, IEEE Internet Computing, v.11 n.6, p.36-45, November 2007 [doi>10.1109/MIC.2007.125]
• 4: A. Hotho, D. Benz, R. Jäschke, and B. Krause, editors. ECML PKDD Discovery Challenge 2008 (RSDC'08). Workshop at 18th Europ. Conf. on Machine Learning (ECML'08) / 11th Europ. Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD'08), 2008.
• 5: Beate Krause , Christoph Schmitz , Andreas Hotho , Gerd Stumme, The anti-social tagger: detecting spam in social bookmarking systems, Proceedings of the 4th international workshop on Adversarial information retrieval on the web, April 22-22, 2008, Beijing, China [doi>10.1145/1451983.1451998]
• 6: Mary McGlohon , Leman Akoglu , Christos Faloutsos, Weighted graphs and disconnected components: patterns and a generator, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401955]
• 7: N. Neubauer and K. Obermayer. Predicting tag spam examining cooccurrences, network structures and url components. In ECML PKDD Discovery Challenge 2008 (RSDC'08), 2008.
• 8: N. Neubauer and K. Obermayer. Hyperincident components of tagging networks (submitted). In HyperText 2009, Proceedings of, 2009.
• 9: Knowledge Discovery and Data Engineering Group, University of Kassel. Benchmark folksonomy data from bibsonomy, version of june 30th, 2008.
• 10: E. Santos-Neto, M. Ripeanu, and A. Iamnitchi. Tracking usage in collaborative tagging communities.
• 11: R. Wetzker, C. Zimmermann, and C. Bauckhage. Analyzing social bookmarking systems: A del.icio.us cookbook. In Mining Social Data (MSoDa) Workshop Proceedings, ECAI 2008, pages 26--30, 2008.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Keywords:
connected components, spam detection, tagging