Berlin 2005 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

SYBN: Biological and Social Networks

SYBN 3: Biologische und Soziale Netzwerke, Postersitzung

SYBN 3.7: Poster

Monday, March 7, 2005, 14:00–15:30, Poster TU E

Topology regulates pattern formation capacity of binary cellular automata on graphs — •Carsten Marr and Marc-Thorsten Hütt — Bioinformatics Group, Department of Biology, Darmstadt University, Schnittspahnstr. 3-5, D-64287 Darmstadt

We study the effect of topology variation on the dynamic behavior of a system with local update rules. We implement one-dimensional binary cellular automata on graphs with various topologies by formulating two sets of degree-dependent rules, each containing a single parameter. We observe that changes in graph topology induce transitions between different dynamic domains without a formal change in the update rule. Along with topological variations, we study the pattern formation capacities of regular, random, small-world and scale-free graphs. Pattern formation capacity is quantified in terms of two entropy measures, which for standard cellular automata allow a qualitative distinction between the four Wolfram classes. We present a model which explains the differences in a mean-field manner. Implication for our understanding of information transport through complex, network-based systems are discussed.

By implementing these dynamics on protein interaction graphs we can assess the graph’s capacity to produce complex (Wolfram class IV) patterns.