# Unknown Title
## Complexity of Networks (reprise)
## Russell K. Standish
Mathematics and Statistics, University of New South Wales hpcoder@hpcoders.com.au
November 3, 2018
## Abstract
Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction.
In a previous paper, a complexity measure of networks was proposed based on the complexity is information content paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object.
The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical.
In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure.
This measure is extended to directed and weighted links, and several real world networks have their network complexities compared with randomly generated model networks with matched node and link counts, and matched link weight distributions. Compared with the random networks, the real world networks have significantly higher complexity, as do artificially generated food webs created via an evolutionary process, in several well known ALife models.
Keywords: complexity; information; networks; foodwebs
## 1 Introduction
This work situates itself firmly within the complexity is information content paradigm, a topic that dates back to the 1960s with the work of Kolmogorov, Chaitin and Solomonoff. Prokopenko et al. [28] provide a recent review of the area, and argue for the importance of information theory to the notion of complexity measure. In [32], I argue that information content provides an overarching complexity measure that connects the many and various complexity measures proposed (see [14] for a review) up to that time. In some ways, information-based complexity measures are priveleged, motivating the present work to develop a satisfactory information-based complexity measure of networks.
The idea is fairly simple. In most cases, there is an obvious prefix-free representation language within which descriptions of the objects of interest can be encoded. There is also a classifier of descriptions that can determine if two descriptions correspond to the same object. This classifier is commonly called the observer , denoted O ( x ).
To compute the complexity of some object x , count the number of equivalent descriptions ω ( /lscript,x ) of length /lscript that map to the object x under the agreed classifier. Then the complexity of x is given in the limit as /lscript →∞ :
$$( x ) = \lim _ { t \rightarrow + \infty } ( t \log N - \log w )$$
where N is the size of the alphabet used for the representation language.
Because the representation language is prefix-free, every description y in that language has a unique prefix of length s ( y ). The classifier does not care what symbols appear after this unique prefix. Hence ω ( /lscript,O ( y )) ≥ N /lscript -s ( y ) . As /lscript increases, ω must increase as fast, if not faster than N /lscript , and do so monotonically. Therefore C ( O ( y )) decreases monotonically with /lscript , but is bounded below by 0. So equation (1) converges.
The relationship of this algorithmic complexity measure to more familiar measures such as Kolmogorov (KCS) complexity, is given by the coding theorem[22, Thm 4.3.3]. In this case, the descriptions are halting programs of some given universal Turing machine U , which is also the classifier. Equation (1) then corresponds to the logarithm of the universal a priori probability , which is a kind of formalised Occam's razor that gives higher weight to simpler (in the KCS sense) computable theories for generating priors in Bayesian reasoning. The difference between this version of C and KCS complexity is bounded by a constant independent of the complexity of x , so these measures become equivalent in the limit as message size goes to infinity.
Many measures of network properties have been proposed, starting with node count and connectivity (no. of links), and passing in no particular order through cyclomatic number (no. of independent loops), spanning height (or width), no. of spanning trees, distribution of links per node and so on. Graphs tend to be classified using these measures small world graphs tend to have small spanning height relative to the number of nodes and scale free networks exhibit a power law distribution of node link count.
Some of these measures are related to graph complexity, for example node count and connectivity can be argued to be lower and upper bounds of the network complexity respectively. More recent attempts include offdiagonal complexity [9], which was compared with an earlier version of this proposal in [36], and medium articulation [42, 19].
However, none of the proposed measures gives a theoretically satisfactory complexity measure, which in any case is context dependent (ie dependent on the observer O , and the representation language).
In setting the classifier function, we assume that only the graph's topology counts - positions, and labels of nodes and links are not considered important. Links may be directed or undirected. We consider the important extension of weighted links in a subsequent section.
A plausible variant classifier problem might occur when the network describes a dynamical system (such as interaction matrix of the EcoLab model, which will be introduced later). In such a case, one might be interested in classifying the network according to numbers and types of dynamical attractors, which will be strongly influenced by the cyclomatic count of the core network, but only weakly influenced by the periphery. However, this problem lies beyond the scope of this paper.
The issue of representation language, however is far more problematic. In some cases, eg with genetic regulatory networks, there may be a clear representation language, but for many cases there is no uniquely identifiable language. However, the invariance theorem [22, Thm 2.1.1] states that the difference in complexity determined by two different Turing complete representation languages (each of which is determined by a universal Turing machine) is at most a constant, independent of the objects being measured. Thus, in some sense it does not matter what representation one picks - one is free to pick a representation that is convenient, however one must take care with non-Turing complete representations.
In the next section, I will present a concrete graph description language that can be represented as binary strings, and is amenable to analysis. The quantity ω in eq (1) can be simply computed from the size of the automorphism group, for which computationally feasible algorithms exist[23].
The notion of complexity presented in this paper naturally marries with thermodynamic entropy S [21]:
$$\max = C + S$$
where S max is called potential entropy , ie the largest possible value that entropy can assume under the specified conditions. The interest here is that a dynamical process updating network links can be viewed as a dissipative system, with links being made and broken corresponding to a thermodynamic flux. It would be interesting to see if such processes behave according the maximum entropy production principle[10] or the minimum entropy production principle[27].
In artificial life, the issue of complexity trends in evolution is extremely important[5]. I have explored the complexity of individual Tierran organisms[33,
35], which, if anything, shows a trend to simpler organisms. However, it is entirely plausible that complexity growth takes place in the network of ecological interactions between individuals. For example, in the evolution of the eukaryotic cell, mitochondria are simpler entities than the free-living bacteria they were supposedly descended from. A computationally feasible measure of network complexity is an important prerequisite for further studies of evolutionary complexity trends.
In the results section, several well-known food web datasets are analysed, and compared with randomly-shuffled 'neutral models'. An intriguing 'complexity surplus' is observed, which is also observed in the food webs of several different ALife systems that have undergone evolution.
## 2 Representation Language
One very simple implementation language for undirected graphs is to label the nodes 1 ..n , and the links by the pair ( i, j ) , i < j of nodes that the links connect. The linklist can be represented simply by an L = n ( n -1) / 2 length bitstring, where the 1 2 j ( j -1) + i th position is 1 if link ( i, j ) is present, and 0 otherwise.
The directed case requires doubling the size of the linklist, ie or L = n ( n -1). We also need to prepend the string with the value of N in order to make it prefixfree - the simplest approach is to interpret the number of leading 1s as the number n , which adds a term n +1 to the measured complexity.
This proposal was analysed in [36], and has the unsatisfactory property that the fully connected or empty networks are maximally complex for a given node count. An alternative scheme is to also include the link count as part of the prefix, and to use binary coding for both the node and link counts. The sequence will start with /ceilingleft log 2 n /ceilingright 1's, followed by a zero stop bit, so the prefix will be 2 /ceilingleft log 2 n /ceilingright + /ceilingleft log 2 L /ceilingright +1 bits.
This scheme entails that some of bitstrings are not valid networks, namely ones where the link count does not match the number of 1s in the linklist. We can, however, use rank encoding[25] of the linklist to represent the link pattern. The number of possible linklists corresponding to a given node/link specification is given by
$$\sigma = ( L ) = \frac { L _ { 1 } } { ( L - l ) ! }$$
This will have a minimum value of 1 at l = 0 (empty network) and l = L , the fully connected network.
Finally, we need to compute ω of the linklist, which is just the total number of possible renumberings of the nodes ( n !), divided by the size of the graph automorphism group, which can be practically computed by Nauty[23], or a new algorithm I developed called SuperNOVA[38] which exhibits better performance on sparsely linked networks.
A network A that has a link wherever B doesn't, and vice-versa might be called a complement of B . A bitstring for A can be found by inverting the 1s and 0s in the linklist part of the network description. Obviously, ω ( A,L ) = ω ( B,L ),
Figure 1: The new complexity measure as a function of link count for all networks with 8 nodes. This shows the strong dependence of complexity on link count, and the symmetry between networks and their complements.
<details>
<summary>Image 1 Details</summary>
### Visual Description
## Scatter Plot: Complexity vs. Links
### Overview
The image is a scatter plot displaying the relationship between two variables: "links" on the horizontal axis and "complexity" on the vertical axis. The data points, represented by black plus signs (`+`), form a distinct, roughly symmetric, inverted U-shaped or bell-shaped distribution. The plot suggests a non-linear relationship where complexity initially increases with the number of links, reaches a peak, and then decreases.
### Components/Axes
* **X-Axis (Horizontal):**
* **Label:** `links`
* **Scale:** Linear scale ranging from 0 to 60.
* **Major Tick Marks:** Labeled at intervals of 10 (0, 10, 20, 30, 40, 50, 60).
* **Minor Tick Marks:** Present between major ticks, indicating intervals of 2 units.
* **Y-Axis (Vertical):**
* **Label:** `complexity`
* **Scale:** Linear scale ranging from 15 to 40.
* **Major Tick Marks:** Labeled at intervals of 5 (15, 20, 25, 30, 35, 40).
* **Minor Tick Marks:** Present between major ticks, indicating intervals of 1 unit.
* **Data Series:**
* **Marker:** Black plus sign (`+`).
* **Legend:** No legend is present, indicating a single data series.
* **Plot Area:** A standard rectangular frame with tick marks on all four sides (bottom, left, top, right). The top and right axes mirror the scales of the bottom and left axes, respectively, but without numerical labels.
### Detailed Analysis
The data points are densely clustered, forming a clear pattern:
1. **Left Slope (Ascending):** Starting from approximately (links=5, complexity=16), the complexity values rise as the number of links increases. The points are tightly grouped along this upward trend.
2. **Peak Region:** The distribution reaches its maximum complexity values in the central region, roughly between **25 and 30 links**. The highest individual data points are located near **links=28-30**, with complexity values approaching **35**. The peak is not a single point but a plateau of high values.
3. **Right Slope (Descending):** Beyond approximately 30 links, the complexity values begin to decrease as the number of links continues to increase. The downward trend mirrors the left slope. The data extends to approximately (links=55, complexity=16).
4. **Data Spread:** At any given x-value (number of links), there is a vertical spread of complexity values. This spread is narrowest at the extremes (very low and very high link counts) and widest in the central peak region (around 20-35 links), where complexity values for a similar number of links can vary by approximately 5-8 units.
### Key Observations
* **Non-Linear Relationship:** The relationship is clearly non-linear and best described by a quadratic or inverted-U function.
* **Symmetry:** The distribution is approximately symmetric around a central axis near **links = 28**.
* **Maximum Complexity:** The highest observed complexity values (~35) occur within a specific, intermediate range of links (approximately 25-32).
* **Minimum Complexity:** The lowest complexity values (~16) are observed at both the low end (~5 links) and the high end (~55 links) of the x-axis range shown.
* **Density:** The highest density of data points is concentrated in the central region of the plot, between 15 and 40 links.
### Interpretation
The scatter plot demonstrates a classic **"inverted-U" or "Goldilocks" relationship** between the number of links and complexity. This pattern suggests that:
1. **Optimal Range:** There exists an intermediate, optimal range of "links" (approximately 25-30) that is associated with the highest levels of "complexity." This could imply that a system or entity requires a certain critical mass of connections to achieve high complexity, but beyond that point, additional links may lead to simplification, overload, or a different organizational principle.
2. **Trade-off or Phase Transition:** The decline in complexity after the peak indicates a potential trade-off. For example, in network theory, adding too many links might create redundancy or force a shift towards a more regular, less complex structure. In a cognitive or organizational context, it could represent a point where managing additional connections becomes counterproductive, leading to streamlined but less complex processes.
3. **Predictive Power:** The tight clustering along the curve suggests a strong, predictable relationship between these two variables within the observed domain. The vertical spread, however, indicates that other factors not plotted here also influence complexity.
4. **Underlying Principle:** This pattern is frequently observed in systems where performance, efficiency, or emergent properties are maximized at an intermediate level of a given parameter (e.g., connectivity, diversity, stress). The data visually argues against a simple "more is better" or "less is better" linear assumption.
</details>
so the complexity of a network is equal to that of its complement, as can be seen in Figure 1.
A connection can be drawn from this complexity measure, to that proposed in [11]. In their proposal, nodes are labelled, so the network is uniquely specified by the node and link counts, along with a rank-encoded linklist. Also, nodes may link to themselves, so L = n 2 . Consequently, their complexity measure will be
$$c = 2 \log _ { 2 } n + \vert \log _ { 2 } L \vert + 1 +$$
This is, to within a term of order log 2 n corresponding to the lead-in prefix specifying the node count, equal to the unnumbered formula given on page 326 of [11].
## 3 New complexity measure compared with the previous proposals
Figures 2 and 3 [36, Fig. 1] shows zcomplexity plotted against the new complexity and the original complexity proposal for all networks of order 8 respectively.
Figure 2: C z plotted against C for all networks of order 8. The diagonal line corresponds to C = C z +3.
<details>
<summary>Image 2 Details</summary>
### Visual Description
## Scatter Plot: Complexity vs. Zcomplexity
### Overview
The image is a scatter plot comparing two variables: "complexity" on the horizontal axis and "zcomplexity" on the vertical axis. The plot contains a large number of data points, each represented by a black "+" symbol. A dashed diagonal line runs from the bottom-left to the top-right, serving as a reference. The overall visual impression is a dense cloud of points showing a positive correlation between the two variables.
### Components/Axes
* **X-Axis (Horizontal):**
* **Label:** "complexity"
* **Scale:** Linear scale ranging from 15 to 40.
* **Major Tick Marks:** At 15, 20, 25, 30, 35, and 40.
* **Y-Axis (Vertical):**
* **Label:** "zcomplexity"
* **Scale:** Linear scale ranging from 10 to 35.
* **Major Tick Marks:** At 10, 15, 20, 25, 30, and 35.
* **Data Series:**
* A single series of data points, all marked with the same black "+" symbol. There is no separate legend.
* **Reference Element:**
* A dashed black diagonal line. It appears to start near the coordinate (15, 12) and extends to approximately (35, 32). This line likely represents the line of equality (y = x) or a model prediction line.
### Detailed Analysis
* **Data Distribution & Trend:**
* The data points form a broad, positively sloped cloud. The trend is clearly upward: as "complexity" increases, "zcomplexity" also tends to increase.
* The cloud of points is densest in the central region, roughly between complexity values of 20 to 30 and zcomplexity values of 20 to 27.
* The spread (variance) of zcomplexity for a given complexity appears relatively consistent across the range, though it may be slightly wider in the middle.
* **Relationship to Reference Line:**
* The majority of data points lie **above** the dashed diagonal reference line. This indicates that for most observations, the value of "zcomplexity" is greater than the value of "complexity".
* The points are not evenly distributed around the line; there is a clear bias towards the upper side.
* **Spatial Grounding & Outliers:**
* **Top-Right Region:** A few points extend to the highest values, near complexity=35 and zcomplexity=32. One notable point is at approximately (35, 25), which lies significantly below the main cloud and the reference line.
* **Bottom-Left Region:** Points extend down to approximately (15, 18). The lowest zcomplexity value appears to be around 17, near complexity=16.
* **Bottom-Right Region (Potential Outlier):** The point near (35, 25) is a clear outlier, being far below the general trend and the reference line.
* **Top-Left Region:** There are no data points in the extreme top-left (e.g., low complexity, very high zcomplexity).
### Key Observations
1. **Strong Positive Correlation:** There is a clear, strong positive linear relationship between "complexity" and "zcomplexity".
2. **Systematic Bias:** The variable "zcomplexity" is systematically higher than "complexity" for the vast majority of the data points, as evidenced by their position above the diagonal reference line.
3. **Consistent Spread:** The vertical dispersion of points around the general trend appears fairly uniform across the observed range of complexity.
4. **Notable Outlier:** A single data point at approximately (35, 25) deviates substantially from the overall pattern, having a much lower zcomplexity than expected for its high complexity value.
### Interpretation
The plot demonstrates a robust, positive association between the two measured quantities, "complexity" and "zcomplexity". The fact that most points lie above the y=x reference line suggests that "zcomplexity" is not merely a direct copy of "complexity" but is consistently amplified or transformed to a higher value. This could imply that "zcomplexity" represents a derived metric, a scaled version, or a measurement that inherently includes an additional factor that increases its magnitude relative to the base "complexity".
The outlier at (35, 25) is significant. In a technical context, this point would warrant investigation—it could represent a measurement error, a unique case, or a failure of the general model that relates the two variables. The uniform spread of points suggests the relationship is stable across the measured range, without obvious heteroscedasticity (changing variance). Overall, the graph effectively communicates that while the two variables are tightly linked, they are not identical, with "zcomplexity" being the larger value in almost all cases.
</details>
Figure 3: C z plotted against the original C from [36] for all networks of order 8, reproduced from that paper.
<details>
<summary>Image 3 Details</summary>
### Visual Description
## Scatter Plot: Relationship between C and zcomplexity
### Overview
The image is a scatter plot displaying the relationship between two variables: "C" on the horizontal axis and "zcomplexity" on the vertical axis. The plot shows a positive correlation, where higher values of C are generally associated with higher values of zcomplexity. The data points are represented by black plus signs (`+`) on a white background with a light gray grid.
### Components/Axes
* **X-Axis (Horizontal):**
* **Label:** `C`
* **Scale:** Linear scale ranging from 20 to 38.
* **Major Tick Marks:** At intervals of 2 (20, 22, 24, 26, 28, 30, 32, 34, 36, 38).
* **Y-Axis (Vertical):**
* **Label:** `zcomplexity`
* **Scale:** Linear scale ranging from 16 to 34.
* **Major Tick Marks:** At intervals of 2 (16, 18, 20, 22, 24, 26, 28, 30, 32, 34).
* **Data Series:** A single data series plotted as black plus signs (`+`). There is no legend, as only one series is present.
* **Grid:** A light gray, dotted grid is present, aligned with the major tick marks on both axes.
### Detailed Analysis
* **Data Distribution and Trend:**
* The data points form a broad, upward-sloping cloud from the lower-left to the upper-right of the plot area, indicating a positive correlation between C and zcomplexity.
* The relationship is not perfectly linear; the spread (variance) of zcomplexity values increases as C increases.
* **Spatial Distribution of Points:**
* **High Density Region (C ≈ 21 to 28):** The majority of data points are concentrated in a dense, vertical band on the left side of the plot. Within this band, for a given C value, zcomplexity values span a range of approximately 4-6 units. For example, at C ≈ 22, zcomplexity values range from ~18 to ~23.
* **Moderate Density Region (C ≈ 28 to 32):** The points become more scattered. The positive trend continues, but the vertical spread for a given C is wider.
* **Low Density / Outlier Region (C > 32):** There are very few data points. Notable outliers include:
* A point at approximately (C=32.2, zcomplexity=32.3) – the highest zcomplexity value.
* A point at approximately (C=37.0, zcomplexity=18.0) – an outlier with a very high C but low zcomplexity, deviating from the main trend.
* **Approximate Value Ranges:**
* **C:** Data spans from ~21.5 to ~37.0.
* **zcomplexity:** Data spans from ~17.8 to ~32.3.
* The core cluster (where most points lie) is within C ≈ 21.5-28.0 and zcomplexity ≈ 18.0-28.0.
### Key Observations
1. **Positive Correlation:** The primary visual pattern is a clear, positive association between the two variables.
2. **Heteroscedasticity:** The variance of zcomplexity is not constant across the range of C. It is smaller at lower C values and increases substantially at higher C values.
3. **Data Density Gradient:** The number of observations decreases sharply as C increases beyond 28.
4. **Notable Outlier:** The point near (37, 18) is a significant outlier, suggesting an instance where a very high C value did not correspond to a high zcomplexity.
### Interpretation
The scatter plot demonstrates a **positive but noisy relationship** between the variable `C` and `zcomplexity`. This suggests that `C` is a predictor of `zcomplexity`, but not a deterministic one. The increasing spread (heteroscedasticity) implies that the predictive power of `C` for `zcomplexity` weakens as `C` becomes larger; other factors likely have a greater influence on `zcomplexity` at higher levels of `C`.
The high density of points at lower C values indicates that the dataset is skewed towards observations with smaller C. The outlier at high C and low zcomplexity is particularly interesting from an investigative standpoint. It could represent a measurement error, a unique case, or a subgroup where the typical relationship breaks down. In a technical context, this point would warrant further examination to understand its cause.
**In summary, the chart shows that while `zcomplexity` tends to increase with `C`, the relationship is probabilistic and subject to greater uncertainty at higher values of `C`.**
</details>
The new complexity proposal is quite well correlated with zcomplexity, and is in this example about 3 bits higher than zcomplexity. This is just the difference in prefixes between the two schemes (the original proposal used 8 1 bits followed by a stop bit = 9 bits overall to represent the node count, and the new scheme uses 3 1 bits and a stop bit to represent the field width of the node count, 3 bits for the node field and 5 bits for the link count field = 12 bits overall). Data points appearing above the line correspond to networks whose linkfields compress better with the new algorithm than the scheme used with zcomplexity. Conversely, data points below the line are better compressed with the old algorithm.
We can conclude that the new scheme usually compresses the link list field better than the run length encoding scheme employed in [36], and so is a better measure of complexity than zcomplexity, as well as being far more tractable. The slightly more complex prefix of the new scheme grows logarithmically with node count, so will ultimately be more compressed than the prefix of the old scheme, which grows linearly.
## 4 Comparison with medium articulation
In the last few years Wilhelm[42, 19] introduced a new complexity like measure that addresses the intuition that complexity should be minimal for the empty and full networks, and peak for intermediate values (like figure 1). It is obtained by multiplying an information quantity that increases with link count by a different information that falls. The resulting measure is therefore in square bits, so one should perhaps consider the square root as the complexity measure.
Precisely, medium articulation is given by
where w ij is the normalised weight ( ∑ ij w ij = 1) of the link from node i to node j .
Figure 4 shows medium articulation plotted against C for a sample of 1000 Erd¨ os-R´ enyi networks up to order 500. There is no clear relationship between medium articulation and complexity for the average network. Medium articulation does not appear to discriminate between complex networks. however if we restrict our attention to simple networks (Figures 5 and 6) medium articulation is strongly correlated with complexity, and so could be used as a proxy for complexity for these cases.
## 5 Weighted links
Whilst the information contained in link weights might be significant in some circumstances (for instance the weights of a neural network can only be varied in a limited range without changing the overall qualitative behaviour of the network), of particular theoretical interest is to consider the weights as continuous
Figure 4: Medium Articulation plotted against complexity for 1000 randomly sampled Erd¨ os-R´ enyi graphs up to order 500.
<details>
<summary>Image 4 Details</summary>
### Visual Description
## Scatter Plot: MA vs. C
### Overview
The image displays a scatter plot showing the relationship between two variables, labeled "C" on the horizontal axis and "MA" on the vertical axis. The plot contains a large number of data points (several hundred to a few thousand), all rendered as small, gray, open circles. The data shows a dense concentration near the origin that spreads out significantly as the value of C increases.
### Components/Axes
* **Chart Type:** Scatter Plot.
* **X-Axis:**
* **Label:** `C` (italicized).
* **Scale:** Linear.
* **Range:** 0 to 250,000.
* **Major Tick Marks & Labels:** 0, 50000, 100000, 150000, 200000, 250000.
* **Y-Axis:**
* **Label:** `MA` (italicized).
* **Scale:** Linear.
* **Range:** 0 to 30.
* **Major Tick Marks & Labels:** 0, 5, 10, 15, 20, 25, 30.
* **Legend:** None present. All data points are represented by the same symbol and color (gray circles).
* **Data Points:** Represented as small, gray, open circles. No other distinguishing features (e.g., color, shape) are used to categorize the data.
### Detailed Analysis
* **Data Distribution & Density:**
* The highest density of points is concentrated in the region where `C` is between 0 and approximately 25,000, and `MA` is between 0 and 15.
* As `C` increases beyond 25,000, the points become more dispersed, covering a wider range of `MA` values.
* **Trend Description (Visual):** The overall cloud of points suggests a positive, but highly variable, relationship. The lower boundary of the point cloud appears to slope upward from the origin. The upper boundary also shows an upward trend, but with much greater scatter. The vertical spread (variance in `MA`) for a given `C` increases substantially as `C` increases.
* **Approximate Data Ranges:**
* For `C` < 10,000: `MA` values range from near 0 up to ~20.
* For `C` between 50,000 and 100,000: `MA` values are spread roughly between 8 and 28.
* For `C` > 150,000: The number of points decreases, but they are scattered widely, with `MA` values ranging from approximately 10 to 20. The maximum observed `MA` appears to decrease slightly for the highest `C` values (above 200,000).
### Key Observations
1. **Heteroscedasticity:** The variance of `MA` is not constant across values of `C`. The spread of `MA` values increases dramatically as `C` increases, indicating a strong heteroscedastic relationship.
2. **Density Gradient:** The data is extremely dense near the origin (`C` and `MA` both low) and becomes progressively sparser towards the top-right of the plot.
3. **Potential Ceiling Effect:** There appears to be an upper bound or ceiling for `MA` around the value of 30, with very few points approaching this limit, and none exceeding it.
4. **Sparse High-C Region:** Data points with `C` values above 200,000 are relatively rare compared to the lower `C` regions.
### Interpretation
The scatter plot demonstrates a positive but noisy association between the variables `C` and `MA`. The key insight is not a simple linear correlation, but the structure of the variance.
* **Relationship:** Higher values of `C` are generally associated with higher possible values of `MA`, but also with much greater uncertainty or variability in `MA`. A low `C` value reliably predicts a low-to-moderate `MA`, while a high `C` value could correspond to a wide range of `MA` outcomes.
* **Underlying Phenomenon:** This pattern is characteristic of processes where the factor represented by `C` enables or scales the potential for `MA`, but other, unmeasured factors become increasingly influential as `C` grows. For example, `C` could be "computational resources" and `MA` "model accuracy," where more resources allow for higher accuracy but also introduce more variables (like algorithm choice, data quality) that cause greater spread in results.
* **Data Quality/Collection:** The extreme density at low values suggests either a natural clustering of observations in that regime or a sampling bias where low-`C` scenarios are more frequently observed or measured. The sparsity at high `C` may indicate these conditions are rarer, more expensive to generate, or harder to measure.
* **Investigative Focus:** An analyst should investigate the causes of the increasing variance. The points forming the upper edge of the cloud might represent optimal conditions or efficient processes, while those on the lower edge might indicate inefficiencies or confounding negative factors. The plot argues against using a simple linear model without also modeling the variance structure (e.g., using weighted regression or a generalized linear model).
</details>
Figure 5: Medium Articulation plotted against complexity for 1000 randomly sampled Erd¨ os-R´ enyi graphs up to order 500 with no more than 2 n links.
<details>
<summary>Image 5 Details</summary>
### Visual Description
## Scatter Plot: Relationship between C and MA
### Overview
The image is a scatter plot displaying a large dataset of individual data points, each represented by a small, hollow circle. The plot illustrates the relationship between two variables, labeled "C" on the horizontal axis and "MA" on the vertical axis. The data shows a clear, non-linear, positive correlation where MA increases with C, but the rate of increase slows as C becomes larger.
### Components/Axes
* **Chart Type:** Scatter Plot.
* **X-Axis (Horizontal):**
* **Label:** "C" (centered below the axis).
* **Scale:** Linear scale.
* **Range:** 0 to 6000.
* **Major Tick Marks:** At intervals of 1000 (0, 1000, 2000, 3000, 4000, 5000, 6000).
* **Y-Axis (Vertical):**
* **Label:** "MA" (centered to the left of the axis, rotated 90 degrees).
* **Scale:** Linear scale.
* **Range:** 0 to 14.
* **Major Tick Marks:** At intervals of 2 (0, 2, 4, 6, 8, 10, 12, 14).
* **Data Series:** A single series of data points. All points are visually identical (small, gray, hollow circles). There is no legend, as only one data category is present.
* **Spatial Layout:** The plot area is bounded by a rectangular frame. The axes are positioned at the bottom and left edges. The data cloud originates near the coordinate (0,0) and extends towards the top-right corner of the plot area.
### Detailed Analysis
* **Data Distribution & Trend:**
* **Trend Verification:** The overall data cloud forms a concave-down curve. It begins with a very steep, near-vertical ascent from the origin (0,0) and gradually transitions to a much shallower, almost horizontal slope as it approaches the right side of the graph.
* **Point Density:** The data points are extremely dense in the region where C is between 0 and approximately 1000, forming a thick, dark band. As C increases beyond 1000, the points become progressively more scattered and sparse, though they still follow the clear curved trend.
* **Approximate Value Ranges:**
* At C ≈ 0, MA ≈ 0.
* At C ≈ 1000, MA values range approximately from 6 to 9, with the central tendency around 7.5.
* At C ≈ 3000, MA values range approximately from 10 to 12.
* At C ≈ 5000, MA values are clustered between approximately 12.5 and 14.
* **Spread/Variance:** The vertical spread (variance in MA for a given C) appears relatively consistent in absolute terms across the range of C, but becomes more noticeable visually at higher C values due to the lower point density.
### Key Observations
1. **Strong Non-Linear Correlation:** There is an unambiguous, strong positive relationship between C and MA. The relationship is not linear; it exhibits clear diminishing returns.
2. **Saturation Behavior:** The curve suggests a saturation effect. As the independent variable C increases, the dependent variable MA continues to increase but approaches what appears to be an asymptotic limit near MA = 14.
3. **High Initial Sensitivity:** The steepest part of the curve is at very low C values (C < 500), indicating that MA is highly sensitive to changes in C when C is small.
4. **Absence of Outliers:** The data points form a cohesive cloud with no obvious outliers far from the main trend. All points adhere closely to the implied curve.
5. **Language:** All text in the image (axis labels "C" and "MA") is in English.
### Interpretation
This scatter plot demonstrates a classic **diminishing returns** or **saturation kinetics** relationship. The variable "MA" is dependent on "C", but its growth is constrained as "C" increases.
* **What the data suggests:** The pattern is characteristic of many natural and engineered systems. For example:
* In **chemistry/enzymology**, this could resemble a Michaelis-Menten plot where reaction rate (MA) increases with substrate concentration (C) until enzyme active sites are saturated.
* In **economics**, it could model production output (MA) versus capital investment (C), where initial investments yield high returns, but later investments add less incremental value.
* In **machine learning**, it might show model accuracy (MA) versus training dataset size (C), where more data helps a lot initially, but gains plateau.
* **How elements relate:** The independent variable "C" drives the increase in "MA". The system's capacity to translate increases in C into increases in MA is finite, leading to the observed plateau. The high density of points at low C suggests that the process or phenomenon being measured is most frequently observed or operates in that lower range.
* **Notable Anomalies:** There are no anomalies. The data is remarkably consistent with the theoretical curve it implies. The lack of scatter at very low C and the uniform spread at higher C suggest a stable, well-characterized process with inherent, consistent variability.
**In summary, the image provides a clear visual fact: the relationship between C and MA is positive, non-linear, and saturating. The precise mathematical function (e.g., logarithmic, square root, hyperbolic) cannot be determined without the raw data, but the qualitative behavior is unequivocally demonstrated.**
</details>
Figure 6: Medium Articulation plotted against complexity for 1000 randomly sampled Erd¨ os-R´ enyi graphs up to order 500 with more than n ( n -5) / 2 links.
<details>
<summary>Image 6 Details</summary>
### Visual Description
## Scatter Plot: MA vs. C
### Overview
The image displays a scatter plot showing the relationship between two variables, labeled "C" on the horizontal axis and "MA" on the vertical axis. The plot consists of a dense cloud of data points that form a clear, smooth, and monotonically increasing curve. The relationship appears non-linear, with the rate of increase in MA slowing as C becomes larger.
### Components/Axes
* **Chart Type:** Scatter Plot.
* **X-Axis (Horizontal):**
* **Label:** `C` (italicized).
* **Scale:** Linear.
* **Range:** 0 to 300,000.
* **Major Tick Marks & Labels:** 0, 50000, 100000, 150000, 200000, 250000, 300000.
* **Y-Axis (Vertical):**
* **Label:** `MA` (italicized).
* **Scale:** Linear.
* **Range:** 3 to 12.
* **Major Tick Marks & Labels:** 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
* **Data Series:** A single series of data points, all rendered as small, open circles (â—‹). There is no legend, as only one data series is present.
* **Spatial Layout:** The plot area is bounded by a rectangular frame. The axes labels are centered along their respective axes. The data points are densely packed, forming a continuous band.
### Detailed Analysis
* **Trend Description:** The data series exhibits a strong, positive, non-linear correlation. The curve rises very steeply from the bottom-left corner and gradually flattens out towards the top-right, resembling a logarithmic or square root function shape.
* **Key Data Points (Approximate):**
* At `C ≈ 0`, `MA` starts at approximately **3**.
* The curve passes through `MA ≈ 6` at a very low `C` value (likely under 1,000).
* At `C = 50,000`, `MA` is approximately **9.0**.
* At `C = 100,000`, `MA` is approximately **10.0**.
* At `C = 150,000`, `MA` is approximately **10.5**.
* At `C = 200,000`, `MA` is approximately **10.8**.
* At `C = 250,000`, `MA` is approximately **11.0**.
* The curve appears to approach an asymptote just above `MA = 11` as `C` approaches 300,000.
* **Data Distribution:** The points are tightly clustered along the trend line with very little vertical scatter, indicating a highly deterministic or low-noise relationship between C and MA.
### Key Observations
1. **Diminishing Returns:** The most prominent feature is the clear pattern of diminishing returns. Initial increases in `C` yield large gains in `MA`, but the benefit per unit of `C` decreases substantially as `C` grows.
2. **High Density at Low C:** The data points are extremely dense for `C` values between 0 and approximately 20,000, making the initial ascent appear almost as a solid line.
3. **Consistent Shape:** The curve is smooth and consistent across the entire range, with no visible outliers, breaks, or secondary trends.
4. **Asymptotic Behavior:** The trend suggests that `MA` may have an upper limit or saturation point it is approaching, likely in the range of `MA = 11.0 to 11.5`.
### Interpretation
This plot demonstrates a classic **concave, increasing function** with strong diminishing marginal returns. The variable `MA` is highly sensitive to changes in `C` when `C` is small, but becomes progressively less sensitive as `C` increases.
* **What it Suggests:** The relationship could model many real-world phenomena, such as:
* **Performance vs. Resources:** `C` could represent computational cost (e.g., FLOPs, model size) and `MA` could represent model accuracy or a performance metric. The plot shows that throwing more resources at the problem yields rapidly decreasing performance improvements.
* **Learning Curve:** `C` could be training examples or time, and `MA` could be a skill or knowledge metric. Early learning is fast, but mastery requires exponentially more effort.
* **Physical Law:** It could represent a physical relationship like stress vs. strain in a material (elastic region) or the charging curve of a capacitor.
* **Underlying Function:** The shape is characteristic of functions like `MA = a * ln(C + b) + c` (logarithmic) or `MA = a * sqrt(C) + b` (square root). The tight fit suggests the data may be generated from such a deterministic equation with minimal noise.
* **Practical Implication:** For decision-making, the plot indicates that operating in the region of `C > 150,000` is inefficient if the goal is to maximize `MA` per unit of `C`. The "knee" of the curve, where the rate of return starts to drop sharply, appears to be around `C = 20,000 to 50,000`.
</details>
parameters connecting one network structure with another. For instance if a network X has the same network structure as the unweighted graph A, with b links of weight 1 describing the graph B and the remaining a -b links of weight w , then we would like the network complexity of X to vary smoothly between that of A and B as w varies from 1 to 0. [16] introduced a similar measure.
The most obvious way of defining this continuous complexity measure is to start with normalised weights ∑ i w i = 1. Then arrange the links in weight order, and compute the complexity of networks with just those links of weights less than w . The final complexity value is obtained by integrating:
$$c ( X = N \times L ) = \int _ { 0 } ^ { 1 } c ( N \times \{ i \}$$
Obviously, since the integrand is a stepped function, this is computed in practice by a sum of complexities of partial networks.
## 6 Comparing network complexity with the Erd¨ osR´ enyi random model
I applied the weighted network complexity measure (6) to several well-known real network datasets, obtained from Mark Newman's website[41, 20, 26], the Pajek website[7, 39, 40, 17, 2, 1, 3] and Duncan Watt's website[13, 18], with the
Figure 7: The distribution of complexities of the shuffled Narragansett Bay food web[24]. Both a normal and a log-normal distribution have been fitted to the data - the log-normal is a slightly better fit than the normal distribution. In the bottom right hand corner is marked the complexity value computed for the actual Narragansett food web (58.2 bits).
<details>
<summary>Image 7 Details</summary>
### Visual Description
## Chart: Dual-Fitted Distribution Curves on Complexity Data
### Overview
The image displays a 2D scatter plot with two overlaid fitted probability distribution curves. The chart compares how well a log-normal distribution (green dashed line) and a normal distribution (red dotted line) model a set of empirical data points (black 'x' marks). The data appears to represent some measure of "Complexity" on the x-axis against an unspecified frequency or density on the y-axis.
### Components/Axes
* **X-Axis:**
* **Label:** `Complexity → |`
* **Scale:** Linear, ranging from approximately 35 to 60.
* **Major Tick Marks:** 35, 40, 45, 50, 55, 60.
* **Y-Axis:**
* **Label:** Not explicitly labeled. Represents frequency, count, or probability density.
* **Scale:** Linear, ranging from 0 to 40.
* **Major Tick Marks:** 0, 5, 10, 15, 20, 25, 30, 35, 40.
* **Data Series:**
1. **Empirical Data:** Represented by black 'x' markers. The points are densely clustered between x=37 and x=43, with a peak density around x=40. The distribution is right-skewed, with a long tail extending to approximately x=48.
2. **Model 1 (Green Dashed Line):** A fitted log-normal distribution curve. Its equation is provided in the legend.
3. **Model 2 (Red Dotted Line):** A fitted normal (Gaussian) distribution curve. Its equation is provided in the legend.
* **Legend:**
* **Position:** Top-right corner of the plot area.
* **Content:**
* **Green Dashed Line:** `(39.8 / (0.0351403 * x)) * exp( -0.5 * ( (log(x) - 3.67978) / 0.0351403 )^2 )`
* **Red Dotted Line:** `(39.8 / 1.40794) * exp( -0.5 * ( (x - 39.6623) / 1.40794 )^2 )`
### Detailed Analysis
* **Data Point Distribution:** The black 'x' markers form a unimodal, right-skewed distribution. The highest concentration of points (peak) is visually estimated at approximately **x = 40, y = 30**. The data spans from a minimum near **x ≈ 37** to a maximum near **x ≈ 48**.
* **Curve Trends & Key Points:**
* **Green Dashed Line (Log-Normal Model):**
* **Trend:** Rises steeply from the left, peaks, and then declines more gradually, following the right skew of the data.
* **Peak:** Visually aligns closely with the data's peak at approximately **x = 40, y ≈ 30**.
* **Fit:** Appears to follow the overall shape and skew of the data points very well, especially in the tail region (x > 43).
* **Red Dotted Line (Normal Model):**
* **Trend:** Symmetrical bell curve.
* **Peak:** Centered at approximately **x = 39.7** (as per its equation: mean = 39.6623), with a peak height of approximately **y ≈ 28.3** (calculated as 39.8 / 1.40794).
* **Fit:** Captures the central tendency but fails to model the right skew. It underestimates the peak density and overestimates the density on the left side (x < 38) while underestimating it on the right tail (x > 43).
### Key Observations
1. **Skewness:** The empirical data is clearly right-skewed (positively skewed), with a tail extending towards higher complexity values.
2. **Model Superiority:** The log-normal distribution (green dashed line) provides a visually superior fit to the data compared to the normal distribution (red dotted line). It better matches both the peak location/height and the asymmetric tail.
3. **Parameter Insight:** The equations reveal both models are scaled by the same factor (39.8), likely related to the total area under the curve or sample size. The log-normal model's parameters (log-mean ≈ 3.68, log-std ≈ 0.035) describe the distribution of the logarithm of the complexity values.
### Interpretation
This chart demonstrates a classic statistical modeling scenario where the underlying data-generating process is better described by a multiplicative (log-normal) rather than an additive (normal) process. In contexts like software complexity, biological measurements, or financial returns, this is common.
* **What it Suggests:** The "Complexity" metric being measured likely results from the product of many small, independent factors, leading to the log-normal distribution. A normal distribution would imply complexity results from the sum of many independent factors, which does not fit the observed skew.
* **Why it Matters:** Choosing the correct distributional model is critical for accurate statistical inference, prediction, and understanding the system's nature. Using the normal model here would lead to systematic errors: underestimating the probability of high-complexity events (the right tail) and overestimating the probability of very low-complexity events.
* **Anomaly/Note:** The y-axis lacks a formal label, which is a minor omission for a technical document. Its meaning (e.g., "Frequency," "Probability Density," "Count") must be inferred from context. The arrow in the x-axis label (`→ |`) is also unconventional and its specific meaning is unclear without additional context.
</details>
results shown in Table 1. The number of nodes and links of the networks varied greatly, so the raw complexity values are not particularly meaningful, as the computed value is highly dependent on these two network parameters. What is needed is some neutral model for each network to compare the results to.
At first, one might want to compare the values to an Erd¨ os-R´ enyi random network with the same number of nodes and links. However, in practice, the real network complexities are much less than that of an ER network with the same number of nodes and links. This is because in our scheme, a network with weighted link weights looks somewhat like a simpler network formed by removing some of the weakest links from the original. An obvious neutral network model with weighted network links has the weights drawn from a normal distribution with mean 0. The sign of the weight can be interpreted as the link direction. Because the weights in equation (6) are normalised, the complexity value is independent of the standard deviation of the normal distribution. However, such networks are still much more complex than the real networks, as the link weight distribution doesn't match that found in the real network.
Instead, a simple way of generating a neutral model is to break and reattach the network links to random nodes, without merging links, leaving the original link weights unaltered. In the following experiment, we generate 1000 of these shuffled networks. The distribution of complexities can be fitted to a lognormal distribution, which gives a better likelihood than a normal distribution for all networks studied here[8], although the difference between a log-normal and a normal fit becomes less pronounced for more complex networks. Figure 7 shows the distribution of complexity values computed by shuffling the Narragansett food web, and the best fit normal and lognormal distributions.
In what follows we compute the average 〈 ln C ER 〉 and standard deviation
σ ER of the logarithm of the neutral model complexities. We can then compare the network complexity with the ensemble of neutral models to obtain a p -value, the probability that the observed complexity is that of a random network. The p -values are so small that is better to represent the value as a number of standard deviations ('sigmas') that the logarithm of the measured complexity value is from the mean logarithm of the shuffled networks. A value of 6 sigmas corresponds to a p -value less than 1 . 3 × 10 -4 , although this must be taken with a certain grain of salt, as the distribution of shuffled complexity values has a fatter tail than the fitted log-normal distribution. In none of these samples did the shuffled network complexity exceed the original network's complexity, meaning the p -value is less than 10 -3 . The difference C exp( 〈 ln C ER 〉 ) is the amount of information contained in the specific arrangement of links.
A code implementing this algorithm is implemented as a C++ library, and is available from version 4.D36 onwards as part of the Eco Lab system, an open source modelling framework hosted at http://ecolab.sourceforge.net.
## 7 ALife models
## 7.1 Tierra
Tierra [29] is a well known artificial life system in which self reproducing computer programs written in an assembly-like language are allowed to evolve. The programs, or digital organisms can interact with each other via template matching operations, modelled loosely on the way proteins interact in real biological systems. A number of distinct strategies evolve, including parasitism, where organisms make use of another organism's code and hyper-parasitism where an organism sets traps for parasites in order to steal their CPU resources. At any point in time in a Tierra run, there is an interaction network between the species present, which is the closest thing in the Tierra world to a foodweb.
Tierra is an aging platform, with the last release (v6.02) having been released more than six years ago. For this work, I used an even older release (5.0), for which I have had some experience in working with. Tierra was originally written in C for an environment where ints were 16 bits and long ints 32 bits. This posed a problem for using it on the current generation of 64 bit computers, where the word sizes are doubled. Some effort was needed to get the code 64 bit clean. Secondly a means of extracting the interaction network was needed. Whilst Tierra provided the concept of 'watch bits', which recorded whether a digital organism had accessed another's genome or vice versa, it did not record which other genome was accessed. So I modified the template matching code to log the pair of genome labels that performed the template match to a file.
Having a record of interactions by genotype label, it is necessary to map the genotype to phenotype. In Tierra, the phenotype is the behaviour of the digital organism, and can be judged by running the organisms pairwise in a tournament, to see what effect each has on the other. The precise details for how this can be done is described in [33].
Having a record of interactions between phenotypes, and discarding self-self interactions, there are a number of ways of turning that record into a foodweb. The simplest way, which I adopted, was sum the interactions between each pair of phenotypes over a sliding window of 20 million executed instructions, and doing this every 100 million executed instructions. This lead to time series of around 1000 foodwebs for each Tierra run.
In Tierra, parsimony pressure is controlled by the parameter SlicePow. CPU time is allocated proportional to genome size raised to SlicePow. If SlicePow is close to 0, then there is great evolutionary pressure for the organisms to get as small as possible to increase their replication rate. When it is one, this pressure is eliminated. In [35], I found that a SlicePow of around 0.95 was optimal. If it were much higher, the organisms grow so large and so rapidly that they eventually occupy more than 50% of the soup. At which point they kill the soup at their next Mal (memory allocation) operation. In this work, I altered the implementation of Mal to fail if the request was more than than the soup size divided by minimum population save threshold (usually around 10). Organisms any larger than this will never appear in the Genebanker (Tierra's equivalent of the fossil record), as their population can never exceed the save threshold. This modification allows SlicePow = 1 runs to run for an extensive period of time without the soup dying.
## 7.2 EcoLab
EcoLab was introduced by the author as a simple model of an evolving ecosystem [31]. The ecological dynamics is described by an n -dimensional generalised Lotka-Volterra equation:
$$n _ { i } = r _ { i n _ { i } } + \sum _ { j } ^ { n _ { i } } b _ { i j } n _ { j }$$
where n i is the population density of species i , r i its growth rate and β ij the interaction matrix. Extinction is handled via a novel stochastic truncation algorithm, rather than the more usual threshold method. Speciation occurs by randomly mutating the ecological parameters ( r i and β ij ) of the parents, subject to the constraint that the system remain bounded [30].
The interaction matrix is a candidate foodweb, but has too much information. Its offdiagonal terms may be negative as well as positive, whereas for the complexity definition (6), we need the link weights to be positive. There are a number of ways of resolving this issue, such as ignoring the sign of the off-diagonal term (ie taking its absolute value), or antisymmetrising the matrix by subtracting its transpose, then using the sign of the offdiagonal term to determine the link direction.
For the purposes of this study, I chose to subtract just the negative β ij terms from themselves and their transpose terms β ji . This effects a maximal encoding of the interaction matrix information in the network structure, with link direction and weight encoding the direction and size of resource flow. The effect is as follows:
- Both β ij and β ji are positive (the mutualist case). Neither offdiagonal term changes, and the two nodes have links pointing in both directions, with weights given by the two offdiagonal terms.
- Both β ij and β ji are negative (the competitive case). The terms are swapped, and the signs changed to be positive. Again the two nodes have links pointing in both directions, but the link direction reflects the direction of resource flow.
- Both β ij and β ji are of opposite sign (the predator-prey or parasitic case). Only a single link exists between species i and j , whose weight is the summed absolute values of the offdiagonal terms, and whose link direction reflects the direction of resource flow.
## 7.3 Webworld
Webworld is another evolving ecology model, similar in some respects to EcoLab, introduced by [6], with some modifications described in [12]. It features more realistic ecological interactions than does EcoLab, in that it tracks biomass resources. It too has an interaction matrix called a functional response in that model that could serve as a foodweb, which is converted to a directed weighted graph in the same way as the EcoLab interaction matrix. I used the Webworld implementation distributed with the Eco Lab simulation platform [34]. The parameters were chosen as R = 10 5 , b = 5 × 10 -3 , c = 0 . 8 and λ = 0 . 1.
## 8 Methods and materials
Tierra was run on a 512KB soup, with SlicePow set to 1, until the soup died, typically after some 5 × 10 10 instructions have executed. Some variant runs were performed with SlicePow=0.95, and with different random number generators, but no difference in the outcome was observed.
The source code of Tierra 5.0 was modified in a few places, as described in the Tierra section of this paper. The final source code is available as tierra.5.0.D7.tar.gz from the Eco Lab website hosted on SourceForge (http://ecolab.sf.net).
The genebanker output was processed by the eco-tierra.3.D13 code, also available from the Eco Lab website, to produce a list of phenotype equivalents for each genotype. A function for processing the interaction log file generated by Tierra and producing a timeseries of foodweb graphs was added to Eco-tierra. The script for running this postprocessing step is process ecollog.tcl.
The EcoLab model was adapted to convert the interaction matrix into a foodweb and log the foodweb to disk every 1000 time steps for later processing. The Webworld model was adapted similarly. The model parameters were as documented in the included ecolab.tcl and webworld.tcl experiment files of the ecolab.5.D1 distribution, which is also available from the Eco Lab website.
Finally, each foodweb, whether real world, or ALife generated, and 100 linkshuffled control versions were run through the network complexity algorithm
Figure 8: Complexity of the Tierran interaction network for SlicePow=0.95, and the associated complexity surplus. The surplus was typically 15-30 times the standard deviation of the ER neutral network complexities.
<details>
<summary>Image 8 Details</summary>
### Visual Description
## Line Chart: Complexity vs. Surplus over Instruction Count
### Overview
The image is a 2D line chart plotting two variables, "complexity" and "surplus," against the number of instructions processed. The chart displays a time-series-like relationship where the x-axis represents a progression of work (instructions in billions) and the y-axis measures a quantity in "bits." The data shows significant volatility, particularly in the "complexity" series, with both series exhibiting a sharp decline towards the end of the observed range.
### Components/Axes
* **Chart Type:** Line chart with two data series.
* **X-Axis:**
* **Label:** `instructions (billions)`
* **Scale:** Linear, ranging from 0 to 100.
* **Major Tick Marks:** At intervals of 10 (0, 10, 20, ..., 100).
* **Y-Axis:**
* **Label:** `bits`
* **Scale:** Linear, ranging from 0 to 450.
* **Major Tick Marks:** At intervals of 50 (0, 50, 100, ..., 450).
* **Legend:**
* **Position:** Top-right corner of the plot area.
* **Series 1:** `complexity` - Represented by a solid red line.
* **Series 2:** `surplus` - Represented by a dashed green line.
### Detailed Analysis
The chart can be segmented into distinct phases based on the behavior of the two lines.
**1. Initial Phase (0 to ~65 billion instructions):**
* **Complexity (Red Line):** Exhibits high volatility. It starts high (approx. 400 bits at 0 instructions), drops sharply to a local minimum around 100-150 bits near 5 billion instructions, then enters a period of large, rapid oscillations. The values frequently spike above 300 bits and dip below 150 bits. The overall trend in this phase is a gradual, noisy increase, with the highest peak (approx. 450 bits) occurring around 45 billion instructions.
* **Surplus (Green Line):** Shows much lower magnitude and volatility compared to complexity. It starts around 100 bits, quickly drops to a range between approximately 25-75 bits, and remains within this band for the majority of this phase. Its fluctuations are smaller and less frequent than those of the complexity line.
**2. Transition and Drop Phase (~65 to ~70 billion instructions):**
* **Complexity:** Experiences a dramatic, sustained drop from its volatile range (200-350 bits) down to a much lower level, stabilizing around 50-100 bits by 70 billion instructions.
* **Surplus:** Also drops during this period, reaching its lowest point in the chart (near 0 bits) around 68 billion instructions.
**3. Secondary Volatility Phase (~70 to ~90 billion instructions):**
* **Complexity:** After the drop, it immediately rebounds into another period of high volatility, though the average level appears slightly lower than in the first phase. Values oscillate roughly between 150 and 350 bits.
* **Surplus:** Recovers from its low and enters its most active phase, showing larger spikes than before, with peaks reaching approximately 100-130 bits.
**4. Final Decline Phase (~90 to 100 billion instructions):**
* **Complexity:** Begins a final, steep decline from its volatile state, falling towards 0 bits as instructions approach 100 billion.
* **Surplus:** Similarly declines sharply from its last peak, also trending towards 0 bits at the end of the chart.
### Key Observations
1. **Magnitude Disparity:** The "complexity" value is consistently and significantly higher than the "surplus" value throughout almost the entire chart, except possibly at the very end where both approach zero.
2. **Volatility Correlation:** The periods of highest volatility in complexity (0-65B and 70-90B instructions) correspond to periods of relatively lower, but still present, volatility in surplus. The major drop in complexity (~65-70B) is mirrored by a drop in surplus.
3. **Synchronized Termination:** Both data series converge and decline sharply to near-zero values in the final segment (90-100B instructions), suggesting a common terminating event or condition.
4. **Anomalous Low Point:** The surplus line hits an extreme low (near 0 bits) around 68 billion instructions, which is a notable outlier within its own trend.
### Interpretation
This chart likely visualizes a computational or information-theoretic process. "Instructions (billions)" suggests a measure of computational work or steps executed. "Bits" is a unit of information, implying the y-axis measures some form of information content, capacity, or cost.
* **Relationship:** "Complexity" appears to be a primary, highly variable cost or state metric of the system, while "surplus" might represent a secondary, residual, or available capacity metric. The fact that surplus is lower and less volatile suggests it is a more constrained or derived quantity.
* **Process Phases:** The data tells a story of a system operating in a high-energy, volatile state (Phases 1 & 3), undergoing a significant state change or reset (Phase 2), and finally reaching a termination or exhaustion point (Phase 4). The sharp drop around 65-70 billion instructions is the most critical event in the timeline.
* **Underlying Phenomenon:** The patterns are characteristic of systems with phase transitions, resource depletion, or error-correction cycles. For example, it could represent the internal state of a machine learning model during training (complexity as loss, surplus as a buffer), a communication system under load, or a simulation reaching a conclusion. The final decline to zero for both metrics strongly indicates the completion of a defined task or the exhaustion of a resource pool at approximately 95-100 billion instructions.
</details>
(6). This is documented in the cmpERmodel.tcl script of ecolab.5.D1. The average and standard deviation of ln C was calculated, rather than C directly, as the shuffled complexity values fitted a log-normal distribution better than a standard normal distribution. The difference between the measured complexity and exp 〈 ln C〉 (ie the geometric mean of the control network complexities) is what is reported as the surplus in Figures 8-10.
## 9 ALife results
Figures 8-10 show the computed complexity values and the surplus of the complexity over the average randomly shuffled networks. In both the EcoLab and Tierra cases, significant amounts of surplus complexity can be observed, but not in the case of WebWorld. In WebWorld's case, this is probably because the system complexity was not very high in the first place - the diversity typically ranged between 5 and 10 species throughout the WebWorld run. It is possible that the competition parameter c was too high for this run to generate any appreciable foodweb complexity.
An earlier report of these results [37] did not show significant complexity,
Figure 9: Complexity of EcoLab's foodweb, and the associated complexity surplus. For most of the run, the surplus was 10-40 times the standard deviation of the ER neutral network complexities, but in the final complexity growth phase, it was several 100.
<details>
<summary>Image 9 Details</summary>
### Visual Description
## Line Chart: Complexity and Surplus Over Timesteps
### Overview
The image is a 2D line chart plotting two variables, "complexity" and "surplus," against time. The chart demonstrates a clear divergence between the two metrics over the observed period, with complexity exhibiting high volatility and a strong late-stage increase, while surplus remains relatively stable and low.
### Components/Axes
* **Chart Type:** Line chart with two data series.
* **X-Axis:**
* **Label:** `timesteps (thousands)`
* **Scale:** Linear, ranging from 0 to 1000.
* **Major Tick Marks:** Every 100 units (0, 100, 200, ..., 1000).
* **Y-Axis:**
* **Label:** `bits`
* **Scale:** Linear, ranging from 0 to 700.
* **Major Tick Marks:** Every 100 units (0, 100, 200, ..., 700).
* **Legend:**
* **Position:** Top-right corner of the plot area.
* **Series 1:** `complexity` - Represented by a solid red line.
* **Series 2:** `surplus` - Represented by a dashed green line.
### Detailed Analysis
**1. Complexity (Red Line):**
* **Visual Trend:** The line is highly volatile with frequent peaks and troughs. It shows a general, but non-monotonic, upward trend over the full range, with a dramatic acceleration in the final quarter of the timeline.
* **Key Data Points (Approximate):**
* **Start (0k timesteps):** ~50 bits.
* **First Major Peak (~100k):** ~250 bits.
* **Second Major Peak (~300k):** ~330 bits.
* **Period of Decline (~500k-600k):** Fluctuates between ~50 and ~150 bits.
* **Final Surge (~700k-900k):** Rises sharply from ~100 bits to a peak of approximately **600 bits** at ~880k timesteps, ending near ~580 bits at 900k.
**2. Surplus (Green Line):**
* **Visual Trend:** The line is much smoother and exhibits low volatility. It maintains a relatively flat, slightly positive trend throughout, staying within a narrow band.
* **Key Data Points (Approximate):**
* **Start (0k timesteps):** ~0 bits.
* **General Range:** Fluctuates primarily between **~20 and ~70 bits** for the entire duration.
* **End (900k timesteps):** ~60 bits.
### Key Observations
1. **Magnitude Divergence:** The value of "complexity" is consistently greater than "surplus" after the initial timesteps. The gap between them widens significantly after ~700k timesteps.
2. **Volatility Contrast:** Complexity is characterized by high-frequency, high-amplitude noise, while surplus shows low-frequency, low-amplitude variation.
3. **Correlation:** There is no obvious visual correlation between the short-term fluctuations of the two lines. Their long-term trends are both positive but at vastly different rates.
4. **Notable Outlier Event:** The period between 700k and 900k timesteps represents a regime change for the complexity metric, where it breaks from its previous oscillatory pattern and enters a steep, sustained climb.
### Interpretation
The chart suggests a system where the measured "complexity" (in bits) is dynamic and can undergo phases of rapid growth, while the "surplus" (also in bits) represents a more stable, slowly accruing resource or buffer.
* **What the Data Suggests:** The system may be undergoing a process where increasing complexity does not generate a proportional increase in surplus. The late-stage surge in complexity could indicate a phase transition, a runaway process, or the system reaching a new, more complex state of operation. The stable surplus might represent a fundamental capacity limit or a baseline resource that is largely independent of the system's operational complexity.
* **Relationship Between Elements:** The two metrics appear to be decoupled in the short term. The surplus does not react to the wild swings in complexity, implying it is governed by different underlying mechanisms or constraints.
* **Anomalies and Trends:** The most significant anomaly is the exponential-looking rise in complexity after 700k timesteps. This is the dominant feature of the chart and would be the primary focus for any technical investigation. The consistent, low-level nature of the surplus is the secondary key finding.
</details>
Figure 10: Complexity of Webworld's foodweb, and the associated complexity surplus. The surplus was typically 1-5 times the standard deviation of the ER neutral network complexities.
<details>
<summary>Image 10 Details</summary>
### Visual Description
## Line Chart: Complexity and Surplus Over Timesteps
### Overview
The image is a 2D line chart displaying two data series over a period of 100,000 timesteps. The chart plots the values of "complexity" and "surplus," measured in bits, against time. The overall visual impression is of a highly volatile red series ("complexity") with a general upward trend, contrasted with a much lower, less volatile green series ("surplus").
### Components/Axes
* **Chart Type:** Line chart with two data series.
* **X-Axis:**
* **Label:** `timesteps (thousands)`
* **Scale:** Linear, ranging from 0 to 100.
* **Major Tick Marks:** At intervals of 10 (0, 10, 20, ..., 100).
* **Y-Axis:**
* **Label:** `bits`
* **Scale:** Linear, ranging from 0 to 60.
* **Major Tick Marks:** At intervals of 10 (0, 10, 20, ..., 60).
* **Legend:**
* **Position:** Top-right corner of the chart area.
* **Series 1:** `complexity` - Represented by a solid red line.
* **Series 2:** `surplus` - Represented by a dashed green line.
### Detailed Analysis
**1. "complexity" (Red, Solid Line):**
* **Trend Verification:** The line exhibits high-frequency volatility throughout the entire range. Despite the noise, a clear, non-linear upward trend is visible. The value starts near 15 bits at timestep 0 and ends near 55 bits at timestep 100,000. The growth is not steady; it features periods of sharp increase, plateau, and even decline.
* **Key Data Points (Approximate):**
* Start (t=0): ~15 bits.
* First major peak: ~35 bits around t=5,000.
* Significant dip: Below 10 bits around t=12,000.
* High plateau region: Between t=35,000 and t=45,000, values fluctuate between ~25 and ~48 bits.
* Another major peak: ~50 bits around t=55,000.
* Notable decline: Drops to ~20 bits around t=80,000.
* Final surge: Rises sharply from ~25 bits at t=90,000 to its maximum of ~55 bits at t=100,000.
**2. "surplus" (Green, Dashed Line):**
* **Trend Verification:** This series remains at a much lower magnitude than complexity. It shows moderate volatility but with a much smaller amplitude. A slight upward trend becomes discernible in the final quarter of the timeline.
* **Key Data Points (Approximate):**
* Baseline: Fluctuates primarily between 0 and 5 bits for the first 80,000 timesteps.
* Minor peaks: Reaches ~7 bits around t=40,000 and t=55,000.
* Final trend: Begins a more sustained, gentle rise from approximately t=85,000, ending at its highest point of ~9 bits at t=100,000.
### Key Observations
1. **Magnitude Disparity:** The "complexity" values are consistently an order of magnitude larger than the "surplus" values. The gap between them widens over time.
2. **Correlation of Peaks:** Some peaks in the "surplus" series (e.g., around t=40k and t=55k) appear to coincide with local peaks or high-volatility periods in the "complexity" series, suggesting a potential weak positive correlation during those intervals.
3. **Volatility Contrast:** The "complexity" series is characterized by extreme, jagged volatility, while the "surplus" series, though noisy, has a smoother profile.
4. **Late-Stage Behavior:** Both series show their most pronounced upward movement in the final 10,000 timesteps (90k to 100k), with "complexity" surging dramatically and "surplus" reaching its peak.
### Interpretation
This chart likely visualizes metrics from a computational, biological, or information-theoretic model evolving over time. The "complexity" metric (in bits) appears to represent the amount of information or structural intricacy within the system. Its volatile yet upward trajectory suggests the system is undergoing a process of growth or learning, but in a non-smooth, potentially punctuated equilibrium fashion—where periods of rapid change alternate with consolidation.
The "surplus" metric, also in bits, could represent excess capacity, redundant information, or a resource buffer. Its consistently low value relative to complexity implies the system operates with minimal slack. The slight rise in surplus at the end, concurrent with the complexity surge, might indicate that the system is finally accumulating a small reserve as it reaches a higher state of organization, or that the process driving the final complexity increase also generates a small amount of incidental surplus.
The most significant takeaway is the **divergent scaling** of the two metrics. The system's complexity grows substantially, while its surplus does not keep pace. This could point to an efficient process where resources are tightly coupled to functional complexity, or conversely, to a system becoming increasingly "tight" and potentially fragile, with little excess capacity to handle perturbations. The late-stage rise in both could mark a phase transition or the culmination of a long-term evolutionary or learning process.
</details>
unlike what is shown here. It was discovered that the process of writing the foodweb data to an intermediate file stripped the weight data from the network links, preserving only the graph's topological structure. It turns out that the complexity surplus phenomenon is only present in weighted networks - unweighted networks tend to be indistinguishable from randomly generated networks.
## 10 Discussion
In this paper, a modified version of a previously proposed simple representation language for n -node directed graphs is given. This modification leads to a more intuitive complexity measure that gives a minimum value for empty and full networks. When compared with the zcomplexity measure introduced in the previous paper, it is somewhat correlated with, and is at least as good a measure as zcomplexity, but has the advantage of being far more tractable.
When compared with random networks created by shuffling the links, all real world example networks exhibited higher complexity than the random network. The difference between the complexity of the real network and the mean of the complexities of the randomly shuffled network represents structural information contained in the specific arrangement of links making up the network. To test the hypothesis that networks generated by evolutionary selection will also have a complexity surplus representing the functional nature of the network, I ran the same analysis on foodwebs generated by various artificial life systems. These too, exhibited the same complexity surplus seen in the real world networks.
By contrast, I have applied this technique to some scale free networks generated by the Barab´ asi-Albert preferential attachment process [4], with varying numbers of attachment points per node and different weight distributions. On none of these graphs were significant complexity surpluses generated.
If the weights are stripped off the edges, then the effect disappears, which provides a clue as to the origin of the effect. In equation (6), the components dominating the sum will tend to be connected giant components of the overall network with very few cycles. The randomly shuffled versions of these, however, will tend to be composed of small disconnected components, with many of the same motifs represented over and over again. Consequently, the shuffled network has a great deal of symmetry, reducing the overall complexity. Even though naively one might think that random networks should be the most complex within the class of networks of a given node and link count, given the nature of Kolmogorov complexity to favour random strings, the weighted complexity formula (6) is sensitive to the structure within the network that has meaning to system behaviour that the network represents.
Reverting to an earlier posed question about the amount of complexity stored within the foodweb as compared with individual organism's phenotypic complexity, the results in Figure 8 gives a preliminary answer. Each foodweb in Figure 8 averaged around 100 species, the average phenotypic complexity of which is around 150-200 bits (750 bits at maximum)[33]. So the 250-400 bits of network complexity is but a drop in the bucket of phenotypic complexity.
## References
- [1] Almunia, J., Basterretxea, G., Aristegui, J., and Ulanowicz., R. (1999) Benthicpelagic switching in a coastal subtropical lagoon. Estuarine, Coastal and Shelf Science , 49 , 363-384.
- [2] Baird, D., Luczkovich, J., and Christian, R. R. (1998) Assessment of spatial and temporal variability in ecosystem attributes of the St Marks National Wildlife Refuge, Apalachee Bay, Florida. Estuarine, Coastal, and Shelf Science , 47 , 329-349.
- [3] Baird, D. and Ulanowicz, R. (1989) The seasonal dynamics of the Chesapeake Bay ecosystem. Ecological Monographs , 59 , 329-364.
- [4] Barab´ asi, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science , 286 , 509-512.
- [5] Bedau, M. A., McCaskill, J. S., Packard, N. H., Rasmussen, S., Adami, C., Green, D. G., Ikegami, T., Kaneko, K., and Ray, T. S. (2000) Open problems in artificial life. Artificial Life , 6 , 363-376.
- [6] Caldarelli, G., Higgs, P. G., and McKane, A. J. (1998) Modelling coevolution in multispecies communities. J. Theor, Biol. , 193 , 345-358.
- [7] Christian, R. and Luczkovich, J. (1999) Organizing and understanding a winter's seagrass foodweb network through effective trophic levels. Ecological Modelling , 117 , 99-124.
- [8] Clauset, A., Shalizi, C. R., and Newman, M. E. J. (2009) Power-law distributions in empirical data. SIAM Review , 51 , 661-703, arXiv:0706.1062.
- [9] Claussen, J. C. (2007) Offdiagonal complexity: A computationally quick complexity measure for graphs and networks. Physica A , 375 , 365-373, arXiv:q-bio.MN/0410024.
- [10] Dewar, R. (2003) Informational theory explanation of the fluctuation theorem, maximum entropy production and self-organized criticality in nonequilibrium stationary states. J. Phys. A , 36 , 631-641.
- [11] Dorin, A. and Korb, K. B. (2010) Network measures of ecosystem complexity. Fellerman et al. [15], pp. 323-328.
- [12] Drossel, B., Higgs, P. G., and McKane, A. J. (2001) The influence of predator-prey population dynamics on the long-term evolution of food web structure. J. Theor. Biol. , 208 , 91-107.
- [13] Duch, J. and Arenas, A. (2005) Community identification using extremal optimization. Physical Review E , 72 , 027104.
- [14] Edmonds, B. (1999) Syntactic Measures of Complexity . Ph.D. thesis, University of Manchester, http://bruce.edmonds.name/thesis/, Complexity Bibliography: http://bruce.edmonds.name/compbib/.
- [15] Fellerman, H. et al. (eds.) (2010) Proceedings of Artificial Life XII , MIT Press.
- [16] G¨ ornerup, O. and Crutchfield, J. P. (2008) Hierarchical self-organization in the finitary process soup. Artificial Life , 14 , 245-254.
- [17] Hagy, J. (2002) Eutrophication, hypoxia and trophic transfer efficiency in Chesapeake Bay . Ph.D. thesis, University of Maryland at College Park (USA).
- [18] Jeong, H., Mason, S., Barab´ asi, A.-L., and Oltvai, Z. N. (2001) Centrality and lethality of protein networks. Nature , 411 , 41.
- [19] Kim, J. and Wilhelm, T. (2008) What is a complex graph. Physica A , 387 , 2637-2652.
- [20] Knuth, D. E. (1993) The Stanford GraphBase: A Platform for Combinatorial Computing . Addison-Wesley.
- [21] Layzer, D. (1988) Growth and order in the universe. Weber, B. H., Depew, D. J., and Smith, J. D. (eds.), Entropy, Information and Evolution , pp. 23-39, MIT Press.
- [22] Li, M. and Vit´ anyi, P. (1997) An Introduction to Kolmogorov Complexity and its Applications . Springer, 2nd edn.
- [23] McKay, B. D. (1981) Practical graph isomorphism. Congressus Numerantium , 30 , 45-87.
- [24] Monaco, M. and Ulanowicz, R. (1997) Comparative ecosystem trophic structure of three U.S. Mid-Atlantic estuaries. Mar. Ecol. Prog. Ser. , 161 , 239-254.
- [25] Myrvold, W. and Ruskey, F. (2001) Ranking and unranking permutations in linear time. Information Processing Letters , 79 , 281-284.
- [26] Newman, M. E. J. (2006) Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E , 74 , 036104.
- [27] Prigogine, I. (1980) From Being into Becoming . W.H. Freeman.
- [28] Prokopenko, M., Boschetti, F., and Ryan, A. J. (2009) An informationtheoretic primer on complexity, self-organization, and emergence. Complexity , 15 , 11-28.
- [29] Ray, T. (1991) An approach to the synthesis of life. Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S. (eds.), Artificial Life II , p. 371, Addison-Wesley.
- [30] Standish, R. K. (2000) The role of innovation within economics. Barnett, W., Chiarella, C., Keen, S., Marks, R., and Schnabl, H. (eds.), Commerce, Complexity and Evolution , vol. 11 of International Symposia in Economic Theory and Econometrics , pp. 61-79, Cambridge UP.
- [31] Standish, R. K. (1994) Population models with random embryologies as a paradigm for evolution. Complexity International , 2 .
- [32] Standish, R. K. (2001) On complexity and emergence. Complexity International , 9 , arXiv:nlin.AO/0101006.
- [33] Standish, R. K. (2003) Open-ended artificial evolution. International Journal of Computational Intelligence and Applications , 3 , 167, arXiv:nlin.AO/0210027.
- [34] Standish, R. K. (2004) Ecolab, Webworld and self-organisation. Pollack et al. (eds.), Artificial Life IX , Cambridge, MA, p. 358, MIT Press.
- [35] Standish, R. K. (2004) The influence of parsimony and randomness on complexity growth in Tierra. Bedau et al. (eds.), ALife IX Workshop and Tutorial Proceedings , pp. 51-55, arXiv:nlin.AO/0604026.
- [36] Standish, R. K. (2005) Complexity of networks. Abbass et al. (eds.), Recent Advances in Artificial Life , Singapore, vol. 3 of Advances in Natural Computation , pp. 253-263, World Scientific, arXiv:cs.IT/0508075.
- [37] Standish, R. K. (2010) Network complexity of foodwebs. Fellerman et al. [15], pp. 337-343.
- [38] Standish, R. K. (2010) SuperNOVA: a novel algorithm for graph automorphism calculations. Journal of Algorithms - Algorithms in Cognition, Informatics and Logic , submitted, arXix: 0905.3927.
- [39] Ulanowicz, R., Bondavalli, C., and Egnotovich, M. (1998) Network analysis of trophic dynamics in South Florida ecosystem, FY 97: The Florida Bay ecosystem. Tech. rep., Chesapeake Biological Laboratory, Solomons, MD 20688-0038 USA, [UMCES]CBL 98-123.
- [40] Ulanowicz, R., Heymans, J., and Egnotovich., M. (2000) Network analysis of trophic dynamics in South Florida ecosystems, FY 99: The graminoid ecosystem. Tech. rep., Chesapeake Biological Laboratory, Solomons, MD 20688-0038 USA, [UMCES] CBL 00-0176.
- [41] Watts, D. J. and Strogatz, S. H. (1998) Collective dynamics of 'small-world' networks. Nature , 393 , 409-10.
- [42] Wilhelm, T. and Hollunder, J. (2007) Information theoretic description of networks. Physica A , 385 , 385-396.
Table 1: Complexity values of several freely available network datasets. celegansneural, lesmis and adjnoun are available from Mark Newman's website, representing the neural network of the C. elegans nematode[41], the coappearance of characters in the novel Les Mis´ erables by Victor Hugo[20] and the adjacency network of common adjectives and nouns in the novel David Copperfield by Charles Dickens[26]. The metabolic data of C. elegans [13] and protein interaction network in yeast[18] are available from Duncan Watt's website. PA1 and PA3 are networks generated via preferential attachment with in degree of one or three respectively, and uniformly distributed link weights. The other datasets are food webs available from the Pajek website [7, 39, 40, 17, 2, 1, 3]. For each network, the number of nodes and links are given, along with the computed complexity C . In the fourth column, the original network is shuffled 1000 times, and the logarithm of the complexity is averaged ( 〈 ln C ER 〉 ). The fifth column gives the difference between these two values, which represents the information content of the specific arrangement of links. The final column gives a measure of the significance of this difference in terms of the number of standard deviations ('sigmas') of the distribution of shuffled networks. In two examples, the distributions of shuffled networks had zero standard deviation, so ∞ appears in this column.
| Dataset | nodes | links | C | e 〈 ln C ER 〉 | C - e 〈 ln C ER 〉 | | ln C-〈 ln C ER 〉| σ ER |
|-------------------|---------|---------|---------|-----------------|---------------------|--------------------------------------|
| celegansneural | 297 | 2345 | 442.7 | 251.6 | 191.1 | 29 |
| lesmis | 77 | 508 | 199.7 | 114.2 | 85.4 | 24 |
| adjnoun | 112 | 850 | 3891 | 3890 | 0.98 | ∞ |
| yeast | 2112 | 4406 | 33500.6 | 30218.2 | 3282.4 | 113.0 |
| celegansmetabolic | 453 | 4050 | 25421.8 | 25387.2 | 34.6 | ∞ |
| baydry | 128 | 2138 | 126.6 | 54.2 | 72.3 | 22 |
| baywet | 128 | 2107 | 128.3 | 51 | 77.3 | 20 |
| cypdry | 71 | 641 | 85.7 | 44.1 | 41.5 | 13 |
| cypwet | 71 | 632 | 87.4 | 42.3 | 45 | 14 |
| gramdry | 69 | 911 | 47.4 | 31.6 | 15.8 | 10 |
| gramwet | 69 | 912 | 54.5 | 32.7 | 21.8 | 12 |
| Chesapeake | 39 | 177 | 66.8 | 45.7 | 21.1 | 10.4 |
| ChesLower | 37 | 178 | 82.1 | 62.5 | 19.6 | 10.6 |
| ChesMiddle | 37 | 208 | 65.2 | 48 | 17.3 | 9.3 |
| ChesUpper | 37 | 215 | 81.8 | 60.7 | 21.1 | 10.2 |
| CrystalC | 24 | 126 | 31.1 | 24.2 | 6.9 | 6.4 |
| CrystalD | 24 | 100 | 31.3 | 24.2 | 7 | 6.2 |
| Everglades | 69 | 912 | 54.5 | 32.7 | 21.8 | 11.8 |
| Florida | 128 | 2107 | 128.4 | 51 | 77.3 | 20.1 |
| Maspalomas | 24 | 83 | 70.3 | 61.7 | 8.6 | 5.3 |
| Michigan | 39 | 219 | 47.6 | 33.7 | 14 | 9.5 |
| Mondego | 46 | 393 | 45.2 | 32.2 | 13 | 10.0 |
| Narragan | 35 | 219 | 58.2 | 39.6 | 18.6 | 11.0 |
| Rhode | 19 | 54 | 36.3 | 30.3 | 6 | 5.3 |
| StMarks | 54 | 354 | 110.8 | 73.6 | 37.2 | 16.0 |
| PA1 | 100 | 99 | 98.9 | 85.4 | 13.5 | 2.5 |
| PA3 | 100 | 177 | 225.9 | 207.3 | 18.6 | 3.0 |