🕸️ Netzwerk-Perkolation — Schwellenwert der Riesenkomponente

Die Simulation mischt vorab die vollständige Liste aller möglichen Knotenpaare (mittels Fisher-Yates-Shuffle) und deckt sie dann nacheinander als Kanten auf. Dies entspricht dem G(N,M)-Erdős-Rényi-Modell, bei dem genau M Kanten gleichmäßig zufällig aus den N(N−1)/2 möglichen Paaren gewählt werden, statt jede Kante unabhängig mit Wahrscheinlichkeit p einzuschließen — die beiden Formulierungen konvergieren für großes N.

Sie verwendet eine Union-Find-(Disjoint-Set-Union)-Datenstruktur. Jeder Knoten beginnt in seiner eigenen Komponente; das Hinzufügen einer Kante ruft union(a,b) auf, was die beiden Komponenten verschmilzt, indem die Wurzel des kleineren Baums an die Wurzel des größeren angehängt wird. Mit Pfadkomprimierung (Abflachen des Baums bei find) und Union nach Rang laufen beide Operationen in nahezu konstanter Zeit, sodass das Verfolgen von Komponenten für Hunderte von Knoten und Tausende von Kanten auch in Echtzeit schnell bleibt.

⟨k⟩ ist die durchschnittliche Anzahl der Kanten pro Knoten, berechnet als 2M/N, wobei M die aktuelle Kantenzahl ist. Der Schieberegler legt ein Ziel-⟨k⟩ fest; die Simulation berechnet dann die Ziel-Kantenzahl M = round(⟨k⟩·N/2) und fügt entweder Kanten hinzu, um sie zu erreichen (wenn Sie ⟨k⟩ erhöhen), oder führt einen vollständigen Reset durch und baut von Grund auf neu auf (wenn Sie es verringern, da Kanten nicht schrittweise entfernt werden können).

Unterhalb von ⟨k⟩ = 1 ist der Zufallsgraph ein Wald aus kleinen baumartigen Clustern, jeweils von Größe O(log N), und keiner von ihnen kann zu einem endlichen Anteil des Graphen heranwachsen. Sobald ⟨k⟩ die 1 überschreitet, wird der Verzweigungsprozess, der das Clusterwachstum beschreibt, überkritisch: Ein Cluster hat nun im Durchschnitt mehr als einen neuen Knoten, in den er sich bei jedem Schritt ausdehnen kann, sodass sich das Wachstum eines Clusters verstärkt, bis er einen Anteil S aller N Knoten verschlingt, der S = 1 − e^(−⟨k⟩S) erfüllt. Dies ist ein echter Phasenübergang zweiter Ordnung, kein bloßer glatter Trend.

Nein. Die Positionen auf dem Bildschirm sind rein kosmetisch, erzeugt durch ein einfaches kraftbasiertes Abstoßungslayout (oder ein Gitterlayout bei großem N), rein damit sich Knoten visuell nicht überlappen. Welche Knoten der Riesenkomponente beitreten, wird vollständig durch die zufällige Kantenreihenfolge und die Konnektivität des Graphen bestimmt — die Position auf dem Bildschirm trägt keine Information über Grad oder Komponentenzugehörigkeit.