🔗 Sechs Ecken der Trennung — Small-World-Netzwerke

Die durchschnittliche Pfadlänge ist die mittlere Anzahl von Kanten auf der kürzesten Route zwischen allen Knotenpaaren in einem Netzwerk. Sie ist wichtig, weil sie bestimmt, wie schnell sich Informationen, Krankheiten oder Einfluss in einem System ausbreiten können. In einem reinen Ringgitter mit ein paar Hundert Knoten wächst die durchschnittliche Pfadlänge etwa linear mit der Netzwerkgröße, was das Netzwerk in einem funktionalen Sinne „groß" macht. Das Hinzufügen weniger zufälliger Abkürzungen führt stattdessen nur zu logarithmischem Wachstum der durchschnittlichen Pfadlänge mit der Größe, weshalb riesige soziale Netzwerke immer noch in einer Handvoll Schritten durchquert werden können.

Stanley Milgram war ein amerikanischer Sozialpsychologe an der Harvard-Universität, am bekanntesten für seine umstrittenen Gehorsamkeitsexperimente, aber seine Studie zum „Small-World-Problem" von 1967 ist ebenso einflussreich. Er gab mehreren Hundert Menschen in Nebraska und Kansas eine Mappe, adressiert an einen bestimmten Börsenmakler in Boston, und bat sie, sie nur an jemanden weiterzugeben, den sie persönlich kannten und der dem Ziel näher sein könnte. Abgeschlossene Ketten hatten durchschnittlich etwa fünf bis sechs Zwischenglieder, was zum populären Ausdruck „sechs Ecken der Trennung" führte, obwohl die ursprüngliche Studie erhebliche methodische Einschränkungen hatte, einschließlich einer niedrigen Abschlussquote.

Duncan Watts, damals Doktorand, und sein Betreuer Steven Strogatz, ein angewandter Mathematiker an der Cornell-Universität, veröffentlichten 1998 „Collective dynamics of 'small-world' networks" in Nature. Sie führten ein einfaches algorithmisches Modell ein — beginne mit einem regulären Ringgitter und verdrahte jede Kante mit Wahrscheinlichkeit p neu — und zeigten rechnerisch, dass ein schmaler Bereich von p Netzwerke mit sowohl kurzer durchschnittlicher Pfadlänge als auch hoher Vernetzung erzeugt, was Eigenschaften entspricht, die in realen Netzwerken wie dem elektrischen Stromnetz der westlichen USA und dem neuronalen Netzwerk des Fadenwurms C. elegans beobachtet werden.

Small-World-Struktur wurde in einer enormen Bandbreite von Systemen dokumentiert: sozialen und Freundschaftsnetzwerken, wissenschaftlichen Kollaborations- und Zitationsgraphen, der neuronalen Verdrahtung von Gehirnen einschließlich C. elegans, großen Stromübertragungsnetzen, der Router-Ebene-Topologie des Internets und Filmschauspieler-Kollaborationsnetzwerken — der Grundlage des populären „Sechs Ecken von Kevin Bacon"-Wissensspiels, bei dem fast jeder Schauspieler durch eine kurze Kette gemeinsamer Filmcredits mit Kevin Bacon verknüpft werden kann.

Nein. „Sechs Ecken der Trennung" ist eine einprägsame Näherung aus einem bestimmten historischen Experiment, keine universelle Konstante. Die tatsächliche durchschnittliche Pfadlänge in jedem Netzwerk hängt stark von dessen Größe, Dichte und Gradverteilung ab. Große moderne Online-Sozialnetzwerke wurden mit durchschnittlichen Distanzen näher an vier Schritten gemessen, während spärlichere oder geografisch eingeschränktere Netzwerke längere typische Pfade haben können. Das Watts-Strogatz-Modell erklärt, warum so kurze Pfade überhaupt möglich sind, nicht dass jedes Netzwerk genau sechs Ecken hat.

Die durchschnittliche Pfadlänge wird geschätzt, indem eine Breitensuche von einer Stichprobe von bis zu 40 Quellknoten ausgeführt und die kürzesten Pfaddistanzen zu jedem anderen erreichbaren Knoten gemittelt werden, was die Berechnung auch für größere Netzwerke schnell hält. Der Clusterkoeffizient wird für jeden Knoten exakt berechnet als Anteil möglicher Kanten unter seinen Nachbarn, die tatsächlich existieren, dann über alle Knoten gemittelt. Beide Statistiken werden automatisch neu berechnet, sobald du die Neuverdrahtungswahrscheinlichkeit, Knotenzahl oder Nachbarnzahl änderst.

Sigma ist eine gängige zusammenfassende Statistik, die die Vernetzung und Pfadlänge eines Netzwerks mit denen vergleicht, die in vergleichbaren zufälligen und regulären Netzwerken erwartet werden. Ein Sigma-Wert deutlich über 1 zeigt echte Small-World-Struktur an — hohe Vernetzung im Vergleich zu einem Zufallsgraphen kombiniert mit kurzen Pfaden im Vergleich zu einem regulären Gitter. Die hier gezeigte Schätzung verwendet vereinfachte analytische Näherungen für die Basisvergleiche, statt vollständige Vergleichsgraphen zu erzeugen, sodass sie eher als illustrativer Indikator denn als präzises forschungsreifes Maß zu verstehen ist.