next up previous contents
Nächste Seite: Indegree-Korrelationen Aufwärts: Gemeinsame In- und Outdegree Vorherige Seite: Vorhersage des Modells von   Inhalt

Der Vergleich

In Abbildung 4.5 ist zum besseren Vergleich die empirische Verteilung des Webcrawl mit der theoretischen Vorhersage des Krapivsky et al. Modells normiert gezeigt.

Abbildung: Gemeinsame Verteilung aus dem Webcrawl normiert mit der Verteilung des Krapivsky Modells $r_{crawl}(i,j)/r_{krr}(i,j)$ Die Färbung gibt die Abweichung der Wahrscheinlichkeiten an, einen Knoten mit $i$ Inlinks und $j$ Outlinks zu finden (lineare Farbskala).
\begin{figure}\noindent
\centering\epsfig{file=eps/p_io_drawkrap.eps, width=\linewidth} \vskip 0.1in\par
\end{figure}

Insgesamt zeigen die großen relativ ebenen Bereiche, daß der Verlauf der gemeinsamen Verteilung des Webcrawls gut mit der Verteilung des Modells übereinstimmt. Die Korrelationen zwischen dem Indegree und Outdegree der Knoten werden in diesen Bereichen gut wiedergegeben.

Deutlich als Diagonale zu erkennen ist eine unerwartet hohe Wahrscheinlichkeit, Knoten mit fast identischem In- und Out-Degree zu finden, die in der Vorhersage des Modells fehlt. Eine mögliche Erklärung ist eine besondere Art des Webdesign. Eine sehr beliebte und häufig anzutreffende Form von Webseiten sind sogenannte Archive und Diskussionsforen. Diese setzen sich im wesentlichen aus einer Index-Seite mit Links zu allen Seiten mit Beiträgen zusammen. Jeder dieser Beiträge hat jedoch auch ein Link auf die Indexseite. Somit wird die Index-Seite zunächst genau die gleiche Anzahl Inlinks wie Outlinks haben. Diese Seiten dominieren vor allem bei hohen, symmetrischen Konnektivitäten. In Tabelle 4.1 sind exemplarisch alle Knoten mit URL angegeben, deren Degrees ähnlich und größer als 1500 sind.


Tabelle: Typische Seiten aus dem Webcrawl mit ähnlichem In- und Out-Degree größer 1500. Alle Seiten sind Archive oder Foren, deren Outlinks auf Artikelseiten zeigen von denen jeweils ein Outlink zurück zeigt.
Indegree Outdegree URL
2586 2587 www.han.de/~ gero/netboot/archive/threads.html
2266 2266 infosoc.uni-koeln.de/archives/php/maillist.html
2021 2023 www.sfs.nphil.uni-tuebingen.de/linguist/issues/11/
4987 4991 infosoc.uni-koeln.de/archives/mysql-de/index.html
1552 1554 www.sfs.nphil.uni-tuebingen.de/linguist/issues/10/
1546 1547 www.film-photo.de/FilmVideoVHSActionAbenteuer.htm
1527 1530 www.yorkie.ch/forum/archiv/forum9-archiv.html
4988 4992 infosoc.uni-koeln.de/archives/mysql-de/maillist.html


Ebenso führt die Verwendung von sogenannten ``Web-Management''-Programmen zu einer großen Anzahl von Seiten mit nahezu identischen Degrees. Mit Hilfe dieser Programme werden ganze Websites mit vielen einzelnen Seiten erstellt. Diese Seiten haben typischerweise alle eine Navigationsleiste aus Links, damit sich der Benutzer auf der Website bewegen kann und ihm ein ständiger Überblick geboten wird. Diese Leiste enthält aber im einfachsten Fall eine Liste von Links auf alle anderen Seiten. Somit zeigt jede Seite auf alle anderen Seiten der Website und alle anderen Seiten zeigen zurück. Dieser Aufbau wird im Webdesign empfohlen und als ``Mitgeführte Hauptnavigation'' bezeichnet [37].

Ein weiteres auffälliges Merkmal erkennt man bei Knoten mit einem Indegree von 1 bis 5. Deren Häufigkeit wächst vom Ursprung her langsam an, erreicht bei einem Outdegree von ca. $j= 20$ den Maximalwert und bleibt dann zu beliebig hohen Outdegrees nahezu konstant. Ein Webcrawl ist nur ein Ausschnitt aus dem gesamten WWW. Am Rand des Webcrawls werden daher viele Seiten erfasst, deren lokales Umfeld jedoch nur teilweise oder garnicht mehr erfasst ist. Da die Seiten selbst aber via mindestens eines Inlinks erreicht worden sind (vgl. Abschnitt 3.2), um in den Webcrawl aufgenommen zu werden, erwartet man eine erhöhte Häufigkeit von Seiten mit wenigen Inlinks.

Bei Outdegrees von $j=1\ldots4$ fällt ein ähnlicher Effekt auf. Die Outlinks auf den zuletzt in den Webcrawl aufgenommenen Seiten werden noch ausgewertet. Um mit den Vorraussetzungen des Krapivsky Modells konsistent zu sein, werden jedoch nur noch die Outlinks zu Seiten im Webcrawl aufgenommen. Es werden daher die Verweise auf das lokale Umfeld dieser Seiten teilweise verworfen. Damit wird auch eine erhöhte Häufigkeit von Seiten mit wenigen Outlinks erwartet.

Zum Ursprung hin ($j<10$) gehen diese Randeffekte einerseits in der Menge der Seiten unter, andererseits nimmt die Wahrscheinlichkeit, daß das lokale Umfeld ebenfalls erfasst ist, zu.

Ein weiterer Unterschied fällt bei etwa $j=8$ auf, wenn man dem Verlauf von $i=15$ zu höheren $i$ verfolgt. Die Outdegrees der Knoten verteilen sich häufiger um einen Mittelwert von ca. $j=8$. Die Ursache könnte in der naheliegenden Annahme liegen, daß Webdesigner, innerhalb einer Webseite vermeiden zuviele Outlinks zu verwenden, um die Seite nicht unübersichtlich werden zu lassen. In aktuellen Lehrbüchern zum Design von Webseiten werden häufig $8-10$ Outlinks pro Seite empfohlen [37].

Eine andere Erklärung für diesen Unterschied wäre ein Anteil zufälliger Verbindungen zwischen Knoten im Netzwerk. Diese zufälligen Verbindungen würden für eine hinreichend große Anzahl Links zu einer überlagerten Poisson-Verteilung um den Degreemittelwert $<k>=6.4$ des Netzwerks führen. In einem gerichteten Netzwerk können für eine Verbindung das Ziel, die Quelle oder Beides zufällig gewählt sein. Würden das Ziel und die Quelle zufällig gewählt werden, so müsste sich ebenfalls um $i=<k>$ eine überlagerte Poisson-Verteilung zeigen. Dies ist nicht zu sehen. Demnach ist nur die Wahl der Quelle zufällig, sofern ein Anteil zufälliger Verbindungen die Ursache für diese Abweichung ist.

Abbildung: Dargestellt sind je ein diagonaler Schnitt durch Abb. 4.2 ($\times $) und Abb. 4.5 ($+$), ausgehend von $i=0,j=15$ mit einer Steigung von Eins. Für $n>5$ wird der Verlauf der gemeinsamen Verteilung $r_{crawl}(i,j)$ gut durch das Modell von Krapivsky et al. wiedergegeben. Die Daten sind jeweils in logarithmischen Intervallen gemittelt und auf Werte um Eins verschoben worden.
\begin{figure}\noindent
\centering\epsfig{file=eps/p_io_bothupper_cut.eps, width=\linewidth} \vskip 0.1in\par
\end{figure}

Um den Einfluß der zuvor genannten Abweichungen zu minimieren und eine möglichst große Datenmenge zu erhalten, ist in Abbildung 4.6 ein diagonaler Schnitt mit der Steigung Eins, ausgehend von $j=15$, $i=0$ dargestellt. $n$ bezeichnet den Abstand von Ursprung des Schnittes. Zum Vergleich ist der gleiche Schnitt aus der unkorrelierten Verteilung (Abb. 4.3) ebenfalls dargestellt. Die Daten sind jeweils in logarithmischen Intervallen gemittelt worden und durch einen Proportionalitätsfaktor auf Werte um Eins verschoben worden. Deutlich zu erkennen ist der Randeffekt der Indegree zwischen $n=1$ und $n=5$. Für $n>5$ erkennt man eine gute Übereinstimmung des Verlaufs der empirischen Verteilung und der Verteilung des Modells von Krapivsky et al.. Bemerkenswert ist der Wandel der Verteilung im Bereich von $n=5$. Beschreibt die unkorrelierte Verteilung den Verlauf von etwa $n=1 \ldots 5$ gut, so wird der Bereich jenseits von $n=5$ durch das Modell wiedergegeben. Der zuvor diskutierte Randeffekt für die Indegrees $i=n=1 \dots 5$ zerstört offenbar die Korrelationen zwischen In- und Outdegree eines Knotens.


next up previous contents
Nächste Seite: Indegree-Korrelationen Aufwärts: Gemeinsame In- und Outdegree Vorherige Seite: Vorhersage des Modells von   Inhalt
Autor:Lutz-Ingo Mielsch