Emergent Algorithms and Network Dynamics
Institut Henri-Poincaré, Paris, October 10-11, 2018
The main theme of the workshop is programming local interaction dynamics on networks, so as to obtain the desired emergent effects on the system as a whole. Central topics include:
- Evolving graph models and dynamics on random graphs
- Bio-inspired computing and computing with biological agents
- Chemical reaction networks
- Markovian and non-Markovian processes on networks.
Dana Randall (Georgia Tech)
Vincenzo Bonifaci (Rome, IASI-CNR)
Damien Woods (Dublin, Maynooth University)
Alfonso Jaramillo (Warwick, Jaramillo Lab)
Thomas Sauerwald (Cambridge)
Colin Cooper (London, King's College)
Amaury Pouly (Saarbrücken, MPII)
Benjamin Doerr (Paris Saclay, LIX - Ecole Polytechnique)
Nicolas Behr (Paris, IRIF - CNRS, Paris Diderot)
Vincent Cohen-Addad (Paris, LIP6 - CNRS, Sorbonne)
Amos Korman (Paris, IRIF - CNRS, Paris Diderot)
Florent Krzakala (Paris, LPS - ENS)
Laurent Massoulie (Paris, Microsoft Research - Inria)
Nastassia Pouradier Duteil (Paris, LJLL - Inria, CNRS, UPMC)
Guilhem Semerjian (Paris, LPT - ENS)
Speakers ordered by decreasing distance from Paris. A poster is available for printing.
Wednesday, October 10
[9am - 10.30am] Bio-inspired Computing
Vincenzo Bonifaci [slides]: The Network Dynamics of Physarum polycephalum: From Fluid Transport Optimization to Linear Programming
We review models for the network dynamics arising in the physiology of the slime mold Physarum polycephalum, an acellular organism that has been experimentally observed to form efficient adaptive networks. A model based on network flows and edge response functions was proposed in 2007 by mathematical biologists. We review this model and its emergent properties, together with artificial variants of the model that were later proposed by computer scientists as a means to solve linear programming problems. We show that the resulting dynamics are computationally efficient in several settings. Finally, we point out some challenges regarding the understanding of the process at the scale of flow particles, or in the case of more than two flow terminals.
Amos Korman: Limitations on Information Dissemination via Noisy Communication and Implications to Animal Group Behavior
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population.
In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL communication model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise.
We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis niger desert ants.
[11am - 12.30pm] Graph Dynamics
Florent Krzakala: From message passing to spectral algorithms
Laurent Massoulie: Rapid Mixing of Local Graph Dynamics
Graph dynamics arise naturally in many contexts. For instance in peer-to-peer networks, a participating peer may replace an existing connection with one neighbour by a new connection with a neighbour's neighbour. Several such local rewiring rules have been proposed to ensure that peer-to-peer networks achieve good connectivity properties (e.g. high expansion) in equilibrium. However it has remained an open question whether there existed such rules that also led to fast convergence to equilibrium. In this work we provide an affirmative answer: We exhibit a local rewiring rule that converges to equilibrium after each participating node has undergone only a number of rewirings that is poly-logarithmic in the system size. The proof involves consideration of the whole isoperimetric profile of the graph, and may be of independent interest.
[12.30pm - 2pm] Lunch buffet (at IHP)
[2pm - 3.30pm] Random Graphs and Clusters
Vincent Cohen-Addad [slides]: Hierarchical clustering: Objective functions and algorithms
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good’ hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties.
We take an axiomatic approach to defining `good’ objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of “admissible” objective functions (that includes the one of Dasgupta) that have the property that when the input admits a `natural’ hierarchical clustering, it has an optimal value.
Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an O(log^1.5 n)-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an O(log^0.5 n)-approximation (a result also independently shown by Charikar and Chatziafratis). This improves upon the LP-based O(log n)-approx. of Roy and Pokutta.
For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approximation, and provide a simple and better algorithm that gives a factor 1.5 approximation.
Finally, we consider `beyond-worst-case’ scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta’s cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.
Guilhem Semerjian [slides]: Optimization Problems for Structural and Dynamical Properties of Random Graphs
Many real-world systems are described as graphs, with vertices representing individuals and edges the connections between them. Depending on the context the connectivity of the graph can be an asset (in a transportation system, or in an electrical network) or a liability (as it favors the spreading of epidemics). One can study the modifications of the properties of a graph when some vertices are removed; when they are chosen randomly this is nothing but the classical percolation theory and its variants as bootstrap percolation. It is also possible to look for non-random, optimal choices of these vertices, and ask for instance: what is the minimal number of vertices to be removed from a graph in order to destroy its percolating cluster? In this talk I will discuss this type of questions in the context of random graphs and present results obtained by statistical mechanics methods.
[4pm-5.30pm] Mathematics of Chemical Reactions
Amaury Pouly [slides]: Strong Turing Completeness of Continuous Chemical Reaction Networks
In this talk, I will present some recent results on the Turing compleness of continuous chemical reaction networks (CRNs). We will see the link between these results and recent advances in the theory of analog computability and complexity. In particular, we will see how CRNs relate to the General Purpose Analog Computer (GPAC), a continuous-time analog model introduced by Claude Shannon in 1941. The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. I will then discuss the limit of this equivalence when it comes to biological implementations and highlight the crucial importance of robustness when designing CRNs.
Nicolas Behr: Combinatorial Conversion and Moment Bisimulation for Stochastic Rewriting Systems
Aimed at applications of our recently developed rule algebra framework to the study of complex systems, we introduce two novel concepts. Consider a complex system specified in the form of a stochastic rewriting system, in terms of its state space, its initial state and its possible random transitions. Our combinatorial conversion theorem allows to compute for each chosen set of observables of the system an evolution equation for the exponential generating function (EGF) of the statistical moments of these observables. Thus, our theorem permits to convert the problem of analyzing the evolution of the complex system to a problem in the realm of generating functions.
As a second novel concept, we introduce the notion of moment bisimulation, which defines two complex systems to be behaviorally equivalent with respect to two sets of observables (one set per system) if their moment EGF evolution equations agree. The concept will be illustrated in terms of a complete characterization of the bisimilarity class of chemical reaction systems via a standard choice of observables. We conclude with an example of a network model which, for a certain choice of observables, falls within this bisimilarity class.
Thursday, October 11
[9am-10am] Emergent Algorithms
Dana Randall: Phase transitions in programmable active matter
We consider stochastic solutions to problems arising from programmable active matter based on emergent phenomena. We view active matter as a collection of simple computational elements (or particles) with limited memory that self-organize to solve system-wide problems of movement, configuration, and coordination. First, we present a solution to the compression problem, which aims to have the particle system gather as tightly together as possible through a distributed, local, and asynchronous algorithms. We show that under the geometric amoebot model, we can achieve compression whenever we start with a particle system that is simply connected. We also present a stochastic solution to the separation problem, in which heterogenous (colored) particles interact initially without bias, but separate into homogeneous clusters in the presence of new environmental conditions.
[10.30am-12pm] Computing with Bio-molecules
Damien Woods: Molecular computation with DNA self-assembly
The field of algorithmic self-assembly is concerned with the theory and practice of having molecules stick together to grow computational structures in an autonomous bottom-up fashion. Theoretical work focuses on characterising the computational expressiveness of self-assembly models. Practice is concerned with using molecules, such as DNA, to implement algorithmic self-assembly programs in the wet-lab. The presentation will cover both topics. First, there will be an introduction to what it means to compute during a self-assembly process, an overview of some computational models, as well as basic mathematical results. We will then cover some of our latest results on implementing Boolean circuits via self-assembly.
Alfonso Jaramillo: Computation in living cells using RNA logic gates
Living entities process information in very different ways than existing human-made object as the former excel at having a built-in capability for self-reproduction, self-construction, evolvability, self-organization, scalability, adaptability and robustness. They can store information in DNA or epigenetically, although the former case is more tractable, and hence exploitable, by current technology. The machinery of living cells allows expressing functional biomolecules encoded in DNA. Such biomolecules can further switch the expression of selected genes, progressing asynchronously through successive reaction steps. We propose a strategy for the design of logic gates in living cells that relies on the expression of exogenous RNA as biomolecules. The RNA has biophysical properties that allow engineering of complex logical devices by predicting the alternative conformations the RNA may adopt when interact with other RNA or small-molecules. Moreover, the devices can be connected once the RNA controls the expression of other RNAs. For this, we developed a methodology based on physical principles to automatically design RNA components able to transduce environmental signals into RNA, process the RNA throughout cascades of RNA interactions to eventually regulate gene expression in cells. The gates implement logic gates, RNA cascades and RNA-controlled RNA switches. Our RNAs are different to any known non-coding sequence and their predicted behavior is validated in living E. coli at the population and single-cell levels. Moreover, we have developed switchable CRISPR/Cas9 guide RNAs able to sense RNAs and whole transcripts in vivo, which will allow the de novo design of sensors for the cell-cycle phase or the tissue type in eukaryotic cells. Our RNAs could empower cells with a ‘Virtual Machine’, able to interpret a universal RNA language, allowing engineering networks of molecular switches that could be made to process arbitrary orders encoded in RNA.
[12pm - 2pm] Lunch on your own (see a selection of restaurants)
[2pm - 3.30pm]: Particles in Graphs
Colin Cooper [slides]: Dispersion Processes
We introduce a process we call dispersion, which can be used to separate a group of particles located on a single vertex of finite graph. The particles are assumed to be unlabeled and behave identically, with no symmetry breaking properties. The only action they can perform is to move randomly from their current location to a neighboring vertex when disturbed. Physically, we can imagine the particles as being similarly charged and thus move apart when brought into contact.
For symmetric graphs such as paths, trees, grids, and hypercubes, and of large enough size n in terms of the number of particles M, we give bounds on the time to finish dispersion, and the maximum distance traveled from the origin as a function of M.
Thomas Sauerwald: On coalescence time in graphs - When is coalescing as fast as meeting?
Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper et al. and Berenbrink et al., the coalescence time for graphs such as binary trees, d-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved.
We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log^2 n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O(n^3). By duality, our results give bounds on the voter model.
[4pm - 5.30pm] Opinions and Rumors
Nastassia Pouradier Duteil: Sparse Control of Hegselmann-Krause Models: Black Hole and Declustering
We elaborate control strategies to prevent clustering effects in opinion formation models. This is the exact opposite of numerous situations encountered in the literature where, on the contrary, one seeks controls promoting consensus. In order to promote declustering, instead of using the classical variance that does not capture well the phenomenon of dispersion, we introduce an entropy-type functional that is adapted to measuring pairwise distances between agents. We then focus on a Hegselmann-Krause type system and design declustering sparse controls both in finite-dimensional and kinetic models. We provide general conditions that characterize whether clustering can be avoided as function of the initial data. Such results include the description of black holes (where complete collapse to consensus is not avoidable), safety zones (where the control can keep the system far from clustering), basins of attraction (attractive zones around the clustering set) and collapse prevention (when convergence to the clustering set can be avoided).
Benjamin Doerr: Randomized Rumor Spreading Revisited
We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed.
This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a G(n,p) random graph sampled independently each round.
The following events take place in central Paris in October.