Critical phenomena and dynamical phase transitions in Boolean networks

Boole’sche Netzwerke werden als hoch nicht-lineare dynamische Modelle in der Biologie, Soziologie und Wirtschaftwissenschaften verwendet. Schon bei der Einfuhrung als genetische Regelnetzwerke in den späten 1960ern durch Stuart Kauffman wurden zwei Phasen in der Dynamik unterschieden: eine geordnete Phase, wo mögliche Störungen rasch verschwinden, und die ungeordnete Phase, wo sich anfänglich kleine Störungen auf das ganze Netzwerk ausbreiten können. In den 1980ern fuhrten statistische Uberlegungen von Bernard Derrida und Kollegen zu einigen analytischen Ergebnissen fur das dynamische Verhalten dieser Netzwerke, im Speziellen wurde eine statistische Charakterisierung der Kritischen Bedingung fur den Phasenubergang abgeleitet. In dieser Arbeit wurden einige neuere Ergebnisse und Entwicklungen gesammelt und formal präsentiert, wobei ein Hauptaugenmerk auf die Kritische Bedingung gelegt wurde. Diese ist für viele Netzwerke in der Natur von Bedeutung, da deren Dynamik oft in der Nähe des Phasenübergangs liegt. Die Ableitung der gekoppelten Iterationsgleichungen für die beiden makroskopischen Parameter Magnetisierung und Hammingdistanz wird erklärt für beliebige Mischungen von Boole’schen Funktionen und Verteilungen von Verknupfungsgraden. Aus diesen Iterationsgleichungen wird die Kritische Bedingung berechnet, und gezeigt, dass diese nur von der gemittelten “Empfindlichkeit“ der Verteilung der Funktionen abhängt. Weiters wird gezeigt, dass das Verwenden von ”Höheren Empfindlichkeiten” in der Iterationsgleichung der Hammingdistanz aquivalent ist zu einer Beschränkung der Magnetisierung, die aber nicht uber die Zeit aufrecht erhalten werden kann, und daher einen falschen Fixpunkt in der Hammingdistanz voraussagt. Im zweiten Teil der Arbeit wird dieser Formalismus auf Lineare Schwellwertfunktionen angewendet. Lineare Schwellwertfunktionen sind eine kleine Untermenge aller möglichen Boole’schen Funktionen und eine explizite Projektionsgleichung auf diese allgemeinen Funktionen ist in dieser Arbeit angegeben. Fur verschiedene Boole’sche Netzwerke wurden Phasendiagramme berechnet, wobei zwei verschiedene Parameter verwendet wurden, der Schwellwert h und die Asymmetrie p in der Verteilung der Gewichte, was ein zusätzlicher Parameter im Vergleich mit einigen früheren Arbeiten ist. Zum Schluss wird bewiesen, dass fur eine einfache Mischung aus Linearen Schwellwertfunktionen der Parameterbereich der geordnete Phase mit steigender Konnektivität K wächst, und der Parameterbereich der ungeordnete Phase auf einen einzigen Wert zusammenschrumpft im Grenzübergang K gegen unendlich. Dieses Verhalten ist konträr zum Kauffman-Modell, wo das gegenteilige Verhalten beobachtet wird: der Parameterbereich der ungeordneten Phase nimmt das ganze Intervall im Grenzübergang K gegen unendlich ein. Das ist ein interessantes Ergebnis, weil biologische Netzwerke normalerweise eine höhere Verknupfungsrate als den kritischen Wert Kc = 2 im ursprunglichen Kauffman-Modell haben, so dass eine realistischere Topologie für das Boole’sche Netzwerk verwendet werden kann. In diesen realistischeren Topologien können dann auch höhere Verknüpfungsraten auftreten, ohne Extremwerte der Modellparameter annehmen zu müssen. Boole’sche Netzwerke werden als hoch nicht-lineare dynamische Modelle in der Biologie, Soziologie und Wirtschaftwissenschaften verwendet. Schon bei der Einfuhrung als genetische Regelnetzwerke in den späten 1960ern durch Stuart Kauffman wurden zwei Phasen in der Dynamik unterschieden: eine geordnete Phase, wo mögliche Störungen rasch verschwinden, und die ungeordnete Phase, wo sich anfänglich kleine Störungen auf das ganze Netzwerk ausbreiten können. In den 1980ern fuhrten statistische Uberlegungen von Bernard Derrida und Kollegen zu einigen analytischen Ergebnissen fur das dynamische Verhalten dieser Netzwerke, im Speziellen wurde eine statistische Charakterisierung der Kritischen Bedingung fur den Phasenubergang abgeleitet. In dieser Arbeit wurden einige neuere Ergebnisse und Entwicklungen gesammelt und formal präsentiert, wobei ein Hauptaugenmerk auf die Kritische Bedingung gelegt wurde. Diese ist für viele Netzwerke in der Natur von Bedeutung, da deren Dynamik oft in der Nähe des Phasenübergangs liegt. Die Ableitung der gekoppelten Iterationsgleichungen für die beiden makroskopischen Parameter Magnetisierung und Hammingdistanz wird erklärt für beliebige Mischungen von Boole’schen Funktionen und Verteilungen von Verknupfungsgraden. Aus diesen Iterationsgleichungen wird die Kritische Bedingung berechnet, und gezeigt, dass diese nur von der gemittelten “Empfindlichkeit“ der Verteilung der Funktionen abhängt. Weiters wird gezeigt, dass das Verwenden von ”Höheren Empfindlichkeiten” in der Iterationsgleichung der Hammingdistanz aquivalent ist zu einer Beschränkung der Magnetisierung, die aber nicht uber die Zeit aufrecht erhalten werden kann, und daher einen falschen Fixpunkt in der Hammingdistanz voraussagt. Im zweiten Teil der Arbeit wird dieser Formalismus auf Lineare Schwellwertfunktionen angewendet. Lineare Schwellwertfunktionen sind eine kleine Untermenge aller möglichen Boole’schen Funktionen und eine explizite Projektionsgleichung auf diese allgemeinen Funktionen ist in dieser Arbeit angegeben. Fur verschiedene Boole’sche Netzwerke wurden Phasendiagramme berechnet, wobei zwei verschiedene Parameter verwendet wurden, der Schwellwert h und die Asymmetrie p in der Verteilung der Gewichte, was ein zusätzlicher Parameter im Vergleich mit einigen früheren Arbeiten ist. Zum Schluss wird bewiesen, dass fur eine einfache Mischung aus Linearen Schwellwertfunktionen der Parameterbereich der geordnete Phase mit steigender Konnektivität K wächst, und der Parameterbereich der ungeordnete Phase auf einen einzigen Wert zusammenschrumpft im Grenzübergang K gegen unendlich. Dieses Verhalten ist konträr zum Kauffman-Modell, wo das gegenteilige Verhalten beobachtet wird: der Parameterbereich der ungeordneten Phase nimmt das ganze Intervall im Grenzübergang K gegen unendlich ein. Das ist ein interessantes Ergebnis, weil biologische Netzwerke normalerweise eine höhere Verknupfungsrate als den kritischen Wert Kc = 2 im ursprunglichen Kauffman-Modell haben, so dass eine realistischere Topologie für das Boole’sche Netzwerk verwendet werden kann. In diesen realistischeren Topologien können dann auch höhere Verknüpfungsraten auftreten, ohne Extremwerte der Modellparameter annehmen zu müssen.Boolean Networks have been used as highly non-linear dynamical models in biology, sociology and economics. Together with the introduction as gene regulatory networks in the late 1960s, Stuart Kauffman established two different phases of the dynamics in Boolean Networks: the ordered phase, where eventual perturbations vanish rather quickly, and the disordered phase, where a small perturbation might spread over the whole network. In the 1980s statistical considerations by Bernard Derrida and coworkers yielded analytical results for the dynamical behavior of those networks, especially a statistical characterization of the critical condition for this phase transition was obtained. In this work, recent developments have been compiled and presented in a rather formal way, with special emphasis on this critical condition, which is important, because many networks in nature are believed to be close to this dynamical phase transition. An approach for the derivation of coupled iteration equations of the macroscopic parameters magnetization and Hamming distance is explained for arbitrary mixtures of Boolean functions and distribution of in-degrees. From these iteration equations the critical condition is derived, showing that this condition only depends on the average sensitivity of the mixture of Boolean functions. Furthermore, the equivalence of using higher sensitivities in the construction of the polynomial for the Hamming distance is established to be a restriction to the magnetization, which cannot be maintained over time, and therefore fails to predict the fixed point in the Hamming distance observed in computer simulations. In the second part of this work, this formalism has been applied to Linear Threshold functions. They are a subclass of all possible Boolean functions and an explicit projection to Boolean functions is given. Complete phase diagrams have been calculated for several different Boolean Networks with all functions being Linear Threshold functions, where an two parameters have been included, the threshold $h$ and the asymmetry $p$ in the distribution of weights, which is an additional degree of freedom compared to several earlier publications. Finally, it has been proven for a simple mixture of Linear Threshold functions, that the parameter region corresponding to the ordered phase actually grows with increased connectivity $K$, and the parameter region of the disordered phase shrinks to a single value in the limit $K\rightarrow\infty$. This is contrary to the Kauffman model, where the opposite behavior is observed: the parameter region of the disordered phase spans the complete interval in the limit $K\rightarrow\infty$. This is an interesting result, because biological networks usually have a connectivity larger than the critical value $K_c=2$ in the (unbiased) Kauffman model, so that a more realistic topology could be imposed on the BN, where also nodes with a higher in-degree occur, without being restricted to extreme values of the external parameters