Proceedings Series

Vol. 3 (2010), No. 2, pp. 251 – 493

Summer Solstice 2009 International Conference on Discrete Models of Complex Systems

Gdańsk, Poland; June 22–24, 2009

Assortativity in Random Line Graphs


We investigate the degree–degree correlations in the Erdös–Rényi networks, the growing exponential networks and the scale-free networks. We demonstrate that these correlations are the largest for the exponential networks. We calculate also these correlations in the line graphs, formed from the considered networks. Theoretical and numerical results indicate that all the line graphs are assortative, i.e. the degree–degree correlation is positive.

Generalized Firing Squad Synchronization Protocols for One-dimensional Cellular Automata — a Survey


In the present article, we firstly examine the state transition rule sets for the generalized firing squad synchronization algorithms that give a finite-state protocol for synchronizing large-scale cellular automata. We focus on the fundamental generalized firing squad synchronization algorithms studied in recent fifty years, each operating in optimum- or non-optimum-steps on one-dimensional cellular arrays. A new eight-state algorithm is proposed. The eight-state optimum-step algorithm is the smallest one known at present in the class of generalized optimum-step firing squad synchronization protocols. A six-state non-optimum-step algorithm is also examined. We also construct a survey of the generalized synchronization algorithms and compare transition rule sets with respect to the number of internal states of each finite state automaton, the number of transition rules realizing the synchronization, and the number of state-changes on the array.

Small-world Bifurcations in an Opinion Model


We study a cellular automaton opinion formation model of Ising type, with antiferromagnetic pair interactions modeling anticonformism, and ferromagnetic plaquette terms modeling the social norm constraints. For a sufficiently large connectivity, the mean-field equation for the average magnetization (opinion density) is chaotic. This “chaoticity” would imply irregular coherent oscillations of the whole society, that may eventually lead to a sudden jump into an absorbing state, if present. However, simulations on regular one-dimensional lattices show a different scenario: local patches may oscillate following the mean-field description, but these oscillations are not correlated spatially, so the average magnetization fluctuates around zero (average opinion near one half). The system is chaotic, but in a microscopic sense where local fluctuations tend to compensate each other. By varying the long-range rewiring of links, we trigger a small-world effect. We observe a bifurcation diagram for the magnetization, with period doubling cascades ending in a chaotic phase. As far as we know, this is the first observation of a small-world induced bifurcation diagram. The social implications of this transition are also interesting. In the presence of strong “anticonformistic” (or “antinorm”) behavior, efforts for promoting social homogenization may trigger violent oscillations.

Decisional Processes with Boolean Neural Network: the Emergence of Mental Schemes


Human decisional processes result from the employment of selected quantities of relevant information, generally synthesized from environmental incoming data and stored memories. Their main goal is the production of an appropriate and adaptive response to a cognitive or behavioral task. Different strategies of response production can be adopted, among which haphazard trials, formation of mental schemes and heuristics. In this paper, we propose a model of Boolean neural network that incorporates these strategies by recurring to global optimization strategies during the learning session. The model characterizes as well the passage from an unstructured/chaotic attractor neural network typical of data-driven processes to a faster one, forward-only and representative of schema-driven processes. Moreover, a simplified version of the Iowa Gambling Task (IGT) is introduced in order to test the model. Our results match with experimental data and point out some relevant knowledge coming from psychological domain.

Critical Phenomena in Cellular Automata: Perturbing the Update, the Transitions, the Topology


We survey the effect of perturbing the regular structure of a cellular automaton (CA). We are interested in critical phenomena, i.e., when a continuous variation in the local rules of a cellular automaton triggers a qualitative change of its global behaviour. We focus on three types of perturbations: (a) when the updating is made asynchronous, (b) when the transition rule is made stochastic, (c) when topological defects are introduced. It is shown that although these perturbations have various effects on CA models, they are generally identified as first-order or second-order phase transitions. We present open questions related to this topic and discuss some implications on the use of CA to model natural phenomena.

Taylor’s Power Law for Fluctuation Scaling in Traffic


In this article, we study transportation network in Minnesota. We show that the system is characterized by Taylor’s power law for fluctuation scaling with nontrivial values of the scaling exponent. We also show that the characteristic exponent does not unequivocally characterize a given road network, as it may differ within the same network if one takes into account location of observation points, season, period of day, or traffic intensity. The results are set against Taylor’s fluctuation scaling in the Nagel–Schreckenberg cellular automaton model for traffic. It is shown that Taylor’s law may serve, beside the fundamental diagram, as an indicator of different traffic phases (free flow, traffic jam etc.).

Alphabetic Bipartite Network (\(\alpha \)-BiN): Theory and Case Study


Recently, much attention has been paid in analyzing and modeling bipartite network (BNW) due to its importance in many fields like information science, biology, social science, economics. Here we have emphasized on growth of a special type of BNW where the number of nodes in one set is almost fixed. This type of systems can be represented as an Alphabetic Bipartite Network (\(\alpha \)-BiN) where there are two kinds of nodes representing the elementary units and their combinations, respectively [5]. There is an edge between a node corresponding to an elementary unit \(u\) and a node corresponding to a particular combination \(v\) if \(u\) is present in \(v\). The partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. In this paper we reveal some characterizations of \(\alpha \)-BiN growth and give a real world example of \(\alpha \)-BiN. We have done extensive experiments by means of computer simulations of different growth models of \(\alpha \)-BiN to characterize them. We present a practical example of this type of networks, i.e. protein protein complex network where set of proteins are fixed and set of complexes are growing.

GCA-w: Global Cellular Automata with Write-Access


The novel GCA-w model (Global Cellular Automata with Write access) is presented which is based on the GCA (Global Cellular Automata) model. The GCA model is a massively parallel model like the cellular automata model. In the CA model, the cells have static links to their local neighbors whereas in the GCA model, the links are dynamic according to a special local rule. In both models, the access is “read-only”. Thereby no write conflict can occur and all cells can update their states independently in parallel. The GCA model is useful for many parallel problems that can be described by a non-local and changing neighborhood. A shortcoming of the GCA model is the missing write access to neighboring cells. Although a write access can be emulated in \(O(\log n)\) time this slowdown may not be acceptable in some practical applications. Therefore, the GCA-w model was developed. The GCA-w model allows to change the states of the neighboring cells as well as the state of the own cell. Thereby certain parallel algorithms can be described more appropriately and the number of active cells can be controlled by the cells themselves in a decentralized way. Activity control also enables dynamic resource sharing and the reduction of power consumption. The usefulness of the GCA-w model is demonstrated by some fine-grain parallel applications: one-to-all communication, synchronization and moving particles.

Langevin Equations for Modeling Evacuation Processes


In the paper the processes of evacuating rooms and buildings of different types are modeled using Langevin equations with the social force term describing the mental component in pedestrian motion. The level of panic during an evacuation is connected with the desired velocity — a parameter in the social force term. Introducing an additional vertical force exerted on pedestrians on the staircases makes it possible to extend the application of the model to multistorey buildings. Numerical simulations make it possible to observe trajectories of pedestrians and to calculate the time it takes to evacuate different buildings. Factors influencing the effectiveness of evacuation are discussed.

Modeling of Intercellular Connections in the Sinoatrial Node


Electrochemical activity of the sinoatrial node — the first natural heart pacemaker, relies on coordinated activity of sinoatrial cells and on signal transduction by intercellular connections. The modified Greenberg–Hastings automaton is used to model the electrochemical activity of a cell and basic intercellular interactions. A stochastic 2D lattice with preference set to lateral connections is a starting point in the construction of the network of intercellular connections. Then a flat structure of the network is carefully wrinkled by rewiring procedure. The rewiring is restricted to neighboring cells — local rewiring, and it favors densely connected cells — preferential rewiring. In simulations we find that if density of intercellular connections reaches \(d=0.60\) then spirals of activity clusters emerge robustly. However to observe strong spirals: oscillating with the shortest period possible and driving dynamics in the whole network, the intercellular connections have to be rewired locally and preferentially. The critical value of density corresponds very accurately to the known value at which the canine sinoatrial node works.

Surface Dynamic Process Simulation with the Use of Cellular Automata


Cellular automata are known for many applications, especially for physical and biological simulations. Universal cellular automata can be used for modelling complex natural phenomena. The paper presents simulation of surface dynamic process. Simulation uses 2-dimensional cellular automata algorithm. Modelling and visualisation were created by in-house developed software with standard OpenGL graphic library.

From Cellular Automaton Rules to a Macroscopic Mean-field Description


Cellular automata (CA) may be viewed as simple models of self-organizing complex systems. Here, we focus on an important class of CA, the so-called lattice-gas cellular automata (LGCA), which have been proposed as models of spatio-temporal pattern formation in biology. As an example, we introduce a LGCA model for a simple biological growth process based on randomly moving and proliferating agents. We demonstrate how a mean-field approximation can yield insight into the formation of spatial patterns and calculate important macroscopic observables for the biological growth process. In particular, we address the role of the diffusion strength in the approximation by distinguishing well-stirred and spatially distributed cases. Finally, we discuss the potential and limitations of the mean-field description in analyzing biological pattern formation.

Influenza Differentiation and Evolution


The aim of the study is to do a very wide analysis of HA, NA and M influenza gene segments to find short nucleotide regions, which differentiate between strains (i.e. H1, H2, \(\ldots \) etc.), hosts, geographic regions, time when sequence was found and combination of time and region using a simple methodology. Finding regions differentiating between strains has as its goal the construction of a Luminex microarray which will allow quick and efficient strain recognition. Discovery for the other splitting factors could shed light on structures significant for host specificity and on the history of influenza evolution. A large number of places in the HA, NA and M gene segments were found that can differentiate between hosts, regions, time and combination of time and region. Also very good differentiation between different Hx strains can be seen. We link one of our findings to a proposed stochastic model of creation of viral phylogenetic trees.

Synchronization of Coupled Oscillators in a Local One-dimensional Kuramoto Model


A modified Kuramoto model of synchronization in a finite discrete system of locally coupled oscillators is studied. The model consists of \(N\) oscillators with random natural frequencies arranged on a ring. It is shown analytically and numerically that finite-size systems may have many different synchronized stable solutions which are characterised by different values of the winding number. The lower bound for the critical coupling \(k_{\rm c}\) is given, as well as an algorithm for its exact calculation. It is shown that in general phase-locking does not lead to phase coherence in 1D.

Complex and Chaotic Dynamics, Basins of Attraction, and Memory in Discrete Networks


The emergence of interacting structures in cellular automata is intimately connected with notions of order, complexity and chaos, which depend on the degree of converge to attractors. Information can be encrypted by hiding in chaotic trajectories. In the general case of “random” networks, content addressable memory is apparent in the precise arrangement of state-space into basins of attraction and subtrees, a concept of memory and learning at the most basic level. This paper is an overview of the ideas, results and applications illustrated with images created in DDLab.

Digital Laboratory of Agent-based Highway Traffic Model


We describe our microscopic model of highway traffic and its implementation as digital laboratory. We discuss the range of experiments that can be conducted using this laboratory. Software implementation details are discussed together with the model because the implementation affects the model and delimits what can be modeled. This is seldom described in the literature, but lack of this knowledge often affects the ability of the reader to replicate the research. We model the expressway as a number of adjacent lanes, where each lane is divided into cells. Each cell is assumed to be 7.5 m. The most innovative aspect of our model is that we model multiple lanes as a single 1-D automaton. By extending the “Cellular Automata” (CA) paradigm to the “Global Cellular Automata” (GCA) paradigm we can represent the multilane highway with a single 1-D GCA, which can be implemented to execute faster than a traditional 2-D CA implementation and than a multi 1D CA implementation. We present selected simulation results and outline our plan for future work.


ver. 2024.02.28 • we use cookies and MathJax