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
g1
Nodi Good
inlink good = 2
inlink spam = 4
s4
Nodi Spam
Approccio Naive Base:
funziona?
s1
g0
x
s2
g1
=
s3
s4
PageRank(x) = (6c + 1)(1 - c)/n
Contributo g0, g1 = c(1-c)/n
Contributo s1, s2, s3, s4 = c(1-c)/n
Approccio Naive Base:
funziona davvero?
s1
g0
x
s0
s2
g1
inlink good = 2
inlink spam = 1
Nodi Good
Ma… ?!?
sk
Nodi Spam
Approccio Naive Base:
funziona davvero?
s1
g0
x
s0
s2
g1
sk
PageRank(x) = (1 + 3c + kc2)(1 - c)/n
Contributo g0, g1 = c(1-c)/n
Contributo s0 = (c+kc2)(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
Contributo g0, g1 = c(1-c)/n
Contributo s0 = (c+kc2)(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
Variante 1 Naive:
funziona davvero?
s1
s2
g0
s0
x
s5
g1
?
g3
s3
g2
s4
s6
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 [(1c)/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.
Uso di Ṽ
3.
Si considerano:




+
(good-core). Molto più stabile di Ṽ
–
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:
•
•
•
2.
p
p’
m = (p - p’)/p  vettore degli spam mass
relativi approssimati
Per ogni nodo il cui PageRank è >= ρ
a)
b)
se lo spam mass relativo approssimato del nodo
è >= t, il nodo viene etichettato come spam
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



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!!!