# Boolesches Netzwerk

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$ |