TU Darmstadt / ULB / TUprints

Eigenschaften von kritischen Booleschen Zufallsnetzwerken

Möller, Marco :
Eigenschaften von kritischen Booleschen Zufallsnetzwerken.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2015)

[img]
Preview
Text
diss.pdf - Accepted Version
Available under Creative Commons Attribution Non-commercial No-derivatives 3.0 de.

Download (38MB) | Preview
Item Type: Ph.D. Thesis
Title: Eigenschaften von kritischen Booleschen Zufallsnetzwerken
Language: German
Abstract:

Boolsche Netzwerke werden häufig als generische Modelle für die Dynamik von interagierenden Einheiten genutzt, deren Zustand sich mit "an" oder "aus" gut beschreiben lässt. Neben sozialen oder ökonomischen Strukturen lässt sich beispielsweise auch die Interaktion von Genen und Proteinen durch Boolsche Netzwerke modellieren. Anhand ihrer Dynamik kann man Boolsche Netzwerke zwei verschiedenen Phasen zuordnen, der gefrorenen Phase sowie der chaotischen Phase. Im ersten Fall läuft die Dynamik des Netzwerkes unabhängig vom Anfangszustand immer auf denselben Fixpunkt. Im zweiten Fall ist sie extrem sensitiv gegenüber Störungen. Von besonderem Interesse sind die kritischen Boolschen Netzwerke, die sich genau auf der Phasengrenze befinden. Diese Arbeit beschäftigt sich mit dynamischen und strukturellen Aspekten von kritischen Boolschen Zufallsnetzen (critical random Boolean networks).

An einer Phasengrenze existiert typischerweise Skaleninvarianz und es gibt somit viele Potenzgesetze für unterschiedliche Charakteristika. Im Falle von Boolschen Netzwerken ist die Größe des gefrorenen Kerns eine solche Charakteristik. Dieser beinhaltet alle Knoten, deren Dynamik für alle Anfangsbedingungen auf demselben Fixpunkt endet. Ein bislang genutzter, sehr effizienter Algorithmus zur Bestimmung des gefrorenen Kerns geht von Knoten mit einer konstanten Aktualisierungsfunktion aus und bestimmt rekursiv weitere konstante Knoten. Es wird gezeigt, dass diese Methode scheitert, wenn der mittlere Grad eine von den verwendeten Aktualisierungsfunktionen abhängige Grenze überschreitet. Im Falle von biased Funktionen liegt diese Grenze bei 4, also durchaus im relevanten Bereich. Die Bildung des gefrorenen Kerns und dessen Robustheit wird mit Hilfe von Simulationen untersucht. Darüber hinaus wird gezeigt, dass einige wichtige Eigenschaften der Daten mittels Mean-Field-Überlegung begründet werden können.

Bei biologischen Netzwerken findet man häufig skalenfreie Ein- und/oder Ausgangsgradverteilungen. Wann immer der Exponent einer solchen skalenfreien Gradverteilung zwischen 2 und 3 liegt, divergiert das zweite Moment dieser Verteilung mit der Netzwerkgröße, was ebenfalls viele natürliche Netzwerke betrifft. Dies führt dazu, dass der Skalenexponent der Größe des gefrorenen Kerns von den Exponenten der Gradverteilungen abhängt. Des Weiteren besteht auch eine Abhängigkeit von der Art des Cut-off der Gradverteilungen. Die meisten bisherigen Ergebnisse sind für solche Netzwerke nicht gültig. Für eben diese Netzwerke werden einige Skalengesetze analytisch hergeleitet und numerisch validiert.

In verschiedenen Anwendungsgebieten existieren Netzwerke, deren Knoten sich stark durch ihre Verknüpfungen oder Dynamik unterscheiden. Dies lässt sich modellieren, indem ähnliche Knoten zu Blöcken zusammengefasst werden. Hierdurch entstehen viele neue Freiheitsgrade in der Modellierung solcher Ensembles. In allgemeinen theoretischen Untersuchungen zu solchen Boolschen Blocknetzwerken stellt sich neben der Frage nach deren Kritikalität auch jene nach der sinnvollen Wahl der zahlreichen Parameter. Eine Möglichkeit, die in dieser Arbeit untersucht wird, ist die Maximierung der Entropie der Ensembles, wobei zwischen struktureller und funktionaler Entropie unterschieden werden muss. Je nach Gewichtung zwischen diesen Entropien und nach mittlerem Grad finden sich für die Struktur der gefundenen Blocknetzwerke mehrere deutlich unterscheidbare Phasen, für deren Ursprung eine Theorie entwickelt wird. Neben einer vollkommen zufälligen Phase kommen auch verschiedene geordnete vor, wie etwa eine core-periphery ähnliche Struktur und eine abgeschwächte Zwei-Gruppen-Struktur. Solche einfachen Makrostrukturen sind die wahrscheinlichsten, solange es außer Kritikalität keine Nebenbedingungen oder zusätzlichen Optimierungskriterien gibt.

Alternative Abstract:
Alternative AbstractLanguage
Boolean networks are often used as generic models for the dynamic of interacting objects whose state can be described as "on" or "off". Beside social or economical structures, Boolean networks can be used for example to model the interaction of genes and proteins. Based on their dynamics, Boolean networks can be assigned to different phases, either the frozen or the chaotic phase. In the first case, the dynamic of the network will always end in the same fixed point regardless its initial state. In the second case, it is very sensitive to disturbances. So-called critical networks, being at the phase boundary, are typically from special interest. This work deals with dynamical and structural aspects of critical random Boolean networks. At a phase boundary, scale invariance exists typically and thus there are many power laws for different characteristics of the system. In case of Boolean networks, such a characteristic is the size of the frozen core. This core contains all nodes whose dynamic will end for all initial conditions on the same fixed point. A previously used, very efficient algorithm for obtaining the frozen core starts from the nodes with constant update functions and determines recursively further constant nodes. It is demonstrated that this method fails when the number of inputs per node exceeds a limit which depends on the set of update functions. In case of biased functions, this limit is 4 and therewith quite in a relevant region. The process of formation of the frozen core and its robustness was studied by computer simulation. Furthermore, it is shown that several important features of the data can be derived by a mean-field calculation. Biological networks often show a scale free in- and / or out-degree distribution. Whenever the power-law exponent is between 2 and 3, the second moment of the distribution diverges with the network size, which also often occurs in nature. As a result, the scaling exponent of the size of the frozen core depends on the exponents of the degree distributions. Furthermore, there is a dependency on the type of cut-off of the degree distributions. Most previous results are not valid for such networks, and a set of new scaling laws is presented in this work. These scaling laws were derived analytically and elaborately validated by numerical computations. In different areas of application, networks occur whose nodes differ strongly in link structure or dynamic. This can be modeled by pooling similar nodes into blocks. Hereby, many new degrees of freedom for modeling such ensembles arise, and therewith the question of how to choose these many different parameters in a canonical way. The presented approach for selecting parameters consists of maximizing the entropy of the ensemble, whereby it is to differentiate between structural and functional entropy. Depending on the weighting of these entropies and on the average degree, several phases can be clearly distinguished, and a theory is developed. Occurring phases range from a fully random structure to several ordered ones, including a core-periphery-like structure, and an attenuated two-group structure. In the absence of competing optimization criteria and any constraints other than criticality, such simple large-scale structures are the most likely to occur. At a phase boundary, scale invariance exists typically and thus there are many power laws for different characteristics of the system. In case of Boolean networks, such a characteristic is the size of the frozen core. This core contains all nodes whose dynamic will end for all initial conditions on the same fixed point. A previously used, very efficient algorithm for obtaining the frozen core starts from the nodes with constant update functions and determines recursively further constant nodes. It is demonstrated that this method fails when the number of inputs per node exceeds a limit which depends on the set of update functions. In case of biased functions, this limit is 4 and therewith quite in a relevant region. The process of formation of the frozen core and its robustness was studied by computer simulation. Furthermore, it is shown that several important features of the data can be derived by a mean-field calculation. Biological networks often show a scale free in- and / or out-degree distribution. Whenever the power-law exponent is between 2 and 3, the second moment of the distribution diverges with the network size, which also often occurs in nature. As a result, the scaling exponent of the size of the frozen core depends on the exponents of the degree distributions. Furthermore, there is a dependency on the type of cut-off of the degree distributions. Most previous results are not valid for such networks, and a set of new scaling laws is presented in this work. These scaling laws were derived analytically and elaborately validated by numerical computations. In different areas of application, networks occur whose nodes differ strongly in link structure or dynamic. This can be modeled by pooling similar nodes into blocks. Hereby, many new degrees of freedom for modeling such ensembles arise, and therewith the question of how to choose these many different parameters in a canonical way. The presented approach for selecting parameters consists of maximizing the entropy of the ensemble, whereby it is to differentiate between structural and functional entropy. Depending on the weighting of these entropies and on the average degree, several phases can be clearly distinguished, and a theory is developed. Occurring phases range from a fully random structure to several ordered ones, including a core-periphery-like structure, and an attenuated two-group structure. In the absence of competing optimization criteria and any constraints other than criticality, such simple large-scale structures are the most likely to occur. English
Place of Publication: Darmstadt
Classification DDC: 500 Naturwissenschaften und Mathematik > 530 Physik
Divisions: 05 Department of Physics > Institute for condensed matter physics > Bio Physics
05 Department of Physics > Institute for condensed matter physics > Statistische Physik und komplexe Systeme
Date Deposited: 20 Apr 2015 10:19
Last Modified: 20 Apr 2015 10:19
URN: urn:nbn:de:tuda-tuprints-44910
Referees: Drossel, Prof. Dr. Barbara and Dünweg, Prof. Dr. Burkhard
Refereed: 18 February 2015
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/4491
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year