🔗 Boolesches Netzwerk — Kauffmans NK-Modell

Der neue Zustand jedes Knotens ist eine zufällige Boolesche Funktion von K Eingängen. Im Durchschnitt breitet sich eine Störung (umgeklapptes Bit) mit Wahrscheinlichkeit 1/2 auf jeden nachgeschalteten Knoten aus (da zufällige Wahrheitstabellen symmetrisch sind). Ist K × 1/2 < 1 (also K < 2), schrumpfen Störungen im Durchschnitt — die geordnete Phase. Ist K × 1/2 > 1 (K > 2), wachsen sie — die chaotische Phase. Bei K = 2 beträgt das Verzweigungsverhältnis genau 1, was den kritischen Punkt ergibt.

Die Hamming-Distanz H(t) zwischen zwei Zuständen ist einfach die Anzahl der abweichenden Knoten. Startet man zwei Trajektorien von Zuständen, die sich nur in einem Bit unterscheiden (H = 1), und verfolgt H über die Zeit, ist das das Boolesche-Netzwerk-Analogon des Lyapunov-Exponenten: Geht H → 0, ist das System geordnet; geht H → N/2, ist das System chaotisch (die beiden Trajektorien werden statistisch unkorreliert); stabilisiert sich H, ist das System kritisch.

Ein Boolesches Netzwerk mit N Knoten hat genau 2^N mögliche Zustände — einen endlichen Zustandsraum. Da die Aktualisierungsregel deterministisch ist, muss jede Trajektorie irgendwann einen zuvor besuchten Zustand erneut aufsuchen und dann unendlich zyklieren. Dieser sich wiederholende Zyklus ist der Attraktor. Die Menge der Anfangszustände, die zum selben Attraktor führen, ist sein Einzugsbereich. Für N = 32 sind das 4 Milliarden Zustände, doch kritische (K = 2) Netzwerke haben typischerweise nur etwa √N ≈ 6 kurze Attraktoren.

Kauffman argumentierte, dass jedes Gen entweder exprimiert (1) oder unterdrückt (0) ist und dass die Expression jedes Gens von wenigen regulatorischen Eingängen abhängt — genau ein NK-Boolesches-Netzwerk mit K ≈ 2. Er zeigte, dass die Anzahl der Attraktoren in einem K = 2-Netzwerk mit N ≈ 30.000 Knoten (der ungefähren Anzahl menschlicher Gene) etwa √N ≈ 170 beträgt — nahe an der Anzahl der unterschiedlichen menschlichen Zelltypen (~260). Ohne Parameteranpassung reproduziert dasselbe Modell korrekt den Zellzyklus-Attraktor der Hefe S. cerevisiae.

Bei K = 2 (dem Rand des Chaos) koexistieren geordnetes und chaotisches Verhalten: Störungen breiten sich über das Netzwerk aus, ohne abzuklingen oder zu explodieren, sodass Information alle Knoten erreichen kann, während sich dennoch stabile Attraktoren bilden. Dies gilt als Maximierung der Rechenkapazität des Netzwerks — geordnete Netzwerke können Signale nicht weiterleiten (zu starr), chaotische können sie nicht speichern (zu instabil). Dasselbe Konzept liegt dem Reservoir-Computing und den Echo-State-Netzwerken im maschinellen Lernen zugrunde.

Die synchrone Aktualisierung (hier verwendet) berechnet alle N neuen Zustände gleichzeitig aus dem aktuellen Zustand und erzeugt so eine eindeutige deterministische Trajektorie mit einem einzigen Attraktor pro Anfangsbedingung. Die asynchrone Aktualisierung aktualisiert jeweils einen zufälligen Knoten und erzeugt einen stochastischen Prozess mit einer Attraktorverteilung, der allgemein als biologisch realistischer gilt — echte Gene schalten nicht gleichzeitig um. Die beiden Schemata können für dieselbe Netzwerktopologie sehr unterschiedliche Attraktorstrukturen aufweisen.

Da der Zustandsraum endlich ist (2^N Zustände), muss jede Trajektorie zyklieren. Der Simulator verwendet eine Hash-Menge besuchter Zustandsketten, um zu erkennen, wann sich ein Zustand wiederholt; die Zykluslänge ist dann der aktuelle Schritt minus dem Schritt, an dem dieser Zustand erstmals gesehen wurde. Für großes N skaliert die erwartete Attraktorlänge in K = 2-Netzwerken mit √N, was leicht erkennbar ist. Bei chaotischen K ≥ 3-Netzwerken wachsen Zykluslängen exponentiell und werden in der Praxis selten gefunden.

Bei K = 2 „frieren“ viele Knoten schließlich unabhängig von den Anfangsbedingungen auf feste Werte ein — sie sind Teil keines Attraktorzyklus. Die Menge solcher Knoten ist der gefrorene Kern. Derrida und Pomeau (1986) zeigten, dass sich bei K = 2 der gefrorene Kern mit N → ∞ 100 % der Knoten annähert; nur ein verschwindend kleines „relevantes“ Teilnetzwerk treibt die Attraktordynamik an. Dies erklärt, warum selbst sehr große kritische Netzwerke trotz ihrer riesigen Zustandsräume kurze Attraktoren haben.

Beide sind diskrete dynamische Systeme mit binären Zuständen und deterministischen synchronen Aktualisierungsregeln. Der Unterschied liegt in der Topologie: Ein zellulärer Automat hat ein regelmäßiges Gitter, bei dem jede Zelle dieselbe Regel auf ihre räumlichen Nachbarn anwendet. Ein Boolesches Netzwerk hat ein zufälliges Verdrahtungsschema und eine unterschiedliche zufällige Wahrheitstabelle pro Knoten. Wolframs 1D-elementare zelluläre Automaten (256 Regeln über eine 3-Zellen-Nachbarschaft) sind NK-Boolesche-Netzwerke mit regelmäßiger Topologie, N = ∞ und K = 3.

Ja. Die Verzerrung p der Booleschen Funktionen — die Wahrscheinlichkeit, dass ein bestimmter Eintrag der Wahrheitstabelle 1 ist — steuert ebenfalls den Ordnung-Chaos-Übergang. Die wahre Kritikalitätsbedingung ist 2Kp(1−p) = 1, sodass Sie selbst bei K = 3 kritische Dynamik erhalten können, indem Sie die Wahrheitstabellen zu überwiegend 0 oder überwiegend 1 hin verzerren (p ≈ 0,11 oder p ≈ 0,89). Diese verallgemeinerte Version heißt Derrida-Pomeau-Annealed-Näherung.

Mehrere konkrete Netzwerke wurden erfolgreich modelliert: Das 11-Knoten-Segmentpolaritätsnetzwerk von Drosophila melanogaster (Albert und Othmer, 2003) reproduziert ohne Parameteranpassung das korrekte gestreifte Genexpressionsmuster über Parasegmente hinweg. Das 11-Knoten-Zellzyklus-Netzwerk von S. cerevisiae (Li et al., 2004) hat seinen biologischen Attraktor (G1-Phase) als größten Einzugsbereich, der etwa 86 % des Zustandsraums einnimmt — passend zur robusten Rückkehr der Zelle zu G1 nach der Teilung.