Formatbeschreibung der Netzwerk-Dateien

In diesem Abschnitt wird kurz das Format der Netzwerkdateien erläutert. Als Beispiel dient ein kleines Netzwerk aus 4 Knoten und 6 Verbindungen zwischen den Knoten. In Abbildung A.1 ist das Beispielnetzwerk mit der Darstellung im Dateiformat abgebildet.

Die erste Zeile beginnend mit 't' enthält die Anzahl der Knoten $N$ plus Eins im Netzwerk. Entsprechend enthält die zweite Zeile beginnend mit 'T' die Anzahl der Verbindungen $N_L$ plus Eins im Netzwerk. Ab der dritten Zeile werden die Knoten des Netzwerks in genau $N$ Zeilen beschrieben. Diese Zeilen beginnen mit einem '?' in ersten Spalte. In der zweiten Spalte ist eine ganzahlige eindeutige Laufnummer des Knotens angegeben. Die Nummerierung der Knoten muß mit Eins beginnen. Ab der dritten Spalte kann eine beliebige Beschreibung des Knotens folgen. Für einen Webcrawl könnte dies die URL der Seite sein. Bei sehr großen Netzwerken ist dies nicht immer sinnvoll. Der Beschreibung der Knoten folgen ab Zeile $2+N$ genau $N_L$ Zeilen zur Beschreibung aller Verbindungen im Netzwerk. Diese Zeilen beginnen jeweils mit 'l'. Die zweite Spalte dieser Zeilen enthält eine ganzahlige nummerische Laufnummer beginnend mit Eins. Die dritte und vierte Spalte geben jeweils die Laufnummer des Quell- und des Ziel-Knotens an. Damit ist das Netzwerk vollständig beschrieben.

Dieses Format für Netzwerke erscheint eventuell auf den ersten Blick unnötig kompliziert oder ressourcenintensiv. Würde das Netzwerk nur durch die $N_L$ Verbindungen beschrieben, könnten keine Netzwerke mit unverbundenen Knoten dargestellt werden. Daher werden auch Knoten beschrieben. Die jeweils fortlaufende Nummerierung der Knoten und Verbindungen ausgehend von Eins dient als Konsistenzprüfung, ebenso die Angabe der Menge in den ersten beiden Zeilen. Diese Prüfungen sind besonders beim Umgang mit sehr großen Datenmengen ($> 2 GB$) wichtig. Es sei hier besonders auf einen Fehler des UNIX-Betriebssystems ``Solaris'' hingewiesen. Dort kann es vorkommen, daß beim Beschreiben einer Datei über 2GB hinaus, keinerlei Fehler gemeldet werden, obwohl alle Daten jenseits von 2GB verworfen werden. Es sei bei dieser Gelegenheit auch erwähnt, daß Prozesse größer 2GB häufig ähnliche Schwierigkeiten machen.

Die Speicherung des Netzwerks in Textform bietet eine einfache Möglichkeit konkrete Knoten oder Verbindungen direkt zu prüfen. Beispielsweise welche URL ein aufälliger Knoten $i$ hat.

Dieses Format kann darüber hinaus von einem kostenlos erhältlichen Programm zur Darstellung von Netzen^7.1interpretiert werden. Dieses java-basierte Programm ist allerdings nur für Netze mit weniger als einigen Hundert Knoten einsetzbar.

Abbildung: Ein Beispielnetzwerk. Auf der linken Seite ist das Netzwerk im benutzen Dateiformat beschrieben. Auf der rechten Seite ist das beschriebene Netzwerk abgebildet.