Foundations  (F) Session 2

Abstract: The Game of Life (LIFE), one of the two dimensional cellular automata, exhibits 1/f noise in the evolution starting from random configuration. 1/f noise has the power inversely proportional to frequency, that is, the exponent of the power spectrum is about -1. On the other hand, LIFE is capable of supporting universal computation. Considering these results together we can guess that there is a relationship between computational universality and 1/f noise in cellular automata. However the power spectrum of the computation process in which Turing machine is emulated on the array of LIFE has the exponent -0.3, that is not considered to be 1/f noise. In this research we conduct spectral analysis of the behavior of another computation model called universal register machine (URM) on the array of LIFE. Register machine is an abstract model of computer with a set of registers. Each register is of infinite extent and can hold any single non-negative integer. Universal register machine (URM) is a register machine that can imitate the computation process of any register machines. The first embodiment of URM on LIFE was accomplished by Chapman although we use the other one developed by Rendell (http://rendell-attic.org/gol/UCM/CMappNotes.html). The pattern of the URM is about 19,000 * 3,900 cells on the array and it takes about 32,586,000 time steps to halt. We calculate the power spectrum of the upper part of the pattern of URM with the array size of height * width = 3000 * 3800 = 11,400,000 cells over 65,536 time steps. As a result, the exponent of the power in the range between f = 1 .. 100 is about -1.5. This result shows that the power spectra of the computation process in LIFE vary according to its model and it contrasts clearly with the process starting from random configuration. Close

Abstract: Missing data is an issue ubiquitous in applied science. In the context of temporal networks, loss of data may correspond to missing contacts or missing node activities. In some cases, other data sources containing related information which can be used for data recovery are available. However, combining information from different sources is challenging. Here, we propose a technique based on joint factorization (Evrim et al., 2011) to recover missing activity in temporal networks. Each data source is encoded in a tensor. Assuming that there exists some correlation between the data from the multiple sources, a joint factorization of the tensors allows to infer missing information in one tensor from the others. We illustrate this method on an empirical contact network in which we simulated loss of data for the 10% of nodes by removing their activity for half the time span of the dataset. The resulting network was represented as a tensor where each slice gives the contacts of the nodes at a given time. In addition to the contact network, we have access to the location of the nodes with time. We built a second tensor where each slice gives the position of the nodes at a given time. We jointly factorized the two tensors, with a method handling missing values. Regularization terms were added to control the level of correlation between the contact network and the location network. We evaluated the correlation between the temporal activity of the nodes in the original network and in the recovered one over the missing period and found a good agreement. This suggests that our approach is an efficient method for recovering missing data for temporal networks. Moreover, it generalizes easily to more than two data sources which could all contain missing data. Close

Abstract: The introduction of multilayer neteorks poses the theoretical question of whether critical phenomena will behave differently on such networks with respect to traditional networks. So far theoretical studies have pointed out that such differences in the critical behaviours indeed exists. It has been showed that a multiplex network can exists in different structural phases, the transition among them being abrupt under some conditions. Three different topological scales can be naturally identified in a multiplex: that of the individual layers, that of the network of layers, and that of the aggregate network. The notion of quotient graph gives the connection between those scales in therms of spectral properties of the parent multiplex network an its aggregate representation. Much attention was paid to the coupling parameter p that weights the coupling between different representatives of the same node in different layers. It exists a value p∗ for which the derivative of the algebraic connectivity (the first non-zero eigenvalue of the supra-Laplacian) shows a discontinuity. At this point the Fiedler vector also changes abruptly and the Fiedler cut, that before p∗ only intercepts inter-layer edges, starts to intercepts intra-layer edges. We show that the same transition can be triggered by a completely different mechanism that we call layer degradation. Just acting on a single layer at a fixed p by removing intra-layer edges or tuning the weight of these, the multiplex undergoes to the same transition. Working on an approximation of the algebraic connectivity, we give an analytical description of the transition and its dependency on the value of p and on the value of the algebraic connectivities of isolated layers. We also study the transition numerically and the behaviour of the Shannon entropy of the Fiedler vector during the process, since one can interpret (a function of) this as an order parameter. Close

Abstract: It is intuitive to assume that differences in growth among diverse parts change the constitution of the population as a whole. The larger the differences, the faster the change. Fisher’s fundamental theorem of natural selection formalizes this idea. Counterintuitively, this article shows that large fitness differentials make it likely more beneficial to stop evolutionary selection by stabilizing population structure through informed intervention (i.e. bet-hedging). The larger the differences of fitness among types, the more likely it is that it pays of to hold the shares of type constant by counteracting natural selection. This possibility of such interventions depends on the availability of information about the environmental pattern. With information growth can be optimized through resource redistribution. Information is the key ingredient in order to be able to hedge ones bets and actively manage a portfolio in an uncertain environment. We treat information formally in terms of information theory, including Shannon’s absolute entropy and Kullback-Leibler’s relative entropy. The policy mechanism to convert information into growth is structural adjustment. An empirical analysis over nine levels of an international trade taxonomy shows that is more likely beneficial to intervene on more fine-grained levels, while blind natural selection is likely to optimize growth on more aggregate levels. Close

Abstract: The concept of Computational Irreducibility is formally defined in a rigorous way inside the computational model of Turing machines supplemented with a new kind of machines, the E-Turing machines (for enumerating Turing machine). This helps understanding the behavior of some cellular automata which seem apparently impredictible. Computational Irreducibilty is also mobilized to give an explanation to the concept of Emergence. Close