Finding Large Independent Sets in Networks Using Competitive Dynamics

Many decision-making algorithms were inspired by the inner working of individual biological systems. However, it is less clear whether collective behaviour of biological species can also be interpreted as a mechanism for solving computational tasks. By studying coexistence of species interacting through simple rules on a complex network, we demonstrate that the underlying dynamical system recovers near-optimal solutions to the maximum independent set problem -- one of the fundamental computationally hard problems in graph theory. Furthermore, through illuminating an unexpected connection between bifurcation points in the underlying dynamical system and the Katz centrality in the network, we introduce an algorithm for approximating the maximum independent set problem on a graph. Because of fundamental positioning of this problem in science, our results have multi-fold relevance for biology, economics, complex systems, as well as computer science, including the identification of optimal error-correcting codes.<br><br>These files contain the numerical study performed for the article Finding Large Independent Sets in Networks Using Competitive Dynamics by M.N. Mooij &amp; I. Kryven.