A large diffusion and small amplification dynamics for density classification on graphs
Leal
L
author
Montealegre
P
author
Osses
A
author
Rapaport
I
author
2022
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. Briceno, P. M. de Espanes, 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, Erdos-Renyi and Barabasi-Albert graphs.
Automata networks
density classification
Laplacian matrix
WOS:000882906900002
exported from refbase (show.php?record=1656), last updated on Tue, 13 Dec 2022 16:32:33 -0300
text
10.1142/S0129183123500560
Leal_etal2022
International Journal Of Modern Physics C
Int. J. Mod Phys. C
2022
continuing
periodical
academic journal
Early Access
0129-1831