Finding Large Independent Sets in Networks Using Competitive Dynamics
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912012704940032 |
|---|---|
| author | Mooij, Niek Kryven, Ivan |
| author_facet | Mooij, Niek Kryven, Ivan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding Large Independent Sets in Networks Using Competitive Dynamics Mooij, Niek Kryven, Ivan Physics and Society Dynamical Systems 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. |
| title | Finding Large Independent Sets in Networks Using Competitive Dynamics |
| topic | Physics and Society Dynamical Systems |
| url | https://arxiv.org/abs/2409.01336 |