{'fraction_non_alphanumeric': 0.026822157434402333, 'fraction_numerical': 0.005164514785506039, 'mean_word_length': 4.780452575830525, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Similar impact of topological and dynamic noise on complex patterns

Shortcuts in a regular architecture affect the information transport through the system due to the severe decrease in average path length. A fundamental new perspective in terms of pattern formation is the destabilizing effect of topological perturbations by processing distant uncorrelated information, similarly to stochastic noise. We study the functional coincidence of rewiring and noisy communication on patterns of binary cellular automata.

Within the last two years cellular automata (CA) have re-emerged in the focus of scientific attention, both with respect to fundamental work [1,2] and with respect to applications, e.g., to biology [3,4,5]. Such CA play an important role as minimal models of complex pattern formation. Pattern complexity is usually discussed in terms of the four Wolfram classes [6] distinguishing fixed points, periodic, chaotic and long-range complex behavior, respectively. Recently this approach to pattern formation has been linked with concepts from graph theory by studying the behavior of CA under variation of the underlying topology [7,8]. Investigations elucidating the link between dynamics and topology in complex networks are needed to ultimately understand the evolutionary building principles of biological networks. The incorporation of noise or disorder in such systems is a natural step towards realistic models [8,9]. Qualitatively speaking, there are two possible ways of introducing disorder: On the level of signals and on the level of architecture. The function of shortcuts in regular graphs with local clustering, as first proposed in [10], has mostly been attributed to the dramatic decrease of path lengths in these small-world networks. In addition, however, topological perturbations can distribute global information among the local neighborhoods. Recently, simple binary dynamics in a noisy environment proved to be an excellent example for efficient information processing in decentralized systems [8].
In this paper, we compare the two types of disorder in a model system of complex pattern formation, namely a totalistic CA generalized to arbitrary system topologies. We show that topological disorder, while retaining determinism of the time development, produces qualitatively the same effect on complex patterns as stochastic (external) noise by inserting uncorrelated information into neighborhood-based local patterns. We argue that this mechanism is responsible for the possibility to pass from one Wolfram class to another purely by topological modifications of the underlying graph that has been recently observed in [7]. We show that this relation between topological and dynamic noise remains, even when one skips to a Monte Carlo update scheme.
We consider a simple binary dynamic Ω(κ) presented in [7] which is capable of generating complex behavior on a standard CA topology, i.e. a regular one-dimensional graph with periodic boundary conditions and N nodes, where every node is connected to its d nearest neighbors. The state x i ∈ {0, 1} of a node i is flipped or retained during the update process according to the parameter κ and the density ρ i of 1's in the node's neighborhood, where d i is the degree of node i and A ij is the adjacency matrix of the underlying graph: The dynamic regimes for random initial conditions are intuitive: Small κ favor changing nodes while large κ lead to stationary behavior. In between these limiting regions, space time patterns with both oscillatory and stationary elements occur and complex dynamics can emerge. Fig. 1 shows the κ dependent domains for a synchronous and a Monte Carlo update scheme on a regular graph. In the first case, the simultaneous application of Ω(κ) to all N nodes in one time step leads to strictly oscillatory behavior around small κ and a narrow regime of complex patterns for κ ≈ 0.35. The Monte Carlo update of Ω(κ), where in one time step N randomly selected nodes are updated in random order, leads to chaotic patterns for small κ and a larger complex region. In both cases, the variation of κ results in a gradual change of the dynamic complexity. We systematically studied the effect of noise on the pattern formation capacity of a synchronously updated network according to the rules Ω(κ). In the noiseless case each Ω(κ) then corresponds to a specific deterministic CA rule number. For disordered graphs, we exploit the portability of Ω to arbitrary architectures. In the following we choose a value of κ giving complex (Wolfram Class IV) patterns for the topologically and dynamically unperturbed system. In Fig. 2 two sets of spatiotemporal patterns are shown as typical examples for the impact of noise on such CA dynamics. In the first case, the regular graph topology is altered by rewiring the endpoints of randomly selected links. This procedure is similar to the one described in [10]. Here, however, it is applied to directed graphs. In this context, the noise intensity η specifies the fraction of rewired connections. In the second case we surmise that the communication between the elements is corrupted by noise: The state x j of a linked element j is substituted randomly with a random binary number with probability η during the update of element i. We call this perturbation input noise throughout this paper, since it affects only the perception of the neighboring state x j as seen by i in Eq. (1) and does not change the state of j itself. The visual impression of Fig. 2 suggests that input noise on the one hand and rewiring the regular graph architecture on the other affects the complexity of the system dynamics in a similar way. We apply the word entropy W , introduced in [7] and tailored to the classification of CA into Wolfram classes, to quantify the pattern formation capacity of the noisy network dynamics. The word entropy W i relies on the relative number of words, i.e. blocks of constant cell states, of different length in the time series {x i } of a node i. The overall word entropy W is the average over all N nodes of the graph, where p i (l) is the probability for the occurrence of a word of length l in the time series of node i. For the κ-dependence of W , see [7]. In Fig. 3, we show the word entropy W for systems perturbed by rewiring and input noise, respectively. The pattern complexity decreases in both cases similarly with the noise intensity η. Note that in both cases the numerical value of the noise intensity gives the average number of perturbations per link and time step. In a second investigation we studied the same phenomenon under a Monte Carlo update scheme. This random time evolution is argued to be more realistic in terms of information processing in natural systems, as a simultaneous update may induce stable patterns as artifacts. As η is increased, coherent regions in the patterns disappear and chaotic behavior prevails (Fig. 4). Due to the change in the update scheme, a proper separation of the dynamic regimes with the word entropy fails: Short l-words of different lengths in the chaotic patterns result in similarly high W values as in the complex case with long-range correlations. In order to definitely classify the pattern evolution with a single observable one could use the entropy measure proposed by Wolfram in [6], where all possible words, including non-constant l-words, are accounted for. Instead, we will apply the (statistically less demanding) detrended fluctuation analysis (DFA) to reveal the complexity of the binary network dynamics, as applied in [9].
The DFA characterizes the time correlations of a signal with a single value, the scaling exponent α. A random signal with no long-range time correlations leads to α = 0.5, while Brownian noise exhibits an exponent of 1.5. Many physiologic systems have been shown to generate signals with long-range time correlations [11] resulting in an intermediate scaling exponent of α ≈ 1.  The known relationship to the scaling exponent α ps of the power spectrum of fluctuations, α ps = 2α − 1, allows a comprehensive discussion of parallels between complex dynamics with α = 1 and natural phenomena with 1/f fluctuations [12]. Detailed descriptions of the DFA algorithm can be found in [13]. We use the DFA to measure time correlations in the overall density of a system ρ(t) = 1 N N i=1 x i (t) and thereby quantify the complexity of the system's dynamics. Again we find that both, perturbations of the regular topology and dynamic noise affect the system in a intriguingly similar manner (Fig. 6). In the extremal case of η = 1 (which corresponds to completely disintegrated neighborhoods and the permanent substitution of neighboring states with random binary numbers respectively) both systems exhibit a completely random, white noise signal, characterized by an exponent α ≈ 0.5.
How can the similarity of two such different noise mechanisms be understood? Complex dynamics given, shortcuts insert information from distant regions of the network into local neighborhoods, which is-due to its lack of correlation to the neighborhood at hand and the overall dynamics of the network's elements-similar to random dynamic perturbations. Fig. 7 depicts the two discussed noise mechanisms schematically. One prerequisite for the similar impact of both noise mechanisms is therefore clearly a globally running complex or chaotic dynamics, which ensures an adequately random and uncorrelated signal from the linked distant node. Apparently deviations in the space and time correlations of the noise events are leveled by the internal signal processing of the network. Finally, we want to note that other kinds of dynamical noise (like white noise affecting directly the state x i of the system) and other forms of topological noise (e.g. the addition of links into the architecture) lead to similar results as the mechanisms discussed above.
The effect described in this paper may apply to a large class of network dynamics phenomena. The results in [14] for example, where the forest-fire-model is discussed on a small-world topology can be interpreted in this way. There, a self-organized critical state of the system is achieved without the introduction of dynamic noise (namely the occurrence of lightning strikes) by rewiring a small fraction of links. On the other hand, topological and dynamic noise can also play different functional roles in network dynamics, as reported in [8] for the case of a simple density classi- In the upper picture, a simple directed link has been rewired and accordingly, the states of a distant node j affect the update of node i through this shortcut in every time step t, t + 1, t + 2, . . . . The perturbing binary elements can be lined up as a noise vector, consisting of the time series of element j. In contrast, for dynamic perturbations this noise vector is made up of random binary numbers. These affect the update process of randomly chosen states at random times t ′ , t ′′ , t ′′′ , . . . , substituting the state of a neighboring node with probability eta. fier task. Indeed, the globalizing effect of shortcuts and the random perturbations of input noise provide two very different resources for an effective processing of the majority rule. However, complex dynamics can be regarded as a functional state of a complex network itself, as discussed recently in [15]. As we have shown, the systematic modification of such dynamics can be equally achieved by dynamic noise and topological disorder. We expect that this functional alternative in regulating dynamic features can be found to be exploited in natural systems, as soon as one looks at phenomena from the perspective lined out here.
Summarizing, we find that in graphs with clustered neighborhood structures, links between distant regions of the network can have the same effect as stochastic perturbations of the dynamic signals themselves, if the signal conferred by these shortcuts displays an appropriate degree of chaoticity.