A large-scale study of link spam detection by graph algorithms
A large-scale study of link spam detection by graph algorithms
复制标题
DOI：
10.1145/1244408.1244417
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
Hiroo Saito;Masashi Toyoda;M. Kitsuregawa;K. Aihara
中科院分区：
文献类型：
--
作者：
Hiroo Saito;Masashi Toyoda;M. Kitsuregawa;K. Aihara
链接垃圾邮件是指试图通过欺骗搜索引擎中基于链接的排名算法来提升垃圾邮件发送者网站的排名。垃圾邮件发送者经常创建密集连接的站点的链接结构，即所谓的“链接场”。在这篇文章中，我们研究了拥有580万个站点和2.83亿个链接的日本Web的大规模图表中链接农场的总体结构和分布。为了检查垃圾邮件的结构，我们将三种图算法应用到Web图中。首先，将Web图分解为强连通分量(SCC)。除了网络中心最大的SCC(核心)外，我们还观察到大多数大型组件由链接场组成。接下来，为了提取核心中的垃圾站点，我们列举了最大团作为链接农场的种子。最后，我们通过最小割技术将垃圾站点和非垃圾站点之间的链接分离出来，将这些链接场扩展为可靠的垃圾邮件种子集。我们在核心周围的SCC中发现了约60万个垃圾站点，并通过最大团枚举法和最小割法分别高精度地在核心中额外提取了8000个和4.9万个垃圾站点。
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.