Sessione di conferenza 1
Gruppo 6
Link Spam Detection
Based on Mass Estimation
di:
Zoltan Gyongyi
Hector Garcia-Molina
Pavel Berking
Jan Pederson
Relatore: Cristina Valent
Presentazione di:
Cristina Valent
Elisa Silenzi
Fabrizio Pinto
Sommario






Cenni storici
Obiettivi
Soluzioni iniziali
Spam Detection Algorithm
Caso di studio
Conclusioni
Un po’ di storia…
Fin dagli inizi di Internet sono state applicate tecniche
di web spamming per influenzare maliziosamente il
ranking:
1.
Agli albori  term spamming
•
2.
Farcire le pagine con parole chiave spesso non inerenti
al contenuto
Al giorno d’oggi  link spamming
•
•
•
Insiemi di pagine intercorrelate tra loro, per alterare a
proprio vantaggio il loro PageRank
Si è diffusa enormemente in seguito all’affermazione
del PageRank come tecnica di ranking
Costruzione delle spam farms da parte degli spammer
Obiettivi
Contrastare il link spamming, calcolando un
PageRank corretto e trascurando i
contributi delle spam farm
Concetti di
riferimento (1)

Modello del web:
•
•
•
•

Grafo orientato senza autoanelli
Nodi: Pagine, Host, Siti
Inlink  archi entranti in un dato nodo
Outlink  archi uscenti da un dato nodo
Spam Farm
• Gruppo di nodi interconnessi che linkano un singolo nodo
target con l'obiettivo di incrementare il PageRank di
quest'ultimo
• Più spam farm si possono alleare ed avere più nodi target
Concetti di
riferimento (2)

Stray link
Link da nodi autorevoli che vengono coinvolti
inconsapevolmente nel link spamming da parte degli
spammer stessi
Possono esistere per diverse ragioni:
• spammer pubblicizza un commento che include un
link spam in un sito autorevole (blog, bacheca, …)
• honey pot. Pagina che contiene informazioni utili,
ma è comunque coinvolta nella spam farm
• acquisto di domini popolari scaduti di recente
Assunzioni di base

Partizione dei nodi web:
•
•


V
V
+
–
= { nodi buoni }
= { nodi spam }
Conoscenza a priori della tipologia
dei nodi vicini
c  fattore di riduzione usato nel calcolo del
PageRank (damping factor)
Legenda:
 e = 1-c
 c = 1-e
 out(y)  n° outlink di y
 A  insieme degli archi
py
1 c
px  c 

n
( y , x )A out ( y )
Approccio Naive Base
Idea base:
Considerare la tipologia degli inlink diretti di un nodo,
etichettando quest’ultimo a maggioranza
Procedimento:
1.
2.
3.
4.
si sceglie il nodo x
si considerano i nodi degli inlink diretti di x
si contano quanti nodi appartengono alle due
tipologie (buoni/spam)
si assegna al nodo x l’etichetta prevalente
Approccio Naive Base:
funziona?
s1
g0
x
?
s2
=
s3
inlink good = 2
inlink spam = 4
PageRank(x) = (6c + 1)(1 - c)/n
g1
Contributo g0, Nodi
g1 = c(1-c)/n
Good
s4
Contributo s1, s2, sNodi
c(1-c)/n
3, s4 =Spam
Approccio Naive Base:
funziona davvero?
s1
g0
x
?
s0
s2
g1
inlink good = 2
sk
inlink spam = 1
PageRank(x) = (1 + 3c + kc2)(1 - c)/n
Nodi Good
Ma… ?!?
Contributo g0, g1 = c(1-c)/n
2
Spam
Contributo sNodi
0 = (c+kc )(1-c)/n
Per questo viene usato solo come primo schema di “labeling”
Approccio Naive:
variante 1
Come prima:
Considerare:

inlink diretti al nodo

numero degli inlink diretti al nodo
Idea di base nuova:
Considerare anche il contributo PageRank degli inlink
diretti.
Variante 1 Naive:
funziona?
s1
g0
x
?
s0
s2
g1
sk
PageRank(x) = (1 + 3c + kc2)(1 - c)/n
Nodi Good
Contributo g0, g1 = c(1-c)/n
2
Spam
Contributo sNodi
0 = (c+kc )(1-c)/n
Variante 1 Naive:
funziona davvero?
s1
s2
g0
s0
x
s5
g1
?
g3
s3
g2
s4
s6
PageRank(x) = (1 + 3c + 8c2)(1 - c)/n
Contributo g0 + g2 = (2c+4c2)(1-c)/n
Contributo s0 = (c+4c2)(1-c)/n
Problema: guarda solo gli inlink diretti.
Soluzione: guardare anche quelli indiretti.
Problemi comuni

Conoscenza a priori dei nodi buoni e di
quelli spam:
•
•
•
non disponibile
difficile da produrre
tende a diventare datata in breve tempo
Spam Detection
Algorithm
Concetti base:
 PageRank Contribution
 PageRank Score
 Spam Mass:
assoluto
 relativo

PageRank Contribution
Definizione PageRank Contribution:
Si introduce il concetto di:
 cammino (walk) da x a y
 contributo del PageRank lungo il cammino
 considerazione degli inlink indiretti
Da notare:
 il contributo di un nodo a se stesso è pari alla
probabilità di “saltare” casualmente su quel nodo
[(1-c)/n]
 in assenza di un cammino da x a y, il contributo di x
su y, in termini di PageRank, è nullo
PageRank Score &
Spam Mass
Definizione PageRank Score:
Il PageRank Score di un nodo y è la somma dei
contributi di tutti gli altri nodi (collegati
direttamente o indirettamente) nei confronti di y.
Definizione Spam Mass:
E’ la misura dell’impatto del link spamming sul
PageRank dei nodi
• Assoluto : misura di quanto i nodi spam incrementano il
PageRank del nodo considerato
• Relativo : è la frazione di PageRank del nodo considerato
dovuto al contributo dei nodi spam
(spam mass assoluto / PageRank del nodo considerato)
Nuove Assunzioni
1.
Uso di approssimazioni:
Ṽ + : approssimazione dell’insieme dei nodi good
–
 Ṽ : approssimazione dell’insieme dei nodi spam
Deve essere disponibile almeno uno dei 2 sottoinsiemi

2.
3.
Uso di Ṽ + (good-core). Molto più stabile di Ṽ
Si considerano:
–
p : vettore dei PageRank Score normale
 p’ : vettore dei PageRank Score calcolato sulla base
di Ṽ +
 t : soglia di confronto con lo spam mass relativo
approssimato (m). Se m è superiore il nodo viene
etichettato come spam
 ρ : soglia di confronto con il PageRank (PR). Se PR è
inferiore il nodo non viene considerato

Spam
Detection Algorithm
Procedimento:
1.
Si calcolano i vettori:
•
p
•
p’
•
m = (p - p’)/p  vettore degli spam mass
relativi approssimati
2.
Per ogni nodo il cui PageRank è >= ρ
a) se lo spam mass relativo approssimato del
nodo è >= t, il nodo viene etichettato come
spam
b) altrimenti si passa al nodo successivo
Spam Detection:
Oh…
funziona?
yeah!!
s1
s2
g0
s0
x
s5
g1
?
Ṽ
g3
s3
g2
s4
s6
V
+
+
Spam Mass Relativo di x
m(x) = (p(x) – p’Ṽ+(x)) / p(x)
PageRank(x) beneficia parecchio del contributo dei nodi spam
link spamming in corso!!!!
Caso Yahoo!



Considerati 73,3 milioni di host distinti estrapolati
dagli indici di Yahoo! del 2004
Composizione good core:
– host di una web directory ritenuta affidabile
– host governativi USA
– host di istituti scolastici di più di 150 paesi
Dimensione finale del good core poco più di
500.000 host distinti
Caso Yahoo!:
valutazione algoritmo

Calcolo degli spam mass relativi

Filtraggio dei PageRank con uso di una soglia ρ pari
a 10
 Host risultanti circa 900.000 (insieme T)

Selezione di un insieme campione pari allo 0,1% di
T che vengono:
– verificati manualmente
– suddivisi in 20 gruppi in base allo spam mass
relativo
Caso Yahoo!:
composizione campione
Caso Yahoo!:
precisione algoritmo (1)
Precisione
rapporto tra:
 il numero di host
valutati
manualmente
come spam
 il numero di host
considerati spam
dall’algoritmo
Caso Yahoo!:
precisione algoritmo (2)
Osservazioni

Il Good Core deve:
• essere di dimensione opportuna
• offrire una buona copertura dello scenario web da valutare
(rappresentativo)

Spam mass relativo vs assoluto
Alcuni host molto popolari e autorevoli possono avere uno
spam mass assoluto elevato (contributo dei nodi spam),
ma questo valore è trascurabile se rapportato al loro
PageRank.
Quindi lo spam mass relativo permette di pesare meglio i
contributi dei nodi spam.
Alt... Attenzione!!!
Fare attenzione a:
 comunità isolate che ricevono uno spam
mass positivo dal:
– reciproco ed elevato link tra i partecipanti
– basso numero di inlink esterni
Esempio: Warcraft fans

acquisizione da parte degli spammer di
domini popolari scaduti di recente
NON CONSIDERATI DALL’ALGORITMO
Conclusioni



Algoritmo si basa sullo spam mass. Facile da
calcolare
Con il minimo sforzo è capace di identificare
parecchie decine di migliaia di link spam host
E’ robusto rispetto all’intervento degli spammer che
dovrebbero manipolare in maniera non ovvia il
grafo dei nodi good
Manipolazione impossibile senza conoscenza dell’insieme dei
nodi good in input all’algoritmo

Ottimo per la gestione di strutture link irregolari
Grazie
per
l’attenzione!!!