Surfen in viereinhalb Dimensionen

Für das Internet und das globale Flugliniennetz wurde jetzt die räumliche Dimension berechnet.

Bei der Untersuchung von komplexen Netzwerken wie dem Internet oder Flugliniennetzen wurde bisher kaum danach gefragt, ob sie eine räumliche Dimension haben, die sich von ihrer „Einbettungsdimension“ (die meist 2 ist) unterscheidet. Jetzt haben Forscher um Armin Bunde an der Universität Gießen und Shlomo Havlin an der Bar Ilan Universität ein Verfahren entwickelt, mit dem man die Dimension eines Netzes bestimmen kann. Außerdem konnten sie zeigen, dass diese Netzdimension einen wichtigen Einfluss auf Diffusions- und Perkolationsprozesse hat, die auf dem Netz stattfinden.

Ein Netz besteht aus vielen Knoten, die paarweise miteinander verbunden sind. Das können zum Beispiel Flughäfen sein, zwischen denen es direkte Flugverbindungen gibt, oder Internet-Router, die über eine Datenleitung verbunden sind. In diesen Beispielen gibt es Verbindungen auch zwischen weit voneinander entfernten Knoten, wobei die Länge r der Verbindungen statistisch nach einem Potenzgesetz 1/rb verteilt ist. Es ist somit keine Längenskala ausgezeichnet. Für das globale Flugliniennetz findet man b≈3, für das Internet b≈2,6. Die Anzahl k der Verbindungen, die die einzelnen Knoten haben, ist die ebenfalls nach einem Potenzgesetz verteilt, und zwar wie 1/ka. Für das globale Flugliniennetz ist a≈1,8, für das Internet findet man a≈2,1.

 Um nun für solche „skalenfreien“ Netze eine physikalisch bedeutsame Dimension d zu erhalten, gingen die Forscher folgendermaßen vor. Zunächst wählten sie einen Knoten als Ausgangspunkt und bestimmten seine nächsten Nachbarn, die über das Netz in einem Schritt (n=1) erreichbar waren, dann die übernächsten Nachbarn (n=2) usw. Anschließend ermittelten sie die Anzahl M(n) der n-Nachbarn des Knoten und berechneten deren mittlere Entfernung r(n) vom Ausgangspunkt. Diese Prozedur wiederholten sie, indem sie jeden Knoten des Netzes zum Ausgangspunkt machten und die Mittelwerte für M(n) und r(n) berechneten.

Als die Forscher die Werte für M(n) gegen r(n) doppeltlogarithmisch auftrugen, lagen die Punkte annähernd auf einer Geraden mit einer Steigung d. Somit verhielt sich die Zahl M der Knoten, die sich in einer Hyperkugel mit dem Radius r befanden, wie M~r^d. Die Größe d hatte also die Bedeutung einer Dimension, die allerdings nicht mit der Einbettungsdimension D=2 der Knoten übereinstimmte: Für das Internet fanden die Forscher d≈4,5 und für das Flugliniennetz d≈3. Bei einem Netz, das nicht skalenfrei ist sondern z. B. nur kurzreichweitige Verbindungen mit einer charakteristischen Länge hat, stimmen d und D überein: Aus geometrischen Gründen gilt hier M(n)~n^D und r~n, sodass man M~r^D erhält.

Dass die so gefundene Dimension d eines komplexen Netzes physikalische Bedeutung hat, zeigten die Forscher auf zweifache Weise. Zuerst untersuchten sie den Irrflug oder Random Walk eines Teilchens auf Netzen mit unterschiedlicher Dimension d. Dabei sprang das Teilchen entlang der Verbindungen in zufälliger Weise von einem Knoten zum nächsten. Bunde und seine Kollegen ermittelten die Wahrscheinlichkeit P₀, mit der das Teilchen nach t Schritten zu seinem Startpunkt zurückkehrte. Hatte sich das Teilchen im Mittel um r=r(t) vom Startpunkt entfernt, so konnte es irgendwo in der d-dimensionalen Hyperkugel mit dem Radius r und dem Volumen r^d sein. Man erwartet deshalb, dass P₀~1/rd gilt. Genau dieses Verhalten haben die Forscher beobachtet.

Dann betrachteten sie einen Perkolationsprozess auf dem Netz. Dazu entfernten sie einen Bruchteil q der Knoten. War q nicht zu groß, so konnte sich Teilchen zunächst im ganzen Netz bewegen oder perkolieren. Doch bei einem kritischen Wert q_c zerfiel das Netz in nicht mehr zusammenhängende Teile, die alle möglichen Größen s hatten. Die Größenverteilung folgte dem Potenzgesetz 1/s^c, während das in Bruchstücke zerfallene Netz die fraktale Dimension f hatte. Der Perkolationstheorie zufolge gilt nun: d = (c-1)f, wobei d die Netzdimension ist. Tatsächlich stimmte der am kritischen Punkt der Perkolation ermittelte Wert der Dimension d gut mit dem Wert überein, den die Forscher mit ihrem neuen Verfahren erhalten hatten.

Die Netzdimension spielt also sowohl bei der Diffusion von Teilchen auf einem Netz wie auch bei der Perkolation ein wichtige Rolle. Sie entscheidet z.B. darüber, wie schnell sich eine Infektion durch Flugreisende über das Flugliniennetz ausbreiten kann. Dass man sich bei Flugreisen in einem dreidimensionalen Netz bewegt, leuchtet vielleicht noch ein. Dass man aber im Internet in viereinhalb Dimensionen surft, ist schon überraschend.

Rainer Scharf