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.

Web Marshals Fighting Curly Link Farms

LUCCIO, FABRIZIO;PAGLI, LINDA
2007

Abstract

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.
9783540729136
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/196032
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact