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