The apparent disconnection between the microscopic and the macroscopic is a major issue in the understanding of complex systems. To this extend, we study the convergence of repeatedly applying local rules on a network, and touch on the expressive power of this model. We look at network systems and study their behavior when different types of local rules are applied on them. For a very general class of local rules, we prove convergence and provide a certain member of this class that, when applied on a graph, efficiently computes its k-core and its (k-1)-crust giving hints on the expressive power of such a model. Furthermore, we provide guarantees on the speed of convergence for an important subclass of the aforementioned class. We also study more general rules, and show that they do not converge. Our counterexamples resolve an open question of (Zhang, Wang, Wang, Zhou, KDD- 2009) as well, concerning whether a certain process converges. Finally, we show the universality of our network system, by providing a local rule under which it is Turing-Complete.
@cite_5: In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been lacking even in the simplest of instances. Our first result is an interpretation of the dynamics as an optimization process. We show that Physarum dynamics can be seen as a steepest-descent type algorithm on a certain Riemannian manifold. Moreover, we prove that the trajectories of Physarum are in fact paths of optimizers to a parametrized family of convex programs, in which the objective is a linear cost function regularized by an entropy barrier. Subsequently, we rigorously establish several important properties of solution curves of Physarum. We prove global existence of such solutions and show that they have limits, being optimal solutions of the underlying LP. Finally, we show that the discretization of the Physarum dynamics is efficient for a class of linear programs, which include unimodular constraint matrices. Thus, together, our results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.
@cite_11: A key problem in the study and design of complex systems is the apparent disconnection between the microscopic and the macroscopic. It is not straightforward to identify the local interactions that give rise to an observed global phenomenon, nor is it simple to design a system that will exhibit some desired global property using only local knowledge. Here we propose a methodology that allows for the identification of local interactions that give rise to a desired global property of a network, the degree distribution. Given a set of observable processes acting on a network, we determine the conditions that must be satisfied to generate a desired steady-state degree distribution. We thereby provide a simple example for a class of tasks where a system can be designed to self-organize to a given state.
Except for the analysis of such complex systems, there are some important results on the design of local rules that give rise to a desired global behaviour. @cite_11 designed local rules that allow a network to reach a desired steady-state degree distribution, while proposed a global-to-local design methodology to compose heterogeneous swarms for self-organized task allocation @cite_5 .