{'fraction_non_alphanumeric': 0.028819613573632084, 'fraction_numerical': 0.008808248092222764, 'mean_word_length': 5.2011074754593505, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Regularizing Capacity of Metabolic Networks

Despite their topological complexity almost all functional properties of metabolic networks can be derived from steady-state dynamics. Indeed, many theoretical investigations (like flux-balance analysis) rely on extracting function from steady states. This leads to the interesting question, how metabolic networks avoid complex dynamics and maintain a steady-state behavior. Here, we expose metabolic network topologies to binary dynamics generated by simple local rules. We find that the networks' response is highly specific: Complex dynamics are systematically reduced on metabolic networks compared to randomized networks with identical degree sequences. Already small topological modifications substantially enhance the capacity of a network to host complex dynamic behavior and thus reduce its regularizing potential. This exceptionally pronounced regularization of dynamics encoded in the topology may explain, why steady-state behavior is ubiquitous in metabolism.


I. INTRODUCTION
The general notion of network biology [1] proposes an abstract view on biological systems: The components' complex interaction pattern is represented by a mathematical graph consisting of nodes and links. The aim is to understand universal features and design principles of complex biological networks at a system-wide level [1,2,3]. Recent findings include the ubiquity of heavytail degree distributions [1], a 'bow-tie' structure of certain network types [4,5], the presence of modules [6,7,8] and a similarity in motif content of functionally related networks [9]. An important focus of research is to develop models of graph construction, which yield similar statistical properties as the real graphs [7,10,11,12]. This modeling task is complicated by the fact that dynamic performance is a criterion in the evolutionary shaping of some types of biological networks [13,14]. Consequently, a current challenge is to incorporate dynamics into this general framework, i.e. to link topology and dynamic function. For gene regulatory networks huge progress has been made in the last few years in that regard: The motif content of eukaryotic genetic networks [9] has been shown [13] to correlate with the dynamic robustness profile of these motifs; the dominant branch of the largest attractor of a reduced yeast cell cycle network under the framework of Boolean dynamics coincides with the experimentally observed sequence of cell states [15]. In the case of metabolic networks the situation is far more involved. Since the dynamics of the metabolic concentrations lack an approximately binary behavior, refined kinetic models have been developed [see, e.g., 16,17]. † Jacobs University Bremen as of spring 2007 * Electronic address: marr@bio.tu-darmstadt.de Due to the limited knowledge of kinetic parameters, such models are often restricted to sub-networks, lacking the large-scale perspective, unless strong simplifications and abstractions are introduced in the dynamics. Many approaches exploit an intriguing feature of metabolic network dynamics: the convergence to a steady state. Flux balance analysis (FBA) [18,19], for instance, retains the stoichiometric matrix (and, therefore, the interaction pattern of the network) to formulate hypotheses on the overall performance of the system, together with an objective function incorporating constraints on the metabolic dynamics. This method and related steadystate approaches have been successfully applied to the phenotypic prediction of various wild-type species and mutants under different environmental conditions [see, e.g., 20,21,22]. Here, we address a fundamental topological question: How well is a particular network designed to suppress complex dynamics? We select rules, which lead to transient (i.e., non steady-state) binary dynamics on metabolic networks and compare the pattern complexity for the real and modified topologies. Note that obviously, our dynamics has no immediate connection to real metabolic dynamics, it rather serves as a dynamic probe on complex networks. We find that -in spite of the structural and dynamical abstractions -real metabolic network topologies exhibit the capacity to maximally regularize an imposed complex dynamics compared randomized topologies with identical degree sequences.

II. MATERIALS AND METHODS
We use the metabolic networks compiled by Ma and Zeng (MZ) [24]. Their data rely on the KEGG database [25] and incorporate enzyme-catalyzed reactions based on genomic analyses and biochemical literature. In this Entropy signature of the yeast metabolic network (black) and randomized (red), hierarchized (orange) and anti-hierarchized (blue) counterparts [see 23, for details on these randomization procedures] with degree correlations of 0.05, 0, +0.3, and −0.3, respectively. Each point represents the entropy signature of the respective network for a randomly selected initial condition.
unipartite, substrate-centric representation, metabolites (nodes) are connected by biochemical reactions (links) whenever the catalyzing enzyme is encoded in the respective genome. Compared to other metabolic network representations the MZ networks are relatively sparse. This is due to the exclusion of frequently occuring metabolites like ATP or NADH from those reactions, where they act as current metabolites (or carrier metabolites; cf. [7]) only [see 24, for a detailed discussion of current metabolites in metabolic networks]. As noted in [24], the exclusion of current metabolites is reasonable in terms of metabolic pathways -otherwise, for example, the path length (number of reaction steps) from glucose to pyruvate in the glycolysis pathway would reduce from nine to two [24]. Since we are less interested in mass flow and catalytic regulation, and more interested in the information processing capabilities of such pathways, the substrate-centric representation of biochemically meaningful pathways of the MZ networks is an appropriate choice. However, we performed parts of our analysis on other network representations (see Results) with similar findings. From the available data we only use the largest connected component of the networks similarly to previous studies [4,8,26]. Hence, we limit our attention to the most prominent part of the metabolic networks (on average, the largest connected component comprises 54% of the nodes and 66% of the links of the complete network for the 107 species in the MZ database) and avoid dynamical artifacts due to isolated residual subgraphs of different size.
Cellular automata (CA) are a well-known tool from complexity theory. Under rather general assumptions symmetry arguments reduce the rule space for binary cellular automata on graphs to a set of few outer-totalistic [27] automata. The effect of these assumptions (like isotropy, locality and linearity) on the range of possible CA rules will be discussed elsewhere [28]). Most of the rules lead to trivial spatio-temporal patterns, e.g. oscillations or a steady state like the frequently used majority rule [29,30]. Here, we choose one of those rules, which leads to non steady-state behavior on metabolic network topologies. Each node acts as a threshold device: the state x i of node i changes from 0 to 1 and vice versa, as soon as the density of 1's in its neighborhood exceeds κ. Ω can be formalized to The local density ρ i can be expressed by where d i is the number of neighbors (the degree) of node i and A denotes the adjacency matrix of the graph. The rule Ω has been used previously to assess information processing capacities of synthetic graphs [31]. Complex dynamics on MZ networks are achieved for a κ 0 around 0.3. The exact size of the feasible interval depends on the maximal degree in the network d max , via 1/d max . Our implemented complex dynamics can be considered as the continuous processing of perturbations by the network. Following the argument of [32] that perturbations can travel in both directions of an irreversible reaction, we use undirected graphs as metabolic network representations.
Information theory provides tools to analyze spatiotemporal patterns, e.g., the Hamming distance, the mutual information or the Rényi entropy [33]. Here we apply the Shannon entropy [34] and the word entropy [31], since their combination was found to perform well in separating different dynamic regimes [31]. We thus characterize a graph's capacity to process binary information with the entropy signature (S,W ) on the basis of the specific update scheme Ω. Entropy values are calculated by analyzing N time-steps for each of the N nodes after a transient time of 9N time-steps. In our analysis, we take the mean Shannon entropy S of the N individual entropies S i , calculated for each node's time series separately, as a measure for the structure of the overall pattern, The probabilities p 0 i and p 1 i denote the ratios of 0's and 1's in the time series of node i. Constant nodes yield S i = 0, while nodes with a homogeneous distribution of 0's and 1's, that is ever flipping and irregular nodes, contribute maximally to S with S i ≈ 1. In the dynamical regimes regarded in this study, the value of S is a measure for the homogeneity of dynamical behaviors on the level of single states: Large values of S emerge for an overall oscillatory or complex dynamics, while smaller values of S indicate the existence of constant time series within the patterns. The word entropy W serves as a simple and easily applicable complexity measure of the emerging patterns beyond single time steps. To quantify the irregularity of the time series of a single node, we count the number of constant words, i.e. time blocks of constant cell states, of length l. The probability p l i is the number of words of length l divided by the number of all constant blocks in the time series of node i. The maximal possible word length is simply the length t of the time series analyzed. The word entropy W of a pattern is the average over the individual time series' entropies W i and is defined as Patterns with solely oscillatory or stationary behaviors result in W =0 while an overall irregular or complex behavior results in high W . We use the term entropy for our observables due to their formal definition and due to the application of similar concepts in information theory [34] and the theory of cellular automata (the word entropy serves as a feasible simplification of the 'block entropy', introduced in [35]). Note, however, that the two entropy measures defined in eqs. (2) and (3) may not be interpreted in the standard thermodynamical way, since we average over the individual entropies of an ensemble of coupled dynamical entities. Note also, that the W i are not bound to the interval [0, 1].

III. RESULTS
The metabolic network of the yeast, S. cerevisiae, in the MZ database comprises N =752 nodes and L=777 links. N =448 nodes and L=564 links remain in the largest connected component of this network. It is characterized by a diverse mixture of linear chains of nodes and hubs connecting chains and single elements (see Fig. 1a). This topological diversity is reproduced in the patterns which emerge from running Ω(κ 0 ) on the network (see Fig. 1b): Constant and oscillatory time series coexist with irregular time series, where nodes switch between alternating and constant behavior in an unpredictable manner. A randomized network, where the topology is changed but the degree sequence of the graph is preserved by always switching the links of two pairs of nodes as proposed in [36], shows patterns which are dominated by irregularities. These differences in the dynamic response manifest themselves in different entropy signatures of the yeast network and randomized counterparts (see Fig. 1c). The mean entropy differences for Ω are: ∆S = S rand − S yeast = 0.089, ∆W = W rand − W yeast = 0.50. Apparently, the yeast topology is capable of reducing the resulting entropies, that is, of regularizing the dynamics imposed on it. We checked that any rule among the cellular automata on graphs set of rules [28] leading to complex patterns on the yeast topology confirms the enhanced regularizing capacity of the real metabolic network. Note that here and in the following all graph modifications do not only conserve the overall degree distribution but also the degree sequence, that is, the individual degrees of all nodes. Moreover, we ensure that the randomized graph is connected after every randomization step.
We probe the networks of all species in the MZ database and randomized counterparts with the Ω(κ 0 ) dynamics. We find reduced entropy signatures for the real topologies for 99 of the 107 species. The networks of the remaining 8 species are extremely sparse Method: (a) For different random initial conditions, we yield entropy signatures for the original unperturbed network (black diamonds) and a minimally modified topology (gray dots); (b) The shifts for each initial condition (gray arrows) are averaged (black arrow); (c) Averaging over the ensemble of similarly modified topologies leads to the average entropy shift for this type of topological perturbation (red arrow). Result: (d) Systematic increase of the entropy shift with a single randomization step. Different protocols are performed, namely arbitrary randomization, randomization under conservation of clustering Coefficient and average path length respectively, hierarchization and anti-hierarchization, intermodular and intra-modular randomization. and therefore difficult to properly randomize. A reduced (S, W ) is still observed, if we exclude constant or trivially oscillating nodes from the analysis. Not too sparse metabolic networks (we choose here a link to node ratio L/N ≥ 1.22) can be treated in a statistically robust manner and cluster in the entropy plane at distinctly smaller values than their randomized counterparts. The modification of a network in single randomization steps but at fixed initial conditions leads to a path within the entropy plane. Consequently, this assessment of dynamic performance is highly systematic: Small changes in graph topology lead to small changes in the entropy signature. In Fig. 2, such a randomization procedure connects the metabolic network of the yeast and its randomized counterpart. The opposite direction, from the randomized counterpart towards the region of minimal entropies can in principle be followed by an appropriate randomization process. In this sense, the (S,W ) entropy plane -or an adequate set of other dynamic observables -may provide an orientation for simulated evolution or purposive topological design.
The randomization process alters a number of promi-nent topological properties: The average path length and the clustering coefficient [37] are reduced, degree correlations [23] are diminished and modular substructures [6,8] are disintegrated. In order to investigate whether the optimization of the metabolic networks goes beyond this set of topological observables, we perform different minimal topological perturbations and assess the corresponding entropy shift. We determine the entropy signatures of the yeast network and a modified graph, where only a single modification step has been performed, for different random initial conditions (Fig. 3a). Averaging over the initial conditions yields the average entropy shift for one specific topological perturbation (Fig. 3b). Averaging over many topological perturbations results in a vector which indicates the mean shift in the entropy plane due to a specific modification protocol (Fig. 3c). We observe an average entropy increase for a single randomization, hierarchization and anti-hierarchization step (Fig. 3d), where the latter two modifications, when iterated, lead to positive and negative degree correlations, respectively [see 23, for an explanation of the corresponding algorithms]. In order to retain the modular structure of the network we identify modules with a path length algorithm similar to the one described in [38] and randomize solely links within or between single modules. Both modifications reveal an average entropy increase compared to the original metabolic networks (Fig. 3d). In the case of intra-modular randomization, the similarity to a random flip suggests a topological optimization within the modules. The small shift due to inter-modular randomization indicates an optimized structure on the highest modular scale. We confirmed this result for another module identification algorithm based on the topological overlap of nodes [6]. Moreover, we confirmed an average entropy increase for protocols where a link flip is only allowed if the average clustering coefficient is conserved or increased due to a single randomization step (Fig. 3d). The same is true for a randomization protocol which conserves the average path length (Fig. 3d). Again, we ensured that the randomized networks remain connected through the application of the various randomization protocols. For all conditional randomization protocols, a average entropy increase can result from a limited number of sampled topologies. We checked, that this is not the case. Furthermore, the entropy shift increases with the number of randomization steps, i.e. the modification depth, performed on the topology (data not shown). Strongly hierarchized and anti-hierarchized networks (with considerably positive and negative degree correlations of +0.3 and −0.3 respectively), cluster in the entropy plane far apart from the original networks and slightly below and above randomized networks (see Fig. 1c).
Summarizing, the different topological perturbations clearly show that the pronounced regularizing capacity of  Fig. 2 together with synthetic architectures with the identical size and connectivity, respectively. We display data for the original metabolic networks (black), scale-free graphs (pink), randomized scale-free graphs (blue), small-world graphs (green) and randomized small-world graphs (yellow). The smallworld graphs were generated by rewiring 5% of the links of a regular chain. The randomized synthetic networks where obtained by flipping L pairs of links. Notwithstanding the different network sizes and connectivities, the topological variants cluster in highly specific regions in the entropy plane. We averaged over 100 initial conditions for 100 different synthetic network realizations each. real metabolic networks is not trivially associated with a single topological property within the set of graphs with a given degree distribution. Moreover, this property goes beyond simple degree correlations and modularity and are furthermore persistent on the level of individual modules. One can ask if the reduced entropy signature of real metabolic networks compared to randomized counterparts is an artifact of the specific network representation we discuss throughout this article. However, we verified the regularizing capacity of metabolic network topologies for another uni-partite substrate-centric representation, where current metabolites have not been removed from the system. Due to the existence of these highly connected hubs, the 43 networks discussed in [26] are highly connected and show extremely short average path lengths. All systems with sufficient network size (N > 200) display a pronounced regularizing capacity compared to randomized counterparts and an average entropy signature increase for singe randomization steps. This is also true for two other networks we explicitly checked: a directed version of the yeast network derived from the MZ database and an undirected enzyme-centric network based on the yeast stoichiometric matrix [39], where two enzymes are connected by a link if the product of the reaction catalyzed by the first enzyme serves as an educt for the second. Since a regularizing capacity is found for other representation of metabolic networks as well, we think that this finding a generic property of the network architecture of metabolic processes.
Passing from a real metabolic network to a randomized network samples a subset of graphs with a particular degree sequence. Another level of comparison is achieved if we regard the entropy signatures of simple model graphs of the same network size and connectivity, that is, the same number of nodes and links: Scale-free graphs obtained with a BA scheme [10] analog (where the number of attached links to newly introduced node varies to achieve the desired number of links), and regular graphs (where again the number of next-nearest neighbors differs between two and three) after a few rewiring steps (smallworld graphs) according to the original Watts-Strogatz scheme [37]. Fig. 4 shows the corresponding mean entropy signature and standard deviation for the 22 species from Fig. 2. Obviously, the synthetic model graphs react in a highly specific manner to the imposed dynamics: They separate from the metabolic networks and from each other and cluster tightly in the entropy plane. The scale-free graphs exhibit a slightly reduced word entropy compared to the real metabolic network, but an (on average) higher Shannon entropy. For the small world graphs again both entropies are elevated compared to the real metabolic networks. Another important feature of Fig. 4 is that for the different network types the two entropies respond differently. How do those model graphs react to randomization? For these synthetic networks the entropy shift measures the bias of the dynamic response, contained in the particular construction algorithm. For the scale-free graphs, we find a small reduction of the average word entropy and Shannon entropy under randomization.
If we randomize small-world graphs, and thereby break up the inherent regular neighborhoods, the randomized networks exhibit a reduced average word entropy and a elevated average Shannon entropy [31]. Thus, an average entropy increase, as observed for the metabolic networks discussed in this paper, is not a trivial effect of the randomization procedure. On the contrary, for chains of regularly connected nodes, a topological perturbation in general leads to a decreasing dynamic complexity. In a previous study [40], we showed this behaviour for synchronous and asynchronous update schemes with different observables. Moreover we showed, that both topological perturbation (i.e., the rewiring of links) and dynamic noise increase the regularizing capacity of an initially undisturbed cellular automaton.

IV. DISCUSSION
Characterizing complex networks with dynamic probes is a novel and promising approach. The recent progress in understanding genetic networks by mapping out the information flow through the corresponding graphs constitutes an excellent example of this line of thought [41]. Similarly, our analysis of metabolic networks condenses a variety of topological features into the entropy signature of the network, while the topological impact entering this quantity is selected with respect to its dynamic effect. The method discussed here may also serve as an unbiased probe to assess the dynamic performance of different network types, like protein-interaction networks or transcriptional networks, as well as other natural or technical networks. Moreover, using system-specific tailored dynamics could enhance the structure shaping process in engineering artificial network topologies.
Our key result is that metabolic network topologies embody the capacity to reliably regularize an imposed dynamics -expressed by a systematically reduced entropy signature compared to randomized networks with identical degree sequences. The large-scale architecture of metabolic networks is designed in such a way that complex and chaotic dynamics are systematically dampened out. We believe that the architectural disposition for steady-state dynamics in metabolism manifests in the observed regularizing capacity of the metabolic network topologies.
In this investigation we focused on the entropies averaged over the whole network. Particularly for a direct comparison with standard analysis techniques of metabolic networks, we believe that the entropy distribution over the network could also be extremely informative. The individual responses of the system's entities to a dynamic probe might help characterize different contributions to the functional state of the system, or, in terms of metabolic networks, it might help understand the principles governing the reorganization of steady-state fluxes under topological perturbations [42].
We acknowledge the comments of unknown referees, which substantially improved the manuscript.