A large diffusion and small amplification dynamics for density classification on graphs

Laura Leal (), Pedro Montealegre, Axel Osses () and Ivan Rapaport ()
Additional contact information
Laura Leal: Departamento de Ingeniería Matemática, Universidad de Chile, Chile
Pedro Montealegre: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Chile
Axel Osses: DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Chile
Ivan Rapaport: DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Chile

International Journal of Modern Physics C (IJMPC), 2023, vol. 34, issue 05, 1-16

Abstract: The density classification problem on graphs consists in finding a local dynamics such that, given a graph and an initial configuration of 0’s and 1’s assigned to the nodes of the graph, the dynamics converge to the fixed point configuration of all 1’s if the fraction of 1’s is greater than the critical density (typically 1/2) and, otherwise, it converges to the all 0’s fixed point configuration. To solve this problem, we follow the idea proposed in [R. Briceño, P. M. de Espanés, A. Osses and I. Rapaport, Physica D 261, 70 (2013)], where the authors designed a cellular automaton inspired by two mechanisms: diffusion and amplification. We apply this approach to different well-known graph classes: complete, regular, star, Erdös–Rényi and Barabási–Albert graphs.

Keywords: Automata networks; density classification; Laplacian matrix (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183123500560
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:34:y:2023:i:05:n:s0129183123500560

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183123500560

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().