7. Vorlesung - users.informatik.uni-halle.deusers.informatik.uni-halle.de/~hinnebur/Lehre/IR_WS06_web/IR_WS06_7.pdfWS 2006/07 Alexander Hinneburg, Martin-Luther-Universität Halle/Wittenberg

WS 2006/07 Alexander Hinneburg,Martin-Luther-Universität Halle/Wittenberg

Seite 179

7. Vorlesung

• Bipartite Kerne• Das kopierende Modell• Bow-tie Struktur des Web• Random Sampling von Web Seiten


Seite 180

Web als ein Soziales Netzwerk

Small-world Netzwerk:• Niedriger (Durchschnitts) Durchmesser• Hoher Clustering Koeffizient

vViele Nachbarn von v sind auch selbstNachbarn.

Grund: Web besteht aus Communities.


Seite 181

Cyber Communities• Cyber Community:

– Eine Gruppe von Menschen, die ein gemeinsamesInteresse teilen.

– Web-Seiten, die von diesen Menschen erzeugt/zitiertwerden.

• Beispiele– Große Autohersteller– Ölverschmutzung an Japans Küste– Britney Spears Fans


Seite 182

Struktur von Cyber Communities [Kumar et al, 1999]

• Hubs: Resourcen für das von der Community geteiltem Interesse– Beispiele:

• Yahoo! Autos• Ölverschmutzung in der Nähe von Japan: bookmarks• Donna’s Britney Spears Links

• Authorities: Zentrale Seiten für das von derCommunity geteiltem Interesse– Beispiele:

• Mazda.com• Britney Spears: The official site


Seite 183

Dichte Bipartite Subgraphen

• Hubs– Zitieren viele Autoritäten– Haben überlappende Zitate

• Autoritäten– Werden von vielen Hubs zitiert– Oft zusammen zitiert

• Deshalb: eine Cyber Community wird durch einen dichtengerichteten bipartiten Subgraphencharakterisiert.

Hubs Autoritäten


Seite 184

Bipartite Kerne

• (i,j)-Bipartiter Kern: (H’,A’)– H’: Teilmenge von H der Größe i– A’: Teilmenge von A der Größe j– Subgraph induziert auf (H’,A’) ist ein

vollständiger bipartiter Graph

• Hypothese: Die “meisten” dichten bipartitenTeilgraphen des Webs haben Kerne.

• Deshalb: bipartite Kerne sindFingerabdrücke von Cyber Communities.

H A


Seite 185

Finden von Cyber Communities

• Bipartite Kerne können effizient durch einenCrawl gefunden werden

• Das Web hat eine Vielfalt von Cyber Communities– Etwa 200k disjunkte (3,*)-Kerne in einem 1996 crawl– Crawl hatte ~200M Seiten– Für einen zufälligen Graphen dieser Größe ist es

unwahrscheinliche auch nur einen (3,3) Kern zuenthalten!


Seite 186

Das kopierende Modell[Kleinberg et al 1999] [Kumar et al 2000]

• Initialisierung: Ein Knoten• Entwicklung: In jedem Schritt wird ein neuer

Knoten v hinzugefügt. v verbindet sich zu dNachbarn mit ausgehenden Kanten.

• Prototyp Auswahl: v wählt einen zufälligenKnoten u aus dem Graph.

• Bernoulli Kopieren: Für alle i = 1,…,d, – v wirft Münze mit Wahrscheinlichkeit α für Kopf– Falls Kopf, v verbindet sich zu zufälligem Knoten– Falls Zahl, v verbindet sich zum i-ten Nachbarn von u


Seite 187

Das kopierende Modell : Motivation

• Wenn eine neue Seite erstellt wird, hat derAutor ein “Thema” im Kopf

• Autor wählt Links von einem “Prototyp” u über das Thema

• Autor fügt durch das Einfügen von zufälligen Links eigene Ideen hinzu.


Seite 188

Das kopierende Modell: Gradverteilung

• Falls α = 0, dann ist der i-te Nachbar von v derKnoten u’ mit Wahrscheinlichkeit indeg(u’)/Σwindeg(w)– Identisch zum Modell der bevorzugten Verbindung– Im Grenzwert ist der Anteil der Seiten mit Eingangsgrad

k die Wahrscheinlichkeit 1/k2.• Für beliebige α

– Anteil der Seiten mit Eingangsgrad k ist 1/k(2-α)/(1 - α)


Seite 189

Erdős-Rényi Zufallsgraphen: Bipartite Kerne

• Gn,p mit p = d/n– Für feste A,B ⊆ Gn,p, |A| = i, |B| =j– Wahrscheinlichkeit daß A,B einen kompleten bipartite

graph bilden:

– # solcher Paare A,B:

– Erwartete # (i,j)-bipartiter Kerne ist höchstens


Seite 193

Bow Tie Struktur des Web[Broder et al 2000]


Seite 194

Random Samplingvon

Web Seiten


Seite 195

Überblick

• Problem Definition• Random sampling von Web Seiten

bezüglich ihres PageRank• Uniform Sampling von Web Seiten

(Henzinger et al)• Uniform Sampling von web Seiten

(Bar-Yossef et al)


Seite 196

Random Sampling von Web Seiten• W = ein Schnappschuss des

“indizierbaren Webs”– Betrachte nur “statische” HTML

web Seitenπ = Wahrscheinlichkeitsverteilung

von W

• Ziel: effiziente Algorithmus fürdas Generieren von Stichproben von W bezüglichder Verteilung π.

• Fokus: – π = PageRank– π = Uniform

Indexableweb


Seite 197

Random Sampling von Web SeitenMotivation

• Berechne Statistiken über das Web– Wie hoch ist der Anteil der Web Seiten von .de?– Wie hoch ist der Anteil der Web Seiten in Chinesisch?– Wie hoch ist der Anteil der Werbelinks?

• Vergleich der Abdeckung von Suchmaschinen– Ist Google größer als MSN?– Wie hoch ist der Schnitt zwischen Google and Yahoo?

• Data mining im Web– Wie oft referenzieren Informatikseiten Biologieseiten?– Wie hoch ist der Anteil der Seiten für ein Thema?


Seite 198

Random Sampling von Web SeitenHerausforderungen

• Einfache Lösung: Crawl, Index, Sample– Crawls können nie vollständig sein– Web ändert sich ständig– Crawling ist langsam und teuer

• Ziele:– Genauigkeit: Erzeuge eine Stichprobe von einem

Schnappschuss des gesamten indizierbaren Webs– Geschwindigkeit: Stichprobe soll schnell erzeugt

werden– Geringe Kosten: Verfahren soll auf einem Standard PC

laufen können


Seite 199

Random Walk Ansatz

• Erzeuge Random Walk auf W mit stationärerVerteilung π– P = Übergangsmatrix des Random WalkπP = π

• Iteriere Random Walk hinreichend viele Schritte– Für jede initiale Verteilung q, – Mixing time: # der Schritte um dem Grenzwert nahe zu

kommen• Nutze erreichten Knoten als Element der

Stichprobe• Wiederhole, bis Stichprobe hinreichend groß ist


Seite 200

Random Walk Ansatz :Vorteile & Probleme

• Vorteile:– Genauigkeit: Random Walk kann im Prinzip jede Seite

im Web erreichen– Geschwindigkeit: Gesamtes Web braucht nicht geladen

werden– Geringe Kosten: geringe Speicher und CPU Kosten

• Probleme:– Wie soll der Random Walk entworfen werden, dass er

zu π konvergiert?– Wie kann die Mixing Time des Random Walks

bestimmt werden?


Seite 201

PageRank Sampling [Henzinger et al 1999]

• Nutze den “Random Surfer” Random Walk:– Starte an einen initiale Knoten v0

– Wenn eine Seite v besucht wird• Wirf eine Münze mit Wahrscheinlichkeit α für Kopf• Fall Kopf, gehe zu einer gleichverteilt gewählten Seite• Falls Zahl, gehe zu einem zufälligen Nachbarn von v

• Grenzwert Verteilung: PageRank• Mixing Time: schnell


Seite 202

PageRank Sampling:Realität

• Problem: Wie wird eine Seite zufälliggleichverteilt gewählt?

• Lösungen:– Springe zu einer frühren Seite aus dem Walk

• Erzeugt Bias zu dichten Webdomäns– Wähle einen zufälligen Server aus den Servern

auf dem bisherigen Walk und springe zu einerzufälligen Seite dieses Servers

• Konvergiert nicht mehr zu PageRank• Experimente zeigen, dass es trotzdem funktioniert


Seite 203

Uniform Sampling via PageRankSampling [Henzinger et al 2000]

• Algorithmus:1. Nutze vorherigen Random Walk um ein Element w

bezüglich PageRank Verteilung zu erzeugen2. Wirf eine Münze mit Wahrscheinlkeit für Kopf3. Falls Kopf, gib w als ein Element aus4. Falls Zahl, gehe zu Schritt 1Analyse:–– Braucht C/|W| Iterationen um ein Element zu

bekommen


Seite 204

Uniform Sampling via PageRankSampling: Reality

• Wie wird PR(w) bestimmt?– Nutze den Random Walk selbst:

• VR(w) = Visit Ratio von w (# der Besuche von w auf dem Walk geteilt durch die Länge des Walk)

• Approximation ist sehr ungenau– Nutze den durch die besuchten Knoten

aufgespannten Teilgraph um PageRank zuberechnen

• Bias zu der Nachbarschaft der Startseite– Nutze Google


Seite 205

Uniform Sampling mittels RW auf regulären Graphen [Bar-Yossef et al 2000]

• Fakt: Ein Random Walk auf einem ungerichteten, zusammenhängendem, nicht-bipartiten Graphenkonvergiert gegen eine Gleichverteilung.

• Beweis:– P: Random Walk Übergangsmatrix

• P ist stochastisch• 1 ist ein rechter Eigenvektor mit Eigenwert 1: P1 = 1

– Graph ist zusammenhängend RW ist nichtreduzierbar

– Graph ist nicht-bipartit RW ist aperiodisch– Somit ist RW ergodisch und hat deshalb eine

stationäre Verteilung π: • π ist ein linker Eigenvektor von P mit Eigenwert 1: πP = π


Seite 206

Random Walks auf Regulären Graphen

• Beweis Fortsetzung:– d: der Grad des Graphen,– A: Adjazenzmatrix des Graphen

• Symmetrisch, da derGraph ungerichtet ist– P = (1/d) A

• P ist auch symmetrisch• Linke und rechte Eigenvektoren sind gleich• π = (1/n) 1


Seite 207

Web als Regulärer Graph• Probleme

– Web ist nicht zusammenhängend– Web ist gerichtet– Web ist nicht regulär

• Lösungen– Betrachte nur das indizierbare Web, das

zusammenhängend ist– Ignoriere Richtung derLinks– Füge eine gewichtete Schleife zu jedem Knoten hinzu

• weight(w) = degmax – deg(w)• Alle Seiten haben dann den Grad degmax• Überschätzen von degmax macht nichts


Seite 208

Beispiel Random Walk auf dem Web

• Kann in Senken oder dichten Web Communities feststecken

• Bevorzugt populäre Seiten

• Konvergiert nur langsam, wenn überhaupt

netscape.com

amazon.com

www.cs.berkeley.edu/~zivi

Folgene einemzufälligen Out-link in jedem Schritt

1

2

3

4

56

7

8

9


Seite 209

Ungerichteter regulärer Random Walk auf dem Web

w(v) = degmax - deg(v)

netscape.com

www.cs.berkeley.edu/~zivi

1

2

31

amazon.com

4

02

3

03

2

2

4

4

3

3

3

1

2

5Folge einem zufälligemIn oder OutLink in jedem Schritt

Nutze gewichteteSchleifen um den Grad den Seite zukompensieren


Seite 210

Mixing Time Analyse

• SatzMixing time eines Random Walk ist log(|W|) / (1 - λ2)– 1 - λ2: spektrale Lücke von P

• Experiment (mit großem Web Crawl):– 1 – λ2 ~ 1/100,000– log(|W|) ~ 34

• Deshalb: mixing time ~ 3.4 Millionen Schritte– Schleifenschritte sind frei– Etwa 1 bis 30,000 Schritte sind keine Schleifen

(degmax ~ 300,000, degavg ~ 10)– Tatsächliche mixing time: ~ 115 steps!


Seite 211

Random Walks auf RegulärenGraphen: Realität

• Wie bekommt man die eingehenden Links?– Suchmaschinen

• Beeinflußt durch den Index der Suchmaschine• Ergibt keine vollständige Liste der eingehenden Links• Teure Kommunikation

– Geschichte des Random Walk• Wichtig zum Vermeiden von Sackgassen• Erfordert Speicherplatz

• Wie kann deg(w) geschätzt werden?• Lösung: Random Walk auf dem Teilgraphen von W, der

durch die verfügbaren Links aufgespannt wird– Teilgraph muß nicht mehr gute mixing time Eigenschaften haben


Seite 212

Top 20 Internet Domains (Summer 2003)

10.36%

5.57%4.15%3.01%0.61%

9.19%

51.15%

0%

10%

20%

30%

40%

50%

60%

.com

.org

.net

.edu .de .uk .au .us .es .jp .ca .nl .it .ch .pl .il .nz .gov

.info .m

x


Seite 213

68%

54%50% 50% 48%

38%

0%

10%

20%

30%

40%

50%

60%

70%

80%

Google AltaVista Fast Lycos HotBot Go

Search Engine Coverage(Summer 2000)

Documents

7. Vorlesung - users.informatik.uni-halle.deusers.informatik.uni-halle.de/~hinnebur/Lehre/IR_WS06_web/IR_WS06_7.pdfWS 2006/07 Alexander Hinneburg, Martin-Luther-Universität Halle/Wittenberg