Emergence, Locating and Measuring It - Systematic Design for Emergence in Cellular Nonlinear Networks - page 56

4.3 Semitotalistic Cells: A First Step in Narrowing
The Search Space

Let us consider a network of N interconnected cells. In a typical cellular architec-
ture the cells are locally connected within a Moore or Von Neumann neighbor-
hood. Let us denote k the number of links of a cell with other neighbors. Assuming
that each cell has only two states (Boolean cells), there are k

2 2 possible choices
for the cell (all Boolean functions with k inputs). This is a huge number even for
reasonably small values of k . On the other hand experiments and observations
prove that there is an ordering principle governing the real world, such that not
any randomly chosen Boolean cell will lead to an emergent behavior.
We are thus interested to narrow the huge gene search space (of all possible
Boolean functions) by revealing some structural constraints in relationship to the
assumed ordering principle. Are there any structural constrains in choosing k so
that emergence becomes likely? The answer is positive and it is motivated by sev-
eral independent results.

1. According to the theory of “small worlds” [1] the average degree of separa-
tion 2 “ d” in a large network of nodes is a small number. For instance, real
world webs were found to have from

d 3 (for networks of molecules in a

cell) to d (for the World Wide Web) [59,63]. This postulate proved true

for many natural systems indicating that in nature networks of interconnectivity
are organized such that they are neither sparse (i.e. cells connecting only with
one ore two other cells) nor dense (i.e. fully interconnected networks). For in-

19

stance, in a social network d | 6 [59] representing the average number of ac-
quaintances (shaking hands) that can be established between two arbitrary
persons in the world. Note than in a fully connected network d=1 (minimum)

because any node is connected to any other one. However, the network is not

economic at all, requiring a large number N 2 of links.

2. In a 1D cellular system with links only to the left, the value of d reaches its
maximum (i.e. d=N, where N is the total number of cells) corresponding to a
sparse connectivity. Here the number of links is O(N) but the average degree of
separation is too small to produce emergent phenomena (the only phenomena
possible then is a propagation one, with a speed limited at one cell/iteration).
Increasing the grid dimension of a cellular system (e.g. from two-dimensional
grids to two-dimensional grids) will decrease d while maintaining a reasonable
number of local links . For instance,

d | in the case of 2D topologies,
therefore if the number of cells is less than 400, a CA with 2D topology will fit
the natural models, characterized by values of d ranging from 3 to 19. It is thus
2 Average number of connections between two randomly selected nodes in the graph of the

N

network. This number is related to k (the degree of connectivity for each node) and the

interconnection topology.