Combating Web Spam
with TrustRank
Seminar „Data Mining“
Von Manfred Vonderheidt
07.06.2005
Kurzer Überblick




Suchmaschinen sind leicht durch Spam zu
beeinflussen
Menschen erkennen Spam zuverlässig, sind
jedoch teuer
Ziel ist ein semiautomatischer Algorithmus
Als Testdaten dienen indizierte Seiten der
Suchmaschine AltaVista
2
Einführung

Mehrere Methoden der Spammer:




Unsichtbare Schlüsselwörter
Sehr viele Seiten, die auf eine verweisen
Und viele mehr...
Daher gibt es spezielle Mitarbeiter bei
Suchmaschinen. Diese sind teuer und
langsam, jedoch für deren Erfolg absolut
notwendig!
3
Einführung

Zwei verschiedene Anwendungsfälle:


Als Helfer in einer ersten Durchsuchung, um
Seiten vorzuschlagen, die von einem Experten
klassifiziert werden sollten oder
als Tendenzzähler bei der Bewertung der Seiten,
um mögliche Erhöhungen durch Spam-Techniken
zu neutralisieren.
4
Grundlegende Arbeitsweise
Der Algorithmus arbeitet folgendermaßen:
 Zuerst wählt er eine kleine Startmenge von
Seiten aus, deren „Spam-Status“ bewertet
werden muss.
 Ein menschlicher Experte teilt dem
Algorithmus mit, ob es sich um „gute“ oder
„schlechte“ Seiten handelt.
 Schließlich bewertet dieser andere Seiten
aufgrund ihrer Verbindungen zu den
Startseiten.
5
Modell der Netzstruktur
Anzahlder einkommend
en Links:  ( p)
Anzahlder ausgehenden Links:  (q)
wenn (q, p)
0
T ( p, q)  
1 /  (q) wenn (q, p)
0

1
T 
0

0

0 0 0

1
0 2 0
1 0 0

0 12 0 
wenn (p,q) 
0
U ( p, q)  
1 /  (q) wenn (p,q) 
 0 12 0 0 


0 0 1 0
U 

1
0 2 0 1


0 0 0 0


6
PageRank
r (q)
1
r ( p)    
 1    
N
q:( q , p )  (q )
 α ist ein Dämpfungsfaktor

Die äquivalente Matrixformel:
1
r    T  r  1     1N
N
7
Voreingenommener PageRank
r    T  r  1    d



d ist ein Vektor für eine statische
Bewertungsverteilung.
Seine Einträge sind in der Summe 1, nicht negativ
und frei wählbar.
Damit können bestimmte Seiten beliebig gewichtet
werden, welche diese Gewichtung auf andere
Seiten verteilen, auf die sie verweisen.
8
Vertrauen einschätzen

Die Beurteilung einer Seite in „gut“ oder „schlecht“
durch einen Menschen wird in der „Orakelfunktion“
formalisiert:
0 wenn p schlechtist
O( p )  
1 wenn p gut ist

Knoten 1 bis 4 würden den Wert 1 erhalten, Knoten
5 bis 7 den Wert 0.
9
Angenommene Isolation

Verweisen gute Seite auf Schlechte?



Gästebücher, Foren usw.
„Honigtöpfe“
Gilt diese Vermutung auch für Verweise von
Schlechten auf gute Seiten?

Auf „Hubs“ basierte Bewertung erhöhen?
10
Vertrauensfunktion


Die Vertrauensfunktion weist jeder Seite einen Wert
zwischen 0 (schlecht) und 1 (gut) zu.
Idealerweise gibt sie die Wahrscheinlichkeit an, ob
eine Seite gut ist.
T ( p)  Pr[O( p)  1]
11
Geordnete Vertrauenswahrscheinlichkeit
T ( p)  T (q)  Pr[O( p)  1]  Pr[O(q)  1]
T ( p)  T (q)  Pr[O( p)  1]  Pr[O(q)  1]

Ein anderer Weg ist, einen Grenzwert δ einzuführen:
T ( p)    O( p)  1
12
Bewertungsmaßstäbe
1. Paarweise Ordnung:
1 wenn T ( p )  T (q ) und O ( p )  O (q ),

I (T , O, p, q )  1 wenn T ( p )  T (q ) und O ( p )  O (q ),
0 ansonsten

pairord(T , O,  ) 
  ( p ,q ) I (T , O, p, q)

13
Bewertungsmaßstäbe
1. Precision und Recall:
prec(T , O) 
rec(T , O) 
{ p   T ( p)   und O( p)  1}
{q   T (q)   }
{ p   T ( p)   und O( p)  1}
{q   O(q)  1}
14
Vertrauen berechnen


Gegeben sind L Aufrufe der Orakelfunktion. Wir
wählen eine Startmenge δ aus L Seiten und führen
auf diese die Orakelfunktion aus. Die Untermengen
der guten und schlechten Seiten sind δ+ und δ-.
Solange eine Seite nicht von einem menschlichen
Experten überprüft wurde, erhält sie den Wert ½.
Die unwissende Vertrauensfunktion:
O( p) wenn p  ,
TO ( p)  
 1 2 ansonsten
15
Beispiel
Eine zufällige Startmenge ist {1,3,6}
Es gibt 7·6 = 42 geordnete Paare,
wobei der paarweise geordnete Rang
von T0 = 17∕21 ist.
Bei δ = ½ ist precision = 1 während recall = ½.
16
Weitergabe von Vertrauen

Wir wählen wieder eine Startmenge δ aus L, auf die wir
die Orakelfunktion anwenden. Jede von δ+ in max. M
Schritten erreichbare Seite bekommt den Rang 1. Die
Funktion TM ist definiert als:
O( p) wenn p  ,

TM ( p)  1
wenn p  und  q   : q M p,
1
 2 anonsten

Wobei q  Mp die Existenz eines Pfades der max. Länge
M von q nach p angibt, der keine schlechten Seiten
enthält!
17
Beispiel

Wieder die Startmenge δ = {1,3,6}
18
Abschwächen der Weitergabe

Vertrauensdämpfung:

Was geschieht bei mehreren Verweisen auf
eine Seite?
19
Abschwächen der Weitergabe

Vertrauen teilen:
20
Der TrustRank-Algorithmus
Funktion TrustRank
Eingaben
T Transitionsmatrix
N Anzahl der Seiten
L Max. Anzahl der Orakelaufrufe
αB Dämpfungsfaktor für den voreingenommenen
PageRank
MB Anzahl der voreingenommene PageRank Iterationen
Ausgaben
t* TrustRank Ergebnisse
21
Der TrustRank-Algorithmus
Anfang
// Die Güte der Startmenge berechnen
(1)
s = SelectSeed(...)
// Die entsprechende Ordnung erstellen
(2)
σ = Rank({1,...,N},s)
// Eine gute Startmenge auswählen
(3)
d = 0N
for i = 1 to L do
if O(σ(i)) == 1 then
d(σ(i)) = 1
22
Der TrustRank-Algorithmus
// Den Vektor für die statische Gewichtung normieren
(4)
d = d / |d|
// TrustRank-Ergebnisse berechnen
(5)
t* = d
for i = 1 to MB do
t* = αB · T · t* + (1 - αB) · d
return t*
Ende
23
Der TrustRank-Algorithmus

SelectSeed gibt z.B. den Vektor zurück:
s = [0.08, 0.13, 0.08, 0.10, 0.09, 0.06, 0.02]

Rank(x,s) erzeugt:
σ = [2, 4, 5, 1, 3, 6, 7]

Der normierte Vektor der O-Funktion mit
L=3 und der Startmenge {2,4,5}:
d = [0, ½, 0, ½, 0, 0, 0]
24
Der TrustRank-Algorithmus

Im letzten Schritt werden mit einem voreingenommenen PageRank die TrustRankErgebnisse errechnet. Für
αB = 0.85 und
MB = 20 ergibt dies:
t* = [0, 0.18, 0.12, 0.15, 0.13, 0.05, 0.05]
25
Inverser PageRank
Wie PageRank, nur werden statt der Inlinks die
Outlinks gewertet.
( p, q)     (q, p)  
Es handelt sich um eine Heuristik:
S = [0.05, 0.05, 0.04, 0.02, 0.02, 0.02, 0.02]
δ = {1,2}
26
Eine Startmenge auswählen
Funktion SelectSeed
Eingaben
U Inverse Transitionsmatrix
N Anzahl der Seiten
αB Dämpfungsfaktor
MB Anzahl der Iterationen
Ausgabe
s inverse PageRank-Bewertung
27
Eine Startmenge auswählen
Anfang
s = 1N
for i = 1 to M do
s = α · U · s + (1 – α) · 1∕N · 1N
return s
Ende
28
Hoher PageRank

Als Startmenge einfach Seiten mit einem
hohen PageRank verwenden?

Seiten mit hohem PageRank verweisen meist
auf andere Seiten mit ebenfalls hoher
Wertung.

Ist ein genauer TrustRank bei diesen Seiten
wichtiger?
29
Experimente mit echten Daten
30
PageRank versus TrustRank
31
Herabstufung durch TrustRank
32
Paarweise Ordnung
33
Precision und Recall
34
Ende
Nach eine Arbeit von Zoltán Gyöngyi,
Hector Garcia-Molina und Jan Pedersen.
Vielen Dank für Eure Aufmerksamkeit!
35

α B