Selected Abstracts
In this page we present some selected abstracts that
will be presented in the conference.
|
Structure and Evolution of the Indian Railway Network
|
|
Saptarshi Ghosh, Avishek Banerjee, Naveen Sharma,
Sanket Agarwal, Animesh Mukherjee, Niloy Ganguly
|
|
The structure and evolution of the transportation networks of a country are primary indicators of its
economic progress.
In this paper, we study the Indian Railway Network (IRN) as a weighted complex
network, with emphasis on its present structure and its evolution over the past two decades. Stations are
considered as the nodes in the network, while the weighted edges represent the number of trains linking
two stations. Apart from the small-world characteristics and exponential degree distribution of the IRN,
we explore the correlations of the amount of traffic with the topology of the network. With respect to the
evolution of the IRN, we observe that the IRN is becoming denser with time, following the densification
power law; further, the network is found to become more homogeneous with respect to node-degrees
over time, which indicates improved connectivity among stations.
|
|
InterCell: Large scale cellular and interactive computation
|
|
Hervé Frezza-Buet
|
|
In the field of neural computation, available parallel simulators are mainly dedicated to spiking
neurons (Brette et al., 2007), but very few attempts have been made to design simulators for
discrete dynamical systems like cellular automata and other models extended from them. The
InterCell project (Frezza-Buet, 2007) addresses this issue, providing a C++ API and related tools
to design such systems, hiding the parallelization to the designer.
|
|
Local and Regional Interactions for Programming Discrete Models of Complex Systems
|
|
Giandomenico Spezzano
|
|
This paper describes CARPET-R, a language for
cellular programming which extends the cellular
automata model through the concept of regions. Regions
are spatio-temporal objects that define zones of the
automaton (set of cells), containing interesting and
meaningful data patterns or trends that can be defined as
events. Each cell of the automaton can monitor regions
for a given period and observe their evolution by global
functions (max, min, sum etc.). Furthermore, each cell can
have an associated attribute called its perception rating,
that indicates how far that cell can ‘see’. On the basis of
this value and the cell’s position in the cellular space, we
can define the regions that are visible to the cell. Using
these constructs, a cell can define significant events to
extract data of interest in one or more regions and
perform actions when an event is detected. In the paper,
we show that regions simplify programming and allow the
building of more complex models. After describing the
main constructs of CARPET-R, the paper illustrates the
region-based programming model by describing the
design of a parallel model of animal migration.
Performance results of the model implemented on a
Cluster Computer are also given.
|
|
Critical mass effect in the contact process of decision making
|
|
M. Rybak and K. Kułakowski
|
|
Collective actions need often a chain reaction of approving decisions, made by individuals. According
to the Granovetter’s theory, such a decision is triggered by some threshold number of agents who
joined the action. The effect has been investigated within the so-called critical mass theory. We
are going to investigate this effect in social networks in terms of the theory of contact processes.
The model parameter is the threshold number of neighbors k* who adopted the collective strategy; a
contact with k* individuals is the necessary and sufficient condition for making the approving
decision. The process depends of the clustering coefficient C. In trees, where C=0, the process does
not spread at all for k*>1. In two-dimensional spatial networks, where C=0.46, the critical
connectivity K for k*=2 is about 7.8. Near the critical point, the inverse time of getting the system
boundaries varies with the mean degree <k> as (<k>-K)a, with a close to 0.6. Numerical calculations
are in progress.
|
|
Virtual Stability: A General Principle of Complex Adaptive Systems?
|
|
Burton Voorhees
|
|
The concept of virtual stability is defined as a state in which a system employs
self-monitoring and adaptive control to maintain itself in a configuration that would
otherwise be unstable.
The extra energy expended in doing this is compensated by the advantage gained in
increased behavioral flexibility in the face of random environmental perturbations.
A population model is developed as a proof of concept.
In the model, transition probabilities between three population types are used to
emulate stability: stable types have low probabilities of making transitions to other
types, unstable types have high transition probabilities.
The model itself consists of two stable types and one unstable type and conditions
are explored that lead to dominance by the unstable type.
Under certain conditions the unstable type can defeat a stable type, even in an
environment that always favors the stable type.
Presentation of the model is followed by discussion of the importance for managed
stability for complex systems, and the evolutionary advantage the capacity to
maintain virtually stable states provides.
This leads to the suggestion that such advantage gives an argument both for the
directionality of evolution and for the emergence of self-consciousness.
|
|
Simulating cancer growth with cellular automata: can it help?
|
|
Andreas Deutsch
|
|
Deciphering the principles of cancer growth is crucial for the
development of new therapy concepts. Besides increasingly complex
molecular investigations, mathematical modelling and computer simulation
of selected aspects of cancer growth have become popular within the last
few years. Here, we focus on the analysis of cancer invasion.
Lattice-gas cellular automaton (LGCA) models allow for an adequate
description of individual invasive cancer cell behaviour (microscopic
level). We will show how approximations of the LGCA models allow for
prediction of emerging macroscopic properties (in particular of the
invasion speed). Furthermore, we will use our models to derive and test
a new cancer invasion hypothesis on the basis of experimental data from
in vitro glioma cell invasion assays.
|
|
Sparseness in model gene regulatory networks
|
|
Marcin Zagórski
|
|
Gene regulatory networks typically have low in-degrees, whereby any given gene is
regulated by few of the genes in the network. They also tend to have broad distributions
for the out-degree. What mechanisms might be responsible for these degree
distributions? Starting with an accepted framework of the binding of transcription factors
to DNA, we consider a simple model of gene regulatory dynamics. There, we show that
selection for a target expression pattern leads to the emergence of minimum
connectivities compatible with the selective constraint. As a consequence, these gene
networks have low in-degree, and "functionality" is parsimonious, i.e. is concentrated on
a sparse number of interactions as measured for instance by their essentiality.
Furthermore, we find that mutations of the transcription factors drive the networks to
have broad out-degrees. Finally, these classes of models are evolvable, i.e. significantly
different genotypes can emerge gradually under mutation-selection balance.
|
|
Counting Fixed Point Configurations of Cellular Automata with Simple Threshold Update Rules
|
|
Predrag T. Tošić
|
We study classical cellular automata with linear threshold functions as the node update rules. We restrict
those linear threshold functions to the ones that are also symmetric, and hence can capture the mean
field effects studied in statistical physics and other models of very large-scale systems; we call such
symmetric linear threshold functions simple. The most prominent representatives of simple threshold
functions on the Boolean domain are the AND, OR and Majority update rules.
We completely characterize the configuration spaces of simple threshold CA, with a focus on the Majority
update rule that results in the most interesting dynamics among the CA in this very restricted class. In
particular, we show the combinatorics behind determining the total number of fixed point configurations
for simple threshold CA. Even when the combinatorics is non-trivial, such as in the case of Majority
update rule, the counting problems of interest (such as determining the exact number of fixed points) are
all computationally tractable. This is in stark contrast to our intractability of counting results demonstrated
for the related classes of Boolean network or graph automata with similarly restricted node update rules,
that are characterized by (seemingly) only slightly more complex structures when it comes to (i) the
underlying interconnection topologies (or cellular spaces) and (ii) diversity of the node update rules, i.e.,
whether all the nodes use the same update rule (as in the classical CA), or two different rules from the
given class are allowed. The conclusion is that even most modest generalizations of the classical CA with
simple threshold update rules lead to a phase transition from the dynamics that is "easy in principle" to
predict and fully characterize, to provably very complex and intractable dynamics.
|
|
Modeling Large-Scale Multi-Agent Systems with Sequential and Genuinely Asynchronous Cellular Automata
|
|
Predrag T. Tošić
|
|
We study certain types of cellular automata (CA) viewed as an abstraction of the large-scale multi-agent systems
(MAS). The classical CA model needs to be modified in several important respects, in order to become a relevant and
sufficiently general model for the large-scale MAS, and so that thus generalized model can capture many important
MAS properties at the level of agent ensembles and their long-term behavior patterns.
In this paper, we focus on the issue of inter-agent communication in CA, and propose the sequential cellular
automata (SCA) as the first step, and the genuinely asynchronous cellular automata (ACA) as the ultimate
deterministic CA-based abstract model for large-scale MAS made of simple reactive agents. We first formulate
deterministic and nondeterministic versions of sequential CA, and then we address certain configuration space
properties (i.e., possible dynamic behaviors) of a class of sequential threshold CA. In particular, we compare and
contrast those properties with the corresponding properties in the classical, parallel (that is, perfectly synchronous)
threshold CA. Finally, we outline what would be an appropriate CA-like abstraction for the large-scale distributed
computing insofar as the inter-agent communication model is concerned, and in that context we propose genuinely
asynchronous CA.
|
|
GCA-w Algorithms for Traffic Simulation
|
|
Rolf Hoffmann
|
|
The GCA-w model (Global Cellular Automata with write access) is
an extension of the GCA (Global Cellular Automata) model, which is based on
the cellular automata (CA) model. Whereas the CA model uses static links to
local neighbors, the GCA model uses dynamic links to potentially global
neighbors. The GCA-w model is a further extension that allows modifying the
neighbors’ states. Thereby neighbors can dynamically be activated or
deactivated. Modeling traffic flow is a good example showing the usefulness of
the GCA-w model. The Nagel-Schreckenberg algorithm for traffic simulation is
first described as CA and GCA, and then transformed into the GCA-w model.
Furthermore, this algorithm is extended, allowing to deactivate and to activate
cars stuck in a traffic jam in order to save computation time and energy
|
|
FLAME: A Platform for High Performance Computing of Complex Systems
|
|
Mesude Bicak
|
This paper presents FLAME Flexible Large-scale Agent-based Modelling Environment
for modelling various real complex systems from biological, economic and sociological
systems. FLAME allows models to be automatically parallelised on high performance
computing grids enabling large number of agents to be simulated in less time than other
comparable simulation frameworks. The framework handles this parallelism itself
allowing realistic models to be simulated. Researchers are hindered by complexities of
porting models on parallel platforms and time taken to run large simulations on a single
machine which FLAME overcomes.
Communication between agents is achieved through the use of messages using MPI to
port messages across different machines and platforms. The communication is handled
using an intelligent message board library, Libmboard, which allows filtering of
messages reducing the work for the agents improving simulation performances. Using a
distributed memory model, single program multiple data (SPMD), the framework is able
to handle deadlocks through synchronisation points which ensure all data is coordinated
among agents. Performance results of simulating 106 agents implemented on a computing
grid are also presented.
|
|
Study heart rate variability with tools from complex networks
|
|
Danuta Makowiec, Joanna Wdowczyk-Szulc, Marta Żarczyńska-Buchowiecka,
Rafał Gałaska, Marcin Gruchała, Andrzej Rynkiewicz
|
|
Heart rate, measured as beat-to-beat intervals, is not constant but
varies in time. It is believed that time intervals between subsequent
normal heart contractions carry information about the regulatory system
of the heart. How to quantify such signals is not clear and because of
that heart rate variability is still apart from the clinic routine. In
the following we consider transfering of a heart rate signal into a
directed network and then study the signal properties by complex network
tools. The signals to study were collected from patients recovering
after the heart transplantation. The basic aim is to classify the
progress of adapting of the new heart --- graft. Our investigations are
preliminary --- any criticisms and advices how to deal with such
networks are welcome.
|
|
Emergent network structure, epigenetic organization and evolvable robustness in an artificial genome model
|
|
Thimo Rohlf
|
An important contribution to the processing of genetic information comes from transcription factors (TFs) binding to
specific DNA sequences, and thereby activating or inhibiting transcription of genes (typically) downstream. Many
models of gene regulatory networks (GRNs), however, neglect both the sequence-based nature of TF-gene interactions
and the spatial extension of the genome. Here, we study a simple artificial genome model that allows to include these
additional levels of information into Boolean GRN models.
We analyze statistical properties of randomly generated genomes both on the sequence- and network level, and show
that this model correctly predicts the frequency of genes in genomes as found in experimental data. Distributions of the
lengths of non-coding regions, and asymmetries in GRN in- and outdegree distributions, as found in biological data,
follow from geometric properties of genomes and constraints on TF sequences.
Using an evolutionary algorithm based on stabilizing selection for a phenotype, we show that dynamical robustness
against single base mutations, as well as against random changes in initial states of regulatory dynamics that mimic
stochastic fluctuations in environmental conditions, can emerge in parallel. Point mutations at the sequence level have
strongly non-linear effects on network wiring, including as well structurally neutral mutations and simultaneous
rewiring of multiple connections, which occasionally lead to strong reorganization of the attractor landscape and
metastability of evolutionary dynamics.
|
|
Embedding Kadanoff’s Scaling Picture into the Triangular Lattice
|
|
Dominique Désérable
|
|
A topological aspect of the renormalization procedures is tackled from
the Kadanoff’s scaling picture which splits the “chessboard” into nested
blocks and sub-blocks and we study how to embed a similar scheme onto
the triangular lattice. Although this nested scheme is straightforward
in the chessboard, it is far from being the case in the “honeycomb”. A
background is first proposed to highlight the multiple ways of tiling the
plane with prototiles, in the square tessellation as well as in the hexagonal
tessellation, and to show how the symmetries of the regular tiling may or
may not be stabilized by the prototile. It is shown that there exists a
prototile that preserves symmetries in the hexagonal case. In the (dual)
triangular lattice, this construction generates an “arrowhead” torus which
belongs to the family of hierarchical Cayley graphs.
|
|
Highway Traffic Modeling & Simulation by Means of Agents on GCA-w
|
|
Bruno N. Di Stefano and Anna T. Lawniczak
|
A highway traffic model of the Nagel-Schreckenberg type can be seen as made
up of a CA (Cellular Automaton) acting as a database where all information about
the current state of the model is recorded and a number of vehicles implemented
as agents able to interpret all information about all possible situations and able
to decide what to do next.
The number of actions that a vehicle can take at every time step and their complexity
are much higher than what is possible in the traditional Nagel-Schreckenberg model.
We describe two implementation improvements over the Nagel-Schreckenberg model:
The replacement of the traditional CA with the “Global Cellular Automata” (GCA) and the “Global Cellular Automata with Write access” (GCA-w) developed by Rolf Hoffmann and his collaborators. This allows for faster execution and for the elimination of some potential conflicts during execution.
- The possible replacement of reflexive agents with cognitive agents
We have implemented the first improvement and we will present implementation details.
We are currently working at the second improvement and we will describe our work in
progress about cognitive agents.
|
|
AI Planning and fixed points in asynchronous CA
|
|
Joerg Hoffmann and Nazim Fatés
|
|
AI Planning is concerned with the selection of actions
towards achieving a goal. Research on cellular automata (CA) is concerned
with the question how global behaviours arise from local up dating rules
relating a cell to its direct neighbours. While these two
areas are disparate at first glance, we herein identify a problem that is
interesting to both: How to reach a fixed point in an asynchronous CA
where cells are updated one-by-one? Considering a particular local
updating rule, we encode this problem into PDDL and show that the
resulting benchmark is an interesting challenge for AI Planning. For
example, our experiments determine that, very atypically, an optimal
SAT-based planner outperforms state-of-the-art satisficing heuristic
search planners. This points to a severe weakness of current
heuristics because, as we prove herein, plans for this problem can always
be constructed in time linear in the size of the automaton. Our proof
of this starts from a high-level argument and then relies on using a
planner for flexible case enumeration within localised parts of the argument.
Besides the formal result itself, this establishes a new proof
technique for CAs and thus demonstrates that the potential benefit of
research crossing the two fields is mutual.
|
|
Dynamics of Number of Packet in Transit in Free Flow State of Data Network
|
|
Anna T. Lawniczak
|
|
We study how the dynamics of number of packets in transit (NPT) is affected by the
coupling of a routing type with a volume of incoming packet traffic in a data network model.
The NPT is a network performance indicator of an aggregate type that measures in “real time”
how many packets are in the network on their routes to their destinations. We conduct our
investigation using a time-discrete simulation model that is an abstraction of the Network Layer
of the ISO OSI Seven Layer Reference Model. This model focuses on packets and their routing.
We consider a static routing and two different types of dynamic routings coupled with different
volumes of incoming packet traffic in the network free flow state. Our study shows that the
order of the values of the NPT mean value functions depends on the coupling of a routing type
with a volume of incoming packet traffic and changes when the volume of incoming packet
traffic increases and is closed to the critical source load values, i.e. when it is closed to the
phase transition point from the network free flow state to its congested state. This research is
joint work with Shengkun Xie and other members of A.T. Lawniczak’s research team.
|
|
From Computational Neurosience to Cellular Automata
|
|
Nicolas Rougier
|
|
I will present some works related to computational neuroscience where we
defined the notion of asynchronous evaluation in the context of visual
attention modeling. By considering those models as being a
generalization of cellular automata, we’ll investigate to what extent
this notion of asynchronicity can be translated into the cellular
automata theory.
|
|
