Link Spam Alliances
di Zoltàn Gyöngyi
Hector Garcia-Molina
Stanford University
Computer Science Department
Presentazione a cura del gruppo 7:
Cristian Caruso
Matteo Degli Esposti
Claudia Fontan
Relatore: Claudia Fontan
Sistemi Informativi LS
a.a. 2005-06
Outline
“Conosci il tuo nemico;
Conoscilo e l’avrai per metà vinto.”
(Confucio)
 Introduzione al web spam
 Formulazione del PageRank
 Studio delle Spam Farm:
 Analisi di una singola Farm
 Alleanze tra due Farm
 Caso multi-Farm
 Spam detection
Link Spam Alliances - gruppo 7
2
Spam: perché?
 L’uso di motori di ricerca per rintracciare indirizzi Internet
è sempre più diffuso [FMN]
 Assicurarsi un ranking alto coincide con l’aumentare le
proprie entrate
 Nel periodo aprile-giugno 2005 negli USA le vendite tramite
eCommerce hanno rappresentato il 2.2% del totale (941.282
milioni di dollari) [USC]
…e se non si è ai primi posti
si cerca di “plasmare” i risultati…
Link Spam Alliances - gruppo 7
3
Spam: definizione
Spamming: ingannare i motori di ricerca per ottenere un
ranking più elevato di quanto ci si meriti in realtà
Lo spamming è dannoso [NAJ]
 Per gli utenti
 Rende più difficile trovare le informazioni desiderate
 Scoraggia l’utente
 Per i motori di ricerca
 Spreca la banda del crawler
 Inquina la rete con pagine di spam
 Distorce il ranking reale dei risultati
Link Spam Alliances - gruppo 7
4
Link Spam
Link Spam: si costruiscono strutture di pagine interconnesse
per aumentare il PageRank di uno o più target
Link Spam Alliances - gruppo 7
5
PageRank
PageRank della pagina p0:
link uscenti da pi
p0 = cΣipi/|F(i)| + (1-c)
Generalizzando:
damping
factor
PageRank di
pi che punta a p0
random jump
(1
–
c)
1N
p = cT’p +
N
matrice di
transizione
 Una pagina è importante se è puntata da tante altre
pagine importanti
 Essendo basato sulla struttura dei collegamenti, l’algoritmo del
PageRank può essere vulnerabile al Link Spamming
Link Spam Alliances - gruppo 7
6
Spam Farm: pagine
p1
p2
pk
λ1
λ2
λk
λ0
?
p0
 Target page
 Ogni Farm ne ha una sola
 L’obiettivo dello spammer è
aumentare il suo ranking
 Boosting pages
 Sono controllate dallo spammer
 Puntano al target per aumentare
il suo PageRank
Link Spam Alliances - gruppo 7
7
Spam Farm: link esterni
p1
p2
pk
λ1
λ2
λ0
?
p0
λk
 Leakage
 PageRank aggiunto al target da pagine
al di fuori della Farm (forum, blog, …)
 Lo spammer non ne ha il controllo
 λ = λ0 + … + λk
Link Spam Alliances - gruppo 7
8
Optimal Farm
 Intuitivo
 Ottimale
 Ogni boosting page punta
unicamente al target
 Il target punta alle boosting
pages
(1 – c)(ck + 1)
cλ
p0 = +
N
p1
λ
p2
p0
q0 = p0 / (1 – c2)
Intuitivamente:
q1 target e boosting pages
q2
si rinforzanoλ
a vicenda
q2
q0
qk
pk
qk
Link Spam Alliances - gruppo 7
q1
9
Alleanze tra due Farm
 Intuitivo
 Economico
 Ogni boosting page punta
ad entrambi i target
p0
p1
q0
p2
pk
q1
q2
 (k + m) nuovi link
qm
 Si interconnettono
unicamente i target
p0
p1
q0
p2
pk
q1
q2
qm
 solo 2 nuovi link
 Redistribuzione del PageRank
q0 = p0 = d(k + m)/2 [d = c/N(1 + c)]
 conveniente per la Farm più piccola
Link Spam Alliances - gruppo 7
10
Alleanze tra due Farm
 Ottimo
 Ogni target punta all’altro target
 I target non hanno link alle boosting pages
p1
q1
p0
q0
Intuitivamente:
p2
q2
questo modello risulta vincente
perché concentra tutto il PageRank
qm
pk
sui target minimizzando quello
delle boosting pages
 Incremento del PageRank
ck + c2m 1
p0 =
+
(1 + c)N
N
 conveniente per entrambe le Farm
Link Spam Alliances - gruppo 7
11
Alleanze multi-Farm
 Due strutture fondamentali:
 Web ring
 Complete core
p1
r1
r2
rn
r0
p0
q0
p2
q1
q2
core
qm
pk
Link Spam Alliances - gruppo 7
12
Web ring
 Modalità di connessione più semplice ed intuitiva
1
ck + c2m + c3n
p0 =
+
(1 + c + c2)N
N
r1
p1
r2
rn
r0
p0
q0
 la distanza influenza
il contributo di ogni
Farm al PageRank
delle altre
q1
p2
q2
pk
qm
Link Spam Alliances - gruppo 7
13
Complete core
 Il core è un sotto-grafo completamente connesso
1
2ck – c2k + c2m + c2n
p0 =
+
(2 + c)N
N
r1
r2
rn  il contributo di ogni
Farm al PageRank
delle altre è uniforme
p1
r0
p0
q0
q1
p2
q2
pk
qm
Link Spam Alliances - gruppo 7
14
Riassumendo
Web ring:
Il PageRank del target della
Farm 10 diminuisce rispetto al
caso di non connessione
6000
Scaled Target Page Rank
5000
4000
Complete core:
3000
aumentano
tutti i PageRank,
soprattutto quelli dei target delle
Farm di minori dimensioni
Single Farm
Web Ring
Complete Core
2000
Farm non connesse:
il PageRank del target è lineare
nella dimensione della Farm
(numero di boosting pages)
1000
0
1
2
3
4
5
6
7
8
9
10
Farm Number
Link Spam Alliances - gruppo 7
15
Riassumendo
 Contributo della Farm 1 agli altri target
200
Page Rank Contribution
180
160
140
120
100
Complete core:
si conserva la maggiorparte del
PageRank, agli altri target viene
dato un identico contributo molto
minore
Complete Core
Web Ring
80
60
40
20
Web ring:
i valori 0dei contributi sono vicini
tra
loro 1 e 2 diminuiscono
3
4
5
6
all’aumentare della distanza
7
8
9
10
Farm Number
Link Spam Alliances - gruppo 7
16
Entrare in un’alleanza
 Web ring
 Perchè p0 accetti r0 in un’alleanza con q0 organizzata secondo la
struttura del Web ring è necessario rispettare le seguenti
condizioni:
PR(alleanza p, q, r) > PR(alleanza p, q)
ck + c2m
ck + c2m + c3n
>
(1 + c)N
(1 + c + c2)N
n>
k + cm
(1 + c)
 Le dimensioni delle Farm già presenti determinano la dimensione
minima che deve avere una Farm per essere accettata
 La media pesata delle dimensioni delle Farm già presenti
costituisce un lower bound sulla dimensione della nuova Farm
 Es: k = 20; m = 10:
 Con FL a q  n = 16
 Il punto di inserimento della Farm
entrante ne influenza la dimensione
minima
Link Spam Alliances - gruppo 7
17
Entrare in un’alleanza
 Complete core
 Perchè p0 accetti r0 in un’alleanza con q0 organizzata secondo la
struttura del Complete core è necessario rispettare le seguenti
condizioni:
PR(alleanza p, q, r) > PR(alleanza p, q)
 La dimensione minima che deve avere una Farm per essere
accettata è determinata considerando la Farm più piccola già
presente nell’alleanza:
n>
k + m – (1 – c)min{k, m}
(1 + c)
n>
arithmetic
mean
 La media aritmetica delle dimensioni delle Farm già presenti
costituisce un lower bound sulla dimensione della nuova Farm
 Es: k = 20; m = 10
 n = 16 per m; n = 15 per k  media aritmetica = 15
 La terza Farm deve avere almeno 16 boosting pages
Link Spam Alliances - gruppo 7
18
Lasciare un’alleanza
 Prima abbiamo osservato che:
PR(10, non connessa) > PR(10, ring)
 Intuizione: la Farm 10 contribuisce troppo al PageRank dei suoi
alleati e riceve troppo poco in cambio
 Web ring
 La Farm p0 decide di lasciare l’alleanza se:
PR(non connessa) > PR(ring)
ck + 1
1
ck + c2m + c3n
(1 + c)N > (1 + c + c2)N + N
2) - cn(1 - c2)
c
m(1
c
k >
(1 - c)
 Nell’alleanza tra 10 Farm, risulta che il limite per la Farm 10 è 9091 
avendo 10000 boosting pages, le conviene uscire dall’alleanza
Link Spam Alliances - gruppo 7
19
Lasciare un’alleanza
 Complete core
 La Farm p0 decide di lasciare l’alleanza se:
PR(non connessa) > PR(complete core)
ck + 1
1
2ck – c2k + c2m + c2n
+
(1 + c)N >
(2 + c)N
N
k > 2 + c + (1 + 2c)(k + m + n)
7c
 Contributi distribuiti in modo più uniforme rispetto al Web ring
 Piccole differenze tra i limiti di dimensione per le diverse Farm
 Nell’alleanza tra 10 Farm, risulta che nessuna raggiunge la
dimensione limite  a tutte conviene restare nell’alleanza
Link Spam Alliances - gruppo 7
20
Spam detection
Idea di base: identificare strutture come quelle descritte in
precedenza
Obiettivo: determinate potenziali candidati per il link
spamming
 Zipfian distribution
 Amplification factor
 Spam mass
Link Spam Alliances - gruppo 7
21
Zipfian distribution
 Fetterly et al., 2004
 Le Farm sono spesso generate automaticamente ed hanno
strutture molto regolari
 Si analizzano i gradi di entrata ed uscita delle pagine
 Molte pagine seguono la distribuzione di Zipfian
p1
λ
p2
pk
p0
 Agglomerati di pagine i cui gradi
di ingresso ed uscita seguono
questa distribuzione in modo
esatto risultano spesso essere
parte di una Farm
ZD(p) = |F(1)| = |F(2)| = … = |F(k)|
ZD(p) = |B(1)| = |B(2)| = … = |B(k)|
Link Spam Alliances - gruppo 7
22
Amplification factor
 Zhang et al., 2004
 Una caratteristica comune delle Farm è la capacità dei target di
catturare il PageRank proveniente dalle boosting pages
 I target amplificano il contributo delle boosting pages
p1
p0
q0
p2
pk
q1
q2
colluding
pages
qm
 Amplification factor Amp(H):
in un gruppo di H pagine, è il
rapporto tra il PageRank delle
pagine nel gruppo ed il
contributo di quelle esterne
 Se Amp(H) è dell’ordine di
1/(1–c), le pagine del gruppo
possono essere target di Farm
connesse in un’alleanza
p0 + q0
1
=O 1-c
Σi pi + Σj qj
Link Spam Alliances - gruppo 7
23
Spam mass
 Zyöngyi et Garcia-Molina, 2005
 I target aumentano il proprio PageRank soprattutto grazie alle
boosting pages
 Il PageRank delle boosting pages è dovuto al random jump
 Relative spam mass Mass(i): relativo alla
λ
pagina i, è il rapporto tra PageRank totale e
PageRank con apporto del random jump
p0
posto a 0:
1-c p1
1-c p2
1-c pk
p0 – p’0
p0
0 p1
0 p2
0 pk
p0 = PageRank totale
p’0 = PageRank parziale
λ  Per pagine che non hanno grandi
p’0
benefici da boosting pages,
Mass(i) tende a 0
 Se Mass(i) è elevato, la pagina i
è probabilmente un target
all’interno di una Farm
Link Spam Alliances - gruppo 7
24
Conclusioni
 Le tecniche di Spam Detection presentate sono ancora
sperimentali
 Riescono spesso ad identificare solo il core di un’alleanza
 Possono risultare utili, ma presentano ancora problemi
 La tecnica riguardante la distribuzione di Zipfian non identifica
strutture non regolari
 La tecnica dell’Amplification factor identifica come alleanze di
Farm anche gruppi di pagine che non lo sono
 La tecnica basata sulla Spam Mass non identifica target che
aumentano il proprio PageRank soprattutto grazie al leakage
 Il primo passo per combattere realmente il Link Spam è
conoscere a fondo le strutture proprie di questa tecnica
 Il percorso che porta ad individuare tecniche realmente
efficaci per combattere il Link Spamming è comunque ancora
molto lungo…
Link Spam Alliances - gruppo 7
25
Riferimenti
[FMN] “Spam, Damn Spam, and Statistics”, Dennis Fetterly, Mark
Manasse, Mark Najork, 2004.
research.microsoft.com/research/sv/PageTurner/webdb2004.pdf
[GGM] “Link spam alliances” Technical Report, Stanford University,
2005.
infolab.stanford.edu/~zoltan/publications.html
[NAJ] “Heuristics for Detecting Spam Web Pages”, Mark Najork –
Microsoft Research, Silicon Valley, 2005.
www.cise.ufl.edu/~adobra/DaMn/talks/2005-10-26-Bertinoro.ppt
[USC] U.S. Census Bureau, E-Stats
www.census.gov/eos/www/ebusiness614.htm
Link Spam Alliances - gruppo 7
26
Demo
…and now…
WE WANT YOU
see our
Link Spam Alliances - gruppo 7
27