Papers › Finding Large Independent Sets in Networks Using Competitive Dynamics
Finding Large Independent Sets in Networks Using Competitive Dynamics
Niek Mooij, Ivan Kryven
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Many decision-making algorithms draw inspiration from the inner workings of individual biological systems. However, it remains unclear whether collective behavior among biological species can also lead to solutions for computational tasks. By studying the coexistence of species that interact through simple rules on a network, we demonstrate that the underlying dynamical system can recover near-optimal solutions to the maximum independent set problem -- a fundamental, computationally hard problem in graph theory. Furthermore, we observe that the optimality of these solutions is improved when the competitive pressure in the system is gradually increased. We explain this phenomenon by showing that the cascade of bifurcation points, which occurs with rising competitive pressure in our dynamical system, naturally gives rise to Katz centrality-based node removal in the network. By formalizing this connection, we propose a biologically inspired discrete algorithm for approximating the maximum independent set problem on a graph. Our results indicate that complex systems may collectively possess the capacity to perform non-trivial computations, with implications spanning biology, economics, and other fields.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections