TY - JOUR

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

AU - Leal, Laura

AU - Montealegre, Pedro

AU - Osses, Axel

AU - Rapaport, Ivan

N1 - Funding Information:
Acknowledgments This research was possible by the support of the supercomputing infrastructure of the NLHPC (ECM-02) and the support of Centro de Modelamiento Matematico (CMM), FB210005 BASAL funds for centers of excellence from ANID-Chile. L. L. acknowledges the Chilean government through the National Agency for Research and Development (ANID)/Scholarship Program/BECA DOCTORADO NACIONAL/2019-21191440. P. M. acknowledges ANID-FONDECYT 11190482 and ANDO-PAI 77170068. A. O. acknowledges ANID-Fondecyt 1191903, 1201311, FONDAP/15110009, Millennium Program NCN19-161, ACIPDE MATH190008 and Climat-Amsud project CLI2020008. I. R. acknowledges ANID-FONDECYT 1220142.
Publisher Copyright:
© 2023 World Scientific Publishing Company.

PY - 2023/5/1

Y1 - 2023/5/1

N2 - 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.

AB - 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.

KW - Automata networks

KW - Laplacian matrix

KW - density classification

UR - http://www.scopus.com/inward/record.url?scp=85143413908&partnerID=8YFLogxK

U2 - 10.1142/S0129183123500560

DO - 10.1142/S0129183123500560

M3 - Article

AN - SCOPUS:85143413908

SN - 0129-1831

VL - 34

JO - International Journal of Modern Physics C

JF - International Journal of Modern Physics C

IS - 5

M1 - 2350056

ER -