{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T03:56:39Z","timestamp":1773114999451,"version":"3.50.1"},"reference-count":62,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2012,6,5]],"date-time":"2012-06-05T00:00:00Z","timestamp":1338854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Cellular automata (CA) are a remarkably efficient tool for exploring general properties of complex systems and spatiotemporal patterns arising from local rules. Totalistic cellular automata, where the update rules depend only on the density of neighboring states, are at the same time a versatile tool for exploring dynamical processes on graphs. Here we briefly review our previous results on cellular automata on graphs, emphasizing some systematic relationships between network architecture and dynamics identified in this way. We then extend the investigation towards graphs obtained in a simulated-evolution procedure, starting from Erd\u0151 s\u2013R\u00e9nyi (ER) graphs and selecting for low entropies of the CA dynamics. Our key result is a strong association of low Shannon entropies with a broadening of the graph\u2019s degree distribution.<\/jats:p>","DOI":"10.3390\/e14060993","type":"journal-article","created":{"date-parts":[[2012,6,5]],"date-time":"2012-06-05T14:23:55Z","timestamp":1338906235000},"page":"993-1010","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Cellular Automata on Graphs: Topological Properties of ER Graphs Evolved towards Low-Entropy Dynamics"],"prefix":"10.3390","volume":"14","author":[{"given":"Carsten","family":"Marr","sequence":"first","affiliation":[{"name":"Institute for Bioinformatics and Systems Biology, Helmholtz Zentrum M\u00fcnchen, German Research Center for Environmental Health, D-85764 Neuherberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc-Thorsten","family":"H\u00fctt","sequence":"additional","affiliation":[{"name":"Computational Systems Biology, School of Engineering and Science, Jacobs University Bremen, D-28759 Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2012,6,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1038\/35036627","article-title":"The large-scale organization of metabolic networks","volume":"407","author":"Jeong","year":"2000","journal-title":"Nature"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1038\/nrg1272","article-title":"Network biology: Understanding the cell\u2019s functional organization","volume":"5","author":"Oltvai","year":"2004","journal-title":"Nat. Rev. Genet."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1126\/science.1073374","article-title":"Hierarchical organization of modularity in metabolic networks","volume":"297","author":"Ravasz","year":"2002","journal-title":"Science"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1038\/nature03288","article-title":"Functional cartography of complex metabolic networks","volume":"433","author":"Guimera","year":"2005","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1538","DOI":"10.1126\/science.1089167","article-title":"Superfamilies of evolved and designed networks","volume":"303","author":"Milo","year":"2004","journal-title":"Science"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1038\/nrg2102","article-title":"Network motifs: Theory and experimental approaches","volume":"8","author":"Alon","year":"2007","journal-title":"Nat. Rev. Genet."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s11005-006-0123-1","article-title":"Complex networks: From graph theory to biology","volume":"78","author":"Lesne","year":"2006","journal-title":"Lett. Math. Phys."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1038\/35065725","article-title":"Exploring complex networks","volume":"410","author":"Strogatz","year":"2001","journal-title":"Nature"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1073\/pnas.0706851105","article-title":"Maps of random walks on complex networks reveal community structure","volume":"105","author":"Rosvall","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"114102","DOI":"10.1103\/PhysRevLett.96.114102","article-title":"Synchronization reveals topological scales in complex networks","volume":"96","author":"Arenas","year":"2006","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"pe44","DOI":"10.1126\/scisignal.281pe44","article-title":"Understanding modularity in molecular networks requires dynamics","volume":"2","author":"Alexander","year":"2009","journal-title":"Sci. Signal."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"11775","DOI":"10.1073\/pnas.0501094102","article-title":"Circuit topology and the evolution of robustness in two-gene circadian oscillators","volume":"102","author":"Wagner","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/j.bulsci.2005.02.006","article-title":"Dynamical distance: Coarse grains, pattern recognition, and network analysis","volume":"129","author":"Schulman","year":"2005","journal-title":"Bull. Sci. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.physa.2005.02.019","article-title":"Topology regulates pattern formation capacity of binary cellular automata on graphs","volume":"354","author":"Marr","year":"2005","journal-title":"Physica A"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.physleta.2008.12.013","article-title":"Outer-totalistic cellular automata on graphs","volume":"373","author":"Marr","year":"2009","journal-title":"Phys. Lett. A"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"13773","DOI":"10.1073\/pnas.0503610102","article-title":"Spontaneous evolution of modularity and network motifs","volume":"102","author":"Kashtan","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"13711","DOI":"10.1073\/pnas.0611630104","article-title":"Varying environments can speed up evolution","volume":"104","author":"Kashtan","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1111\/j.1558-5646.2009.00684.x","article-title":"Extinctions in heterogeneous environments and the evolution of modularity","volume":"63","author":"Kashtan","year":"2009","journal-title":"Evolution"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"48001","DOI":"10.1209\/0295-5075\/79\/48001","article-title":"Evolutionary design of functional networks robust against noise","volume":"79","author":"Kaluza","year":"2007","journal-title":"Europhys. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"15101","DOI":"10.1103\/PhysRevE.75.015101","article-title":"Design and statistical properties of robust functional networks: A model study of biological signal transduction","volume":"75","author":"Kaluza","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1063\/1.2945228","article-title":"Self-correcting networks: Function, robustness, and motif distributions in biological signal processing","volume":"18","author":"Kaluza","year":"2008","journal-title":"Chaos"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1140\/epjb\/e2010-00200-9","article-title":"Evolutionary design of oscillatory genetic networks","volume":"76","author":"Kobayashi","year":"2010","journal-title":"Eur. Phys. J. B"},{"key":"ref_24","first-page":"288","article-title":"The general and logical theory of automata","volume":"Volume 5","author":"Taub","year":"1963","journal-title":"Design of Computers, Theory of Automata and Numerical Analysis"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1038\/scientificamerican1070-120","article-title":"Mathematical games: The fantastic combinations of John Conway\u2019s new solitaire game \u201cLife\u201d","volume":"10","author":"Gardner","year":"1970","journal-title":"Sci. Am."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1073\/pnas.72.3.956","article-title":"Life games and statistical models","volume":"72","author":"Dresden","year":"1975","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1103\/RevModPhys.55.601","article-title":"Statistical mechanics of cellular automata","volume":"55","author":"Wolfram","year":"1983","journal-title":"Rev. Mod. Phys."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-2789(84)90245-8","article-title":"Universality and complexity in cellular automata","volume":"10","author":"Wolfram","year":"1984","journal-title":"Physica D"},{"key":"ref_29","unstructured":"Deutsch, A., and Dormann, S. (2005). Cellular Automaton Modeling and Biological Pattern Formation, Birkh\u00e4user."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1126\/science.233.4762.425","article-title":"Percolation and galaxies","volume":"233","author":"Schulman","year":"1986","journal-title":"Science"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0022-5193(05)80737-4","article-title":"A model for simulating cognate recognition and response in the immune system","volume":"158","author":"Seiden","year":"1992","journal-title":"J. Theor. Biol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.physleta.2005.08.096","article-title":"Similar impact of topological and dynamic noise on complex patterns","volume":"349","author":"Marr","year":"2006","journal-title":"Phys. Lett. A"},{"key":"ref_33","first-page":"1","article-title":"Topology regulates the distribution pattern of excitations in excitable dynamics on graphs","volume":"74","author":"Marr","year":"2006","journal-title":"Phys. Rev. E"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"e1000190","DOI":"10.1371\/journal.pcbi.1000190","article-title":"Organization of excitable dynamics in hierarchical biological networks","volume":"4","author":"Hilgetag","year":"2008","journal-title":"PLoS Comput. Biol."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevE.75.041917","article-title":"Regularizing capacity of metabolic networks","volume":"75","author":"Marr","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"15551","DOI":"10.1073\/pnas.0404843101","article-title":"Emergence of complex dynamics in a simple model of signaling networks","volume":"101","author":"Amaral","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"12085","DOI":"10.1073\/pnas.0400672101","article-title":"Efficient system-wide coordination in noisy environments","volume":"101","author":"Moreira","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"036109","DOI":"10.1103\/PhysRevE.68.036109","article-title":"Investigation of the forest-fire model on a small-world network","volume":"68","author":"Graham","year":"2003","journal-title":"Phys. Rev. E"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1038\/ng881","article-title":"Network motifs in the transcriptional regulation network of Escherichia coli","volume":"31","author":"Milo","year":"2002","journal-title":"Nat. Genet."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"e1000725","DOI":"10.1371\/journal.pcbi.1000725","article-title":"Signatures of arithmetic simplicity in metabolic network architecture","volume":"6","author":"Riehl","year":"2010","journal-title":"PLoS Comput. Biol."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"9743","DOI":"10.1073\/pnas.0903206106","article-title":"Toolbox model of evolution of prokaryotic metabolic networks and their regulation","volume":"106","author":"Maslov","year":"2009","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1186\/1471-2105-7-118","article-title":"Low degree metabolites explain essential reactions and enhance modularity in biological networks","volume":"7","author":"Samal","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"026107","DOI":"10.1063\/1.2737828","article-title":"Optimal flux patterns in cellular metabolic networks","volume":"17","author":"Almaas","year":"2007","journal-title":"Chaos"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1038\/nature02289","article-title":"Global organization of metabolic fluxes in the bacterium Escherichia coli","volume":"427","author":"Almaas","year":"2004","journal-title":"Nature"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Basler, G., Grimbs, S., Ebenh\u00f6h, O., Selbig, J., and Nikoloski, Z. (2011). Evolutionary significance of metabolic network properties. J. R. Soc. Interface.","DOI":"10.1098\/rsif.2011.0652"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1397","DOI":"10.1093\/bioinformatics\/btr145","article-title":"Mass-balanced randomization of metabolic networks","volume":"27","author":"Basler","year":"2011","journal-title":"Bioinformatics"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1038\/nrmicro1023","article-title":"Genome-scale models of microbial cells: Evaluating the consequences of constraints","volume":"2","author":"Price","year":"2004","journal-title":"Nat. Rev. Microbiol."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/j.copbio.2003.08.001","article-title":"Advances in flux balance analysis","volume":"14","author":"Kauffman","year":"2003","journal-title":"Curr. Opin. Biotechnol."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1038\/nbt1401","article-title":"The growing scope of applications of genome-scale metabolic reconstructions using Escherichia coli","volume":"26","author":"Feist","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1093\/bioinformatics\/19.2.270","article-title":"Reconstruction of metabolic networks from genome data and analysis of their global structure for various organisms","volume":"19","author":"Ma","year":"2003","journal-title":"Bioinformatics"},{"key":"ref_52","first-page":"290","article-title":"On random graphs","volume":"6","year":"1959","journal-title":"Publ. Math."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"178702","DOI":"10.1103\/PhysRevLett.92.178702","article-title":"Hierarchy measures in complex networks","volume":"92","author":"Trusina","year":"2004","journal-title":"Phys. Rev. Lett."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1098\/rstb.1952.0012","article-title":"The chemical basis of morphogenesis","volume":"237","author":"Turing","year":"1952","journal-title":"Phil. Trans. Roy. Soc. Lond. B Biol. Sci."},{"key":"ref_57","first-page":"544","article-title":"Turing patterns in network-organized activator-inhibitor systems","volume":"6","author":"Nakao","year":"2010","journal-title":"Nature"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Schuster, H.G. (2008). Reviews of Nonlinear Dynamics and Complexity, Wiley.","DOI":"10.1002\/9783527626359"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"056102","DOI":"10.1103\/PhysRevE.80.056102","article-title":"Boolean networks with reliable dynamics","volume":"80","author":"Peixoto","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"158701","DOI":"10.1103\/PhysRevLett.98.158701","article-title":"Basin entropy in Boolean network ensembles","volume":"98","author":"Krawitz","year":"2007","journal-title":"Phys. Rev. Lett."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"e1672","DOI":"10.1371\/journal.pone.0001672","article-title":"Boolean network model predicts cell cycle sequence of fission yeast","volume":"3","author":"Davidich","year":"2008","journal-title":"PLoS One"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1016\/j.jtbi.2006.11.012","article-title":"Superstability of the yeast cell-cycle dynamics: Ensuring causality in the presence of biochemical stochasticity","volume":"245","author":"Braunewell","year":"2007","journal-title":"J. Theor. Biol."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/14\/6\/993\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:50:37Z","timestamp":1760219437000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/14\/6\/993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,5]]},"references-count":62,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2012,6]]}},"alternative-id":["e14060993"],"URL":"https:\/\/doi.org\/10.3390\/e14060993","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,5]]}}}