Web Marshals Fighting Curly Link Farms

Graphides cincinnatae (also known as circulant graphs) Ci n (L) of n vertices are studied here as link farms in the Web, built automatically by a spammer to promote visibility of a page T. These graphs are k-consecutive, denoted by Ci n,k , if each vertex v i is connected to v i + j and v i − j with j = 1,2,...,k. Graphides cirratae are cincinnatae with some irregularities. We discuss how to fight this phenomenon with a set of Web marshals, that is autonomous agents that visit the farm for cutting the links to T. The farm reacts reconstructing the links through majority voting among its pages. We prove upper and lower bounds on the number of marshals, and of link hops, needed to dismantle the farm. We consider both synchronous and asynchronous operations.