Grundlage erweiterter Modelle: Korrelationen zwischen In- und Outdegree

Die Möglichkeit, das WWW durch zwei Verteilungen, die Indegree-Verteilung und die Outdegree-Verteilung, zu beschreiben, wirft die Frage auf, ob diese Verteilungen unabhängig voneinander sind. Um diesen Korrelationen nachzugehen, wurde die gemeinsame Verteilung von In- und Outdegree eines Knotens bestimmt. Ein erster Vergleich mit der zu erwartenden Verteilung ohne Korrelationen zwischen den Degrees zeigte eine höhere Präsenz von Knoten mit hohem Indegree und hohem Outdegree. Der Indegree und Outdegree eines Knoten sind offenbar korreliert.

In einem weiteren Schritt wurde geprüft, ob die Korrelationen durch existierende Modelle der Dynamik des WWW erklärt werden können. Das Modell des WWW von Krapivsky et al. [8] macht eine Vorhersage der gemeinsamen Verteilung von Indegree und Outdegree eines Knotens. Um dieses Modell zu prüfen, wurden ausgehend von den Exponenten der Verteilungen und der mittleren Konnektivität des Webcrawls die Parameter des Modells bestimmt und die gemeinsame Verteilung im Rahmen des Modells ermittelt. In einem Vergleich zwischen dem Modell von Krapivsky et al. [8] und dem Webcrawl konnte gezeigt werden, daß die Korrelationen zwischen dem In- und Outdegree eines Knotens durch das Modell gut wiedergegeben werden.

Aus der Übereinstimmung mit dem Modell von Krapivsky et al. kann geschlossen werden, daß die Wachstumsdynamik des WWW durch zwei Prozesse beschrieben wird. (1) Erzeugen eines neuen Knotens mit einer Verbindung zu einem bestehenden Knoten und (2) Erstellen einer neuen Verbindung zwischen zwei bestehenden Knoten des Netzwerks. Dabei ist die Wahrscheinlichkeit eines Knotens, das Ziel einer Verbindung zu werden, proportional zu seinem Indegree (``Preferential Attachment''). Entsprechend ist zusätzlich für den zweiten Prozess die Wahrscheinlichkeit eines Knotens, Urspung einer Verbindung zu sein, proportional zu seinem Outdegree (``Preferential Update''). Diese lineare-bilineare Form für die Knotenauswahl der beiden Prozesse ist ein wesentlicher Bestandteil des Modells. Sie entspricht einer Verknüpfung des ``Preferential Attachment''[5] für die Indegrees und eines analogen Mechanismus für die Outdegrees.

Es erscheint sinnvoll anzunehmen, daß Webseiten auf die von vielen anderen Seiten verwiesen wird (d.h. mit hohem Indegree), populärer sind als Seiten mit weniger Inlinks. Aufgrund dieser Popularität sind diese Seiten auch mehr Autoren von Webseiten bekannt. Wenn Autoren neue Seiten oder Verweise erstellen wählen sie aus den ihnen bekannten Seiten aus. Dies könnte eine Ursache für das ``Preferential Attachment'' sein. Dieser Mechanismus ist bereits in früheren Untersuchungen der Indegree-Verteilung des WWW und verschiedener anderer Netze gefunden worden [5].

Eine neue Erkenntnis ist, daß die Entwicklung der Outlinks von Seiten des WWW einem analogen Mechanismus unterliegt. Viele Webseiten von Personen haben Sammlungen von Verweisen auf persönlich favorisierte Webseiten. Jemand mit einer Sammlung solcher Verweise wird vermutlich relativ viele Seiten davon regelmäßig besuchen. Dabei werden viele neue Verweise auf Seiten gefunden und einige davon werden angesehen. Jemand mit einer großen Linksammlung wird mehr Seiten regelmäßig besuchen, daher mehr neue Webseiten entdecken und mehr neue Verweise seiner Sammlung hinzufügen. Die größte Linksammlung von mehr als 16000 Outlinks ist eine Sammlung aus deutschen WWW-Domains (http://www.fb9-ti.uni-duisburg.de/mitarbeiter/willett/domains.html). Diese Seite hat den zweithöchsten Outdegree der Seiten des Webcrawls. Die Webseite mit dem höchsten Outdegree existierte zum Zeitpunkt der näheren Untersuchung nicht mehr im WWW.

Es ist intuitiv nicht klar, wie diese Mechanismen zusammenwirken. Daher ist eine weitere wesentliche Aussage des Modells von Krapivsky et al., daß diese Mechanismen in der Dynamik gleichzeitig wirken (lineare-bilineare Raten). Jeder Zielknoten eines Inlinks wird via ``Preferential Attachment'' gewählt. Mit Ausnahme des ersten Outlinks werden alle Quellknoten via ``Preferential Update'' gewählt. Betrachtungen des Modells für verschiedene andere Raten zeigten bereits bei der Indegree- und Outdegree-Verteilung grundsätzliche Unterschiede [8] zum WWW. Dieses Ergebnis unterstreicht die Bedeutung dieser generischen Mechanismen für die Entwicklung des WWW.

Die empirische Bestätigung der Korrelation und der Form der gemeinsamen Verteilung von In- und Outdegrees ist ein Ausgangspunkt für detailiertere Untersuchungen der topologischen Eigenschaften komplexer Netzwerke und ermöglicht einen differenzierten Vergleich des WWW mit anderen Netzwerken. Insbesondere sind diese Korrelationen für Untersuchungen von Perkolation auf gerichteten skalenfreien Netzwerken von besonderer Bedeutung [41] und können in diesem Zusammenhang auch Ausgangspunkt für die Bestimmung weiterer topologischer Eigenschaften sein. Darüber hinaus charakterisiert diese Verteilung das Netzwerk vollständig, wenn zwischen dem Indegree und Outdegree eines Knoten und den Degrees seiner Nachbarn keinerlei Zusammenhang besteht.