TrustRank - eine Einführung

Inhaltsverzeichnis

ABBILDUNGSVERZEICHNIS

TABELLENVERZEICHNIS

ABKÜRZUNGSVERZEICHNIS

1. EINLEITUNG

2. GRUNDLAGEN
2.1 Das Web als Modell
2.2 Suchmaschinen
2.2.1 Webcrawler-System (WCS)
2.2.2 Information Retrieval System (1RS)
2.2.3 Query-Processor (QP)
2.3 Page Rank
2.4 Web Spam

3. TRUSTRANK
3.1 Bewertung von Vertrauen
3.1.1 Orakel
3.1.2 Trust-Funktion
3.2 Auswahl geeigneter Ausgangsseiten
3.3 Berechnung von Vertrauen.
3.4 Der TrustRank Algorithmus.

4. FAZIT.

LITERATURVERZEICHNIS

Abbildungsverzeichnis

Abbildung 2-1 Beispiel eines Webgraphen

Abbildung 2-2 Aufgaben einer Suchmaschine (Eigene Darstellung)

Abbildung 2-3 Basisarchitektur einer Suchmaschine (Eigene Darstellung)

Abbildung 3-1 Beispiel für einen bewerteten Webgraph

Abbildung 3-2 TrustRank-Algorithmus

Tabellenverzeichnis

Tabelle 2-1 Page Rank Berechnung für das Beispiel aus Abbildung 2-1

Tabelle 3-1 Trust Rank Berechnung für das Beispiel aus Abbildung 3-1

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Einleitung

Die Wandlung vom klassischen Web 1.0 zum Web 2.0 bildet den Rahmen dieser Ausarbeitung. Im klassischen Web 1.0 lag der Fokus auf der einfachen Nutzung von veröffentlichten Inhalten. Die Generierung und Bereitstellung von Inhalten war nur relativ wenigen Intemetnutzem Vorbehalten. Ein Grund war unter anderem die hohen Kosten^[1]. Das Web 2.0 lässt sich durch veränderte Technologien und Kosten als Kernpunkte charakterisieren. Daraus hat sich ein enorm gestiegener .Anteil an Inhalten, die von Nutzem generiert wurden, ergeben. Während 1998 noch ungefähr 3,7 Millionen^[2] Websites existierten, sind es 2008 schon ungefähr 165 Millionen^[3]. In dieser Menge von Websites agieren Suchmaschinen. Ein Beispiel dafür ist Google. Mit einem Marktanteil von ca. 90%^[4] ist Google die größte Suchmaschine Deutschlands. 1998 beantwortete Google weltweit noch 10.000^[5] und 2007 schon 200 Millionen^[6] Suchanfragen pro Tag. Nutzer versuchen ihre generierten Inhalte durch verschiedene Techniken der Suchmaschinen­Optimierung optimal zu positionieren. Suchmaschinen werden dabei oft durch so genannten Web Spam manipuliert. Insgesamt entstehen Vertrauens- und Qualitätsprobleme im Web. Aus diesen Betrachtungen ergeben sich neue Anforderungen an Suchmaschinen bezüglich der Bewertung von Webinhalten. Nutzer sollen zu einer Suchanfrage nur passende und zusätzlich vertrauensvolle Websites als Suchergebnis geliefert bekommen. Ziel dieser .Arbeit ist die Darstellung des TrustRank-Algorithmus zur Identifikation von vertrauensvollen Websites.

Kapitel 2 behandelt zunächst die wesentlichen Grundlagen zum Verständnis der Thematik. Es wird der Zusammenhang zwischen Suchmaschine, Ranking, formalem Web Modell und Web Spam dargestellt. In Kapitel 3 folgt die Herleitung der Komponenten des TrustRank­Algorithmus. Die Ausführungen werden dabei zusätzlich an einem Beispiel verdeutlicht. Abschließend enthält Kapitel 4 eine Bewertung des TrustRank-Algorithmus.

2. Grundlagen

In diesem Kapitel werden theoretische Grundlagen zum besseren Verständnis des TrustRank-Algorithmus vermittelt. Dabei wird im ersten Abschnitt eine formale Beschreibung des Web als Modell eingefuhrt^[7]. Im zweiten Abschnitt folgt die Darstellung grundlegender Eigenschaften von Suchmaschinen und deren Bedeutung für die Thematik. Der Page Rank, als spezielles Teilgebiet im Kontext von Suchmaschinen, wird in Abschnitt drei gesondert betrachtet. Die Problematik von Web Spam, als eigentlicher Hintergrund des TrustRank-Algorithmus, ist Thema von Abschnitt vier.

2.1 Das Web als Modell

Unter Web, als Kurzform für World Wide Web (WWW), versteht man einen Dienst im Rahmen des Internet.^[8] Genauer handelt es sich um „(...) ein weltweit verteiltes, öffentliches und multimediales Informationssystem im Internet, auf das über hypermediabasierte Benutzeroberflächen zugegriffen werden kann.“^[9] Dokumente im Web sind einzelne Webseiten^[10], als Teil einer Website^{[11] [12]}. Eine Website bezeichnet den gesamten Webauftritt als eine zusammengehörende Menge einzelner Webseiten und die damit verbundenen Dateien.^Grundlegendes Merkmal von Seiten „(...) ist die Möglichkeit zur Verknüpfung eines Dokuments über sogenannte Hyperlinks^[13] mit anderen Dokumenten.“^[14] Fortfolgend wird die Bezeichnung „Seite“ als Synonym für Webseite und die Bezeichnung „Link“ als Synonym für Hyperlink verwendet. Das Web lässt sich vereinfacht als gerichteter Graph modellieren^[15]. Eine Seite im Web wird durch einen Knoten im Graph repräsentiert. Ein Link ist als gerichtete Kante zwischen zwei Knoten darzustellen. Formal entsteht folgendes Modell des Webs:

Formel 1

Abbildung in dieser Leseprobe nicht enthalten

Die Menge der Knoten N und die Menge der gerichteten Kanten E bilden zusammen den Graph G. Zur Verdeutlichung ist in Abbildung 2-1 ein Beispiel aufgeführt.^[16]

Abbildung in dieser Leseprobe nicht enthalten ^[17]

Zu sehen sind sieben Seiten, die miteinander verknüpft sind. Es ergibt sich die Menge N der Knoten als NT= [1,2,3,4,5,6,7]^[18]. Die Menge E der gerichteten Kanten wird durch eine Matrix dargestellt. Es entsteht folgende binäre^[19] quadratische^[20] Matrix:

Abbildung in dieser Leseprobe nicht enthalten

Die Matrix E wurde durch folgende Eigenschaften vereinfacht:

- Seiten, die auf sich selbst verweisen werden ignoriert —> Markierung mit 0
- Mehrere gleiche Verweise zwischen zwei Seiten werden als ein Verweis betrachtet —> Markierung mit 1

Besteht ein gerichteter Link von einer Seite p zu einer Seite q, so wird die Position epq mit 1 markiert, andernfalls mit 0. Die .Anzahl der ausgehenden Links einer Seite p bilden den Ausgangsgrad^[21] [Abbildung in dieser Leseprobe nicht enthalten] von p. Die .Anzahl der eingehenden Links einer Seite p bilden den Eingangsgrad^[22] т von p. Durch diese Angaben lässt sich die .Aktivität einer Seite beurteilen. Istco(p) = 0, so handelt es sich bei p um eine nicht-referenzierende Seite. Bei [Abbildung in dieser Leseprobe nicht enthalten] ist p eine nicht-referenzierte Seite. Gilt [Abbildung in dieser Leseprobe nicht enthalten], so ist p isoliert^[23]. Mit diesen Informationen lassen sich zwei weitere Matrix-Darstellungen des Web-Graphen aufstellen. Diese Darstellungen sind fur die folgenden Ausführungen der Arbeit von zentraler Bedeutung. Man unterscheidet:

- Übergangsmatrix T

- Umgekehrte Übergangsmatrix U

Die Berechnung der Übergangsmatrix ist durch Formel 2 abgebildet.

Formel 2

Abbildung in dieser Leseprobe nicht enthalten

Mit der Matrix T werden die eingehenden Links aller Seiten bewertet^[24]. Eine Seite p erhält bei einem eingehenden Link von q den Matrixwert 1/ co(q) an der Stelle tpq. Für das Beispiel aus Abbildung 2-1 ergibt sich T als

Abbildung in dieser Leseprobe nicht enthalten

Die Berechnung von beispielsweise T(3,2) wird deutlich bei Betrachtung der Seiten zwei und drei. Seite drei erhält einen eingehenden Link von Seite zwei. Die Wahrscheinlichkeit über diesen Link zu Seite drei zu gelangen beträgt 50%, da Seite zwei daneben noch einen weiteren ausgehenden Link besitzt. Eine steigende Anzahl an ausgehenden Links der referenzierenden Seite verringert somit den Matrixwert.

Die umgekehrte Übergangs matrix U wird formal durch Formel 3 berechnet:

Abbildung in dieser Leseprobe nicht enthalten

Mit der Matrix U werden die ausgehenden Links aller Seiten bewertet. Eine Seite p erhält bei einem ausgehenden Link zu Seite q den Matrixwert l/x(q)an der Stelle tpq. Für das Beispiel aus Abbildung 2-1 ergibt sich U als:

Abbildung in dieser Leseprobe nicht enthalten

Als Beispiel kann man die Berechnung U(2,3) betrachten. Seite zwei hat einen ausgehenden Link zu Seite drei. Seite drei wird allerdings auch durch Seite sechs referenziert. Dadurch ist der Link von Seite zwei zu Seite drei nur einer von u(3) = 2 Links. Die ausgehenden Links einer Seite werden dadurch bewertet. Eine steigende Anzahl eingehender Links der referenzierten Seite verringert somit den Matrixwert.

Abschließend gelten folgende zwei Eigenschaften von T und U:

- U [Abbildung in dieser Leseprobe nicht enthalten] U ist nicht die Transponierte^[25] zu T

- U [Abbildung in dieser Leseprobe nicht enthalten] U ist nicht die Inverse^[26] von T

2.2 Suehmaschinen

Ein weiterer zentraler Punkt im Web ist die Implementierung einer Suchftmktion auf der entstehenden Informationsmenge. Suchmaschinen widmen sich dieser Aufgabe, indem sie Suchprozesse vollständig automatisieren. Der Zusammenhang zwischen Web, Suchmaschine und Nutzer ist in Abbildung 2-2 dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-2 Aufgaben einer Suehmaschine (Eigene Darstellung).

Webseiten werden in einem ersten Schritt aktiv erfasst und anschließend analysiert, aufbereitet sowie indexiert. Der dabei entstehender Index mehrerer Webseiten bezeichnet „(...) im Allgemeinen eine Abbildung von Elementen (Tokens oder Terme) dieser Dokumente (häufig von Wörtern oder Wortteilen eines Textes) auf eine Liste der Dokumente, in denen das jeweilige Token vorkommt.“^[27] Eine Suchmaschine steht in diesem Zusammenhang vor zwei zentralen Herausforderungen, die sich aus den Schnittstellen zur Außenwelt ergeben. Zum einen existieren Probleme bezüglich der Daten, die zwischen Web und Suchmaschine ausgetauscht werden, zum anderen existieren Probleme bezüglich der Kommunikation zwischen Suchmaschine und Nutzer.^[28] Nach diesen Herausforderungen richtet sich der Aufbau von Suchmaschinen. Die Basisarchitektur einer Suchmaschine ist vereinfacht in Abbildung 2-3 dargestellt ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2-3 Basisarchitektur einer Suchmaschine (Eigene Darstellung).^[29]

[...]

^[1] Kosten der Hardware, des Intemetzugangs, der Bandbreite, des Webhostings.

^[2] Vgl. [2].

^[3] Ebenda.

^[4] Vgl. [3].

^[5] Vgl. [16].

^[6] Vgl. [8].

^[7] Vgl. [4].

^[8] Vgl. [5], S. 235.

^[9] Vgl. [6], S. 514.

^[10] Auch als Seiten oder pages bezeichnet.

^[11] Auch als site bezeichnet.

^[12] Vgl. [1] und [11], S. 19.

^[13] Auch als Verweise oder Links bezeichnet.

^[14] Vgl. [7], S. 124.

^[15] Vgl. [4] und [6], S. 446.

^[16] Vgl. [4].

^[17] Ebenda.

^[18] Transponierter Vektor als Umwandlung von Spaltenvektor in Zeilenvektor zur platzsparenden Darstellung.

^[19] Matrix enthält nur die Werte 0 und 1.

^[20] Die Anzahl der Zeilen entspricht der Anzahl der Spalten (Vgl. [9], S.14).

^[21] Vgl. [9], S. 183.

^[22] Vgl. [9], S.183.

^[23] Steht mit keiner anderen Seite in Kontakt.

^[24] Beziehungsweise gewichtet

^[25] Vgl. [9], S. 15.

^[26] Vgl. [10], S. 73.

^[27] Vgl. [13], S. 41.

^[28] Siehe [14], S. 369.

^[29] In Anlehnung an [11], [12], [14].