A large-scale study of link spam detection by graph algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A large-scale study of link spam detection by graph algorithms

Full text

Pdf (126 KB)

Source

AIRWeb; Vol. 215 archive
Proceedings of the 3rd international workshop on Adversarial information retrieval on the web table of contents

Banff, Alberta, Canada

SESSION: Link farms table of contents

Pages: 45 - 48

Year of Publication: 2007

ISBN:978-1-59593-732-2

Authors

Hiroo Saito	Aihara Complexity Modelling Project, ERATO, JST, Tokyo, Japan and University of Tokyo, Tokyo, Japan
Masashi Toyoda	University of Tokyo, Tokyo, Japan
Masaru Kitsuregawa	University of Tokyo, Tokyo, Japan
Kazuyuki Aihara	Aihara Complexity Modelling Project, ERATO, JST, Tokyo, Japan and University of Tokyo, Tokyo, Japan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 59, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1244408.1244417 What is a DOI?

ABSTRACT

Link spam refers to attempts to promote the ranking of spammers' web sites by deceiving link-based ranking algorithms in search engines. Spammers often create densely connected link structure of sites so called "link farm". In this paper, we study the overall structure and distribution of link farms in a large-scale graph of the Japanese Web with 5.8 million sites and 283 million links. To examine the spam structure, we apply three graph algorithms to the web graph. First, the web graph is decomposed into strongly connected components (SCC). Beside the largest SCC (core) in the center of the web, we have observed that most of large components consist of link farms. Next, to extract spam sites in the core, we enumerate maximal cliques as seeds of link farms. Finally, we expand these link farms as a reliable spam seed set by a minimum cut technique that separates links among spam and non-spam sites. We found about 0.6 million spam sites in SCCs around the core, and extracted additional 8 thousand and 49 thousand sites as spams with high precision in the core by the maximal clique enumeration and by the minimum cut technique, respectively.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Becchetti, C. Castillo, and D. Donato. Link-based characterization and detection of web spam. In Proc. of AIRWEB 2006, Seattle, 2006.
	2	L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. Baeza-Yates. Using rank propagation and probabilistic counting for link-based spam detetection. In Proc. of KDD 2006, Philadelphia, Pennsylvania, 2006.
	3	A. Benczúr, K. Csalogány, and T. Sarlós. Link-based similarity search to fight web spam. In Proc. of AIRWEB 2006, Seattle, 2006.
	4	A. Benczúr, K. Csalogány, T. Sarlós, and M. Uher. Spamrank -- fully automatic link spam detection. In Proc. of AIRWEB 2005, Chiba, 2005.
	5	Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
	6	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]
	7	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
	8	Z. Gyöngyi and H. Garcia-Molina. Web spam taxonomy. In Proc. of AIRWEB 2005, Chiba, 2005.
	9	Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In Proc. of VLDB 2004, Toronto, 2004.
	10	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]
	11	V. Krishnan and R. Raj. Web spam detection with anti-trust rank. In Proc. of AIRWEB 2006, Seattle, 2006.
	12	K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. In SWAT 2004, Humlebaek, 2004.
	13	P. T. Metaxas and J. DeStefano. Web spam, propaganda and trust. In Proc. of AIRWEB 2005, Chiba, 2005.
	14	Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
	15	T. Ono, M. Toyoda, and M. Kitsuregawa. An examination of techniques for identifying web spam by link analysis. In Proc. of DEWS 2006, Tokyo, 2006.
	16	L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, 1998.
	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]

CITED BY 2

	Carlos Castillo , Kumar Chellapilla , Brian D. Davison, Adversarial Information Retrieval on the Web (AIRWeb 2007), ACM SIGIR Forum, v.42 n.1, June 2008
	Young-joo Chung , Masashi Toyoda , Masaru Kitsuregawa, A study of link farm distribution and evolution using a time series of web snapshots, Proceedings of the 5th International Workshop on Adversarial Information Retrieval on the Web, April 21-21, 2009, Madrid, Spain