The spontaneous emergence of computation in network cascades

We first experiment on the LTM, to study the observed frequency of Boolean functions in simulation. We have created networks with (N = 10000) knots and (k = 2) starters, in a range of medium degree (z = [0, frac{1}{2}, 1, 2, 4, 8, 16, 64, 256, 1024, 4096, 10000])more than 10000 tests for each z assess. In the middle degree (z = 4), soon after the emergence of the GCC, we observed that the frequency of features is highly asymmetric (Fig. 3a). Experiences for (k = 4) entries, again for (N = 10000) medium degree knots (z = 4), clustered over 500 realizations, also give an approximate exponential decay of the ranking function (Fig. 3b). (See Supplementary Information A.4.)

We study the asymmetric distribution of these functions by setting “What is the probability of obtaining the simplest network to calculate each of these functions?. From (Fig. 1), we can deduce the probability of each monotonic function. For example, if there is no path from the starting nodes a and b at a knot you we obtain (f_0)So

$$begin{aligned} p(f_0) propto (1 – p_{path})^2, end{aligned}$$

where (p_{path}) is the probability of a path between two randomly chosen nodes.

Function (f_1) requires paths from a and b at youSo

$$begin{aligned} p(f_1) propto p_{path}^2. end{aligned}$$


However, keeping percolation in mind, we observe that for large graphs, the probability of paths between not nodes approximates the probability that all not the nodes belong to the giant connected component (GCC)25.37.

This gives us, again from (Fig. 1),

$$begin{aligned} p(f_1) propto p_{path(a,b,u)} propto p_{gcc}^3, end{aligned}$$

where (p_{gcc}) is the probability for a random node to belong to the GCC.

let’s define (v = P_{gcc}). Of37we know that v is given implicitly by the following relation

$$begin{aligned} v = 1 – e^{-zv}, end{aligned}$$


where z is the average degree. (See Supplementary Information A.3 for more information.)

We then observe that the number of paths required from the starting nodes to the node youwhich calculates the monotone function Fis equal to decision tree complexity (VS), the depth of the shortest decision tree to compute F. In order to you to decide the value of a seed node, seed disturbance information must be passed along a path to you.

Taking the Hamming cube representation of a Boolean function, the complexity of its decision tree VS is complementary to the number of congruent axial reflections R along each of its axes D (details in additional information A.1). That is, if the Hamming cube of a Boolean function is constant along an axis, it is independent of that axis, which gives us

$$begin{aligned} C = D – R. end{aligned}$$


In other words, the number of paths required by a monotone Boolean function is exactly the number of axial reflection asymmetries of its Hamming cube. This allows us to relate the symmetry of a function to the complexity of the decision tree and then to its frequency. Recall that the critical percolation threshold in an arbitrarily large Erdos-Renyi-Gilbert graph occurs at the critical mean degree (z_c = 1), a very small connection. Since (p_c = frac{z_c}{N-1})critical connection probability (p_c ll 1). Therefore, the network will contain a GCC and remain treelike even for a substantial mean degree above (z_c = 1)since the clustering coefficient (C_{mathrm{clus}} environ p)25. (for example for (N=10000) and (z = 10), (C_{clus} about 1/1000).) In a tree, the number of nodes is one more than the number of edges (N = |E| + 1). Thus, as (p ​​right arrow p_c),

$$begin{aligned} p(f) propto p_{gcc}^{C(f) + 1}. end{aligned}$$


Indeed it appears that Eq. (4) is strongly correlated with the probabilities derived from the logical patterns Eq. (1), and that the frequency of the observed function is proportional to Eq. (4) also (Fig. 3a), having a Pearson correlation of about 1.0 for k=2 and 0.74 for k=4. This also shows, due to Eq. (4) an inverse ranking relationship between frequency and complexity of the decision tree, appearing as a decreasing exponential frequency. Since, as mentioned in the introduction, there is an exponentially increasing distribution of decision tree complexity in the truth table of all Boolean functions, this result is particularly surprising.

Division of functions with antagonism

A similar simulation, having (N = 10000) knots, (k = 2) inputs, aggregated over 500 trials in a range of mean degree values z and fraction of antagonistic nodes (theta in {0, frac{1}{6}, frac{2}{6},… 1})reveals a sudden increase in the number of non-zero unique functions compared to the two z and (theta ) (Fig. 4a). The number of unique functions is maximized over several orders of magnitude near criticality, for (z in [2^3, 2^{10})]and (theta = 1/3). Observing that antagonism and inhibition are interchangeable12 (Additional information A.2), this allows optimal processing of information around (30 %) inhibition, found in other research38and why this fraction of inhibitory neurons seems to be biologically prevalent.

Figure 4

Antagonism fraction ((theta )) agrees with biology; non-monotonic functions also predicted by path requirements. (a) For networks with (N = 10000) knots and (k = 2) entries, more than 500 achievements, varying the average degree z and fraction of antagonistic nodes (theta in {0, frac{1}{6}, frac{2}{6},ldots 1})we observe that the average number of unique functions per network is maximized over several orders of magnitude ((zin [2^3, 2^{10}])) by networks having a fraction of antagonistic nodes (theta = frac{1}{3}) (triangles), coinciding with other findings38. (b) TO (theta = frac{1}{3}) and (z = 2^6), we again observe an asymmetric frequency and a proportional relationship between the frequency of the function and the probability due to the complexity Eq. (4), with a Pearson correlation of 0.91. The shaded region is one standard deviation. The probabilities were centered and normalized. (Functions (f_0) and (f_{15}) have been removed, as in the ALTM they can occur outside of the GCC).

Figure 5
number 5

Patterns for non-monotonic functions. The simplest logical patterns to calculate non-monotonic Boolean functions ({f_2), (f_4), (f_6}) (Table 1) in the ALTM at random node youon the starting nodes a, b. The dotted lines represent paths and the dotted nodes are antagonists. Functions (f_{13}), (f_{11})and (f_9) are negations of these, respectively, therefore have very similar networks, negating each node.

For this mix of LTM and ALTM nodes, we again see a similar ranking of functions, here at (z = 64, theta = 1/3)and that, as in the LTM, the frequency is again proportional to the probability derived from the complexity of the function (Fig. 4b), with a Pearson correlation of 0.91.

Note, however, that Eq. (3) underestimates the number of paths required for non-monotonic functions. For instance, (f_6) (XOR) requires 6 paths between 5 nodes, all of which must be in the GCC (Fig. 5), so that (p(f_6) propto p_{gcc}^5). However, the complexity of the decision tree of this function (C = 2), predicting by Eq. (4) that (p(f_6) propto p_{gcc}^3). Therefore, a more informative complexity measure is needed for non-monotonic functions.

Sharon D. Cole