Boolesches Netzwerk

Zustandsraum eines Booleschen Netzwerks mit N=4 Knoten und K=1 Kanten pro Knoten (dünne schwarze Pfeile). Jeder Knoten kann entweder eingeschaltet sein (rot) oder ausgeschaltet (blau). Der Einfachheit halber werden hier nur Kopier-Funktionen verwendet. Die dicken (grauen) Pfeile symbolisieren, was eine (synchrone) Aktualisierung bewirkt. Insgesamt hat das Beispiel vier Fixpunkt-Attraktoren, die als große (orangefarbene) Kreise dargestellt sind. Ferner gibt es zwei Attraktoren der Länge zwei.

Boolesche Netzwerke bezeichnen ein Modell aus der Statistischen Physik. Sie können als Generalisierung des Ising-Modells verstanden werden, nämlich als eine Spin-Dynamik auf einem Digraph $G=(V,E)$. Jedem Knoten $V$ sind dabei sowohl ein boolescher Zustand (oder Spin) als auch eine Boolesche Funktion über die Zustände der eingehenden Knoten zugeordnet.

Diese Aktualisierungsregeln definieren die Systemdynamik, die trotz einfacher Regeln nicht trivial ist. Der Arzt Stuart Kauffman war 1969 der erste Wissenschaftler, der Boolesche Netzwerke als Modell für genetische Netzwerke vorschlug und zwar für den Spezialfall, dass es $N$ Knoten (oder Gene) gibt die jeweils exakt von $K$ anderen Knoten abhängen, deswegen wird diese Variation auch $N$-$K$-Modell genannt. Obwohl Boolesche Netzwerke durch einfache Regeln definiert sind, wurde die Systemdynamik erst nach 2000 mathematisch verstanden.

Obwohl Boolesche Netzwerke eine starke Vereinfachung darstellen (Gene sind nie einfach nur an oder aus), gibt es viele Beispiele, in denen ein Boolesches Modell die richtige Abfolge der Schaltereignisse in einem genetischen Netzwerk vorhersagt.

Mathematischer Hintergrund

Netzwerke sind eine Möglichkeit, die Eigenschaften komplexer Systeme zu untersuchen. Die Topologie eines Graphen spiegelt dabei wider, wie die verschiedenen Einheiten des Systems miteinander wechselwirken. Eine zusätzlich zu der Topologie definierte Dynamik kann dabei entweder die Kanten des Graphen im Laufe der Zeit verändern (Dynamik vom Netzwerk) oder nur die Werte der Knoten (Dynamik auf dem Netzwerk). Bei Booleschen Netzwerken handelt es sich um die zweite Variante.

Eine wichtige Fragestellung bei der Untersuchung Boolescher Netzwerke ist, die globalen Eigenschaften eines gegebenen Ensembles zu analysieren. Die Zahl und die Länge der Attraktoren sind eine Möglichkeit, die globalen Eigenschaften zu quantifizieren. Die Herausforderung ist dabei, dass der Zustandsraum extrem schnell wächst, nämlich mit $2^{N}$. Auch mit modernen Computern sind die Speichergrenzen schnell erreicht. Das einfachste Ensemble sind die zufälligen Booleschen Netzwerke (englisch: Random Boolean Networks, RBN). Hier ist die Graph-Topologie ein Erdős-Rényi-Zufallsgraph. Für RBNS gab es viele Versuche, die Verteilung der Attraktoren mittels Mittelwerte in Abhängigkeit von der Anzahl $N$ der Knoten zu charakterisieren.

Autoren	Jahr	Mittlere Attraktorlänge $\langle A\rangle$	Mittlere Attraktorzahl $\langle \nu \rangle$
Kauffman	1969	$\langle A\rangle \sim {\sqrt {N}}$	$\langle \nu \rangle \sim {\sqrt {N}}$
Bastolla/Parisi	1998	schneller als ein Potenzgesetz, $\langle A\rangle >N^{x}\forall x$	schneller als ein Potenzgesetz, $\langle \nu \rangle >N^{x}\forall x$
Bilke/Sjunnesson	2002		linear mit der Systemgröße, $\langle \nu \rangle \sim N$
Socolar/Kauffman	2003		schneller als linear, $\langle \nu \rangle >N^{x}$ with $x>1$
Samuelsson/Troein	2003		Beweis des superpolynomiales Wachstum, $\langle \nu \rangle >N^{x}\forall x$
Mihaljev/Drossel	2005	analytisches Argument für superpolynomiales Wachstum, $\langle A\rangle >N^{x}\forall x$	analytisches Argument für superpolynomiales Wachstum, $\langle \nu \rangle >N^{x}\forall x$