next up previous contents
Nächste Seite: Schlußbetrachtung und Ausblick Aufwärts: Die Korrelationen im Webcrawl Vorherige Seite: Die unkorrelierte Verteilung   Inhalt

Die Verteilung mit In-/Outdegree Korrelationen

Eine mögliche Ursache für die Abweichungen von der Näherung (5.2) könnten die Korrelationen zwischen In- und Outdegree eines Knotens sein, wie sie im vorhergehenden Kapitel beobachtet wurden. Dort zeigte sich beim Vergleich zwischen dem Webcrawl und einem Netzwerk ohne Korrelationen zwischen den Degrees eines Knotens eine deutlich höhere Präsenz von Knoten mit hohem In- und Outdegree. Wenn jedoch Knoten mit hohem Indegree stärker dazu tendieren, auch einen hohen Outdegree zu haben, dann erscheinen diese Knoten auch häufiger als Ursprung von Links.

Daher wird in einer weiteren Näherung diese Korrelationen zwischen Outdegree $j$ und Indegree $i_1$ eines Knotens mit einbezogen. Dazu wird die Anzahl der Outlinks eines Knotens unter der Bedingung, daß dessen Indegree gleich $i_1$ ist, betrachtet, d.h. $P_{out}(j\vert i_1)$. Mit der Anzahl $N P_{in}(i_1)$ von Knoten mit Indegree $i_1$, ist die Wahrscheinlichkeit, daß ein Link seinen Ursprung bei einem Knoten mit Indegree $i_1$ hat, gleich

$\displaystyle P_{Quelle}(i_1)= \int \frac{N P_{in}(i_1) P_{out}(j\vert i_1) j}{N_{L}}dj.$ (5.3)

Für die bedingte Wahrscheinlichkeit gilt $P_{out}(j\vert i_1)=\frac{r(i_1,j)}{P(i_1)}$. Die Wahrscheinlichkeit, daß ein Link bei einem Knoten mit Indegree $i_2$ endet, bleibt wie zuvor $\frac{N P_{in}(i_2)  i_2}{N_L}$. Damit ist die Wahrscheinlichkeit, einen Link von einem Knoten mit Indegree $i_1$ zu einem Knoten mit Indegree $i_2$ zu finden,

$\displaystyle L_{1}(i_1, i_2) = \frac{N  P_{in}(i_2)  i_2}{N_L} \int \frac{N  P_{in}(i_1)  r(i_1,j)  j}{N_L  P_{in}(i_1)} dj .$ (5.4)

Die Verteilungen $P_{in}$ des ersten Faktors der rechten Seite heben sich auf. Mit der mittleren Konnektivität $<k>$ erhält die Näherung der Verteilung $L_{1}(i_1,i_2)$ unter Berücksichtigung der Korrelationen zwischen dem In- und Outdegree eines Knotens die Form

$\displaystyle L_{1}(i_1, i_2) = \frac{P_{in}(i_2)  i_2}{<k>^2} \int r(i_1,j)  j dj.$ (5.5)

Wiederum ist diese Verteilung als Norm für die gemessenen Werte angewendet worden und in Abbildung 5.5 dargestellt.

Abbildung: Verteilung der Links $L(i_1, i_2)$ in Abhänigikeit vom Indegree des Quellknotens $i_1$ und vom Indegree des Zielknotens $i_2$, normiert mit der Näherung $L_1$ (5.5) für Netzwerke mit Korrelationen zwischen dem In-/Outdegree eines Knotens und ohne Korrelationen zwischen den Indegrees benachbarter Knoten.
\begin{figure}\noindent
\centering\epsfig{file=eps/krap_links_norm_lin.eps, width=\linewidth} %\vskip -0.1in\end{figure}

Man erkennt bereits, daß die Verteilung des Webcrawls deutlich besser wiedergegeben wird als zuvor. Die Korrelationen aus Abb. 5.4 stammen demnach zu einem großen Teil aus den Korrelationen zwischen In- und Outdegree der einzelnen Knoten, wie sie bereits im vorhergehenden Kapitel untersucht wurden. Hier sind jedoch weitergehende Korrelationen gesucht.

Wie bei der gemeinsamen Verteilung $r(i,j)$ von Knoten mit Indegree $i$ und Outdegree $j$ fällt auch hier in der Diagonalen eine deutliche Überrepräsentation auf. Demnach gibt es auch eine überdurchschnittlich hohe Anzahl an Links zwischen Knoten mit identischem Indegree. Das Unterstützt die bereits zuvor gemachte Annahme (vgl. Abschnitt 4.5), daß die Ursache Websites mit Navigationsleisten sind. Dadurch das $n$ Seiten eine solche Liste von Links auf alle anderen $n-1$ Seiten einer Website haben, erzeugt jeder derartige Cluster in dieser Linkstatistik entsprechend $n(n-1)$ Links zwischen Knoten mit identischem Indegree $n-1$.

Außerhalb des Einflusses der Diagonalen erscheinen große, ebene Bereiche mit Werten um $0.5\pm 0.1$. Die Bereiche von $i_1,i_2 < 5$ werden nicht in die folgenden Betrachtungen einbezogen, da diese durch Randeffekte verändert sein können (vgl. Abschnitt 4.5).

Insgesamt ist eine leichte Tendenz erkennbar, daß Seiten mit einem Indgree $i_1$ zu Seiten mit einem höheren Indegree $i_2 > i_1$ verweisen. Eine mögliche Erklärung soll folgendes Beispiel veranschaulichen: Die Webseiten einzelner Personen (Homepages) sind im allgemeinen relativ unbekannt. Auf diesen Homepages sind sogenannte Linksammlungen beliebt. Das sind typischerweise eine Reihe von Verweisen auf Webseiten von persönlichem Interesse des Besitzers. Bei einem Fußballfan wird diese Linksammlung vermutlich einen Verweis auf die Webseite seines Lieblingsvereins enthalten, sowie Verweise auf andere Seiten, die für Fußballfans interessant sind. Auf diese Seiten werden jedoch viele Fußballfans verweisen. Hingegen werden diese allgemeinen Fußballseiten nicht, oder zumindest seltener, auf einzelne Fans verweisen.

Ein weiterer Unterschied zeigt sich bei $i_1 > 40$. Seiten mit einem Indegree jenseits von 40 scheinen allgemein seltener auf andere Seiten zu verweisen. Eine denkbare Ursache ist, daß Webseiten ab einem bestimmten Bekanntheitsgrad besser organisiert werden. Wie bereits in Abschnitt 4.5 erwähnt, empfehlen professionelle Lehrbücher zum Webdesign [37], nur 8 bis 10 Outlinks pro Seite zu verwenden.

Anders als bei der Betrachtung in Abschnitt 5.2 lassen sich also bei differenzierterer Analyse leichte Korrelationen zwischen den Indegrees benachbarter Knoten finden.

Unter der Annahme, daß die hier beobachteten Korrelationen und deren Ursachen hinreichend bedeutend sind, wären Verbesserungen für die Verfahren zur Bewertung und Suche von Webseiten denkbar. Es erscheint naheliegend, daß eine professioneller betreute Seite überdurchschnittlich differenzierte und aktuelle Informationen bietet. Bei der Bewertung der Relevanz von Seiten könnten daher Seiten ab 40 Inlinks stärker gewichtet werden. Ebenso könnten bei der Erstellung eines Webcrawls die Outlinks von Seiten ab 40 Inlinks bevorzugt untersucht werden, da diese Seiten wahrscheinlich auch eine wertvollere Auswahl von Verweisen auf Inhalte bieten.


next up previous contents
Nächste Seite: Schlußbetrachtung und Ausblick Aufwärts: Die Korrelationen im Webcrawl Vorherige Seite: Die unkorrelierte Verteilung   Inhalt
Autor:Lutz-Ingo Mielsch