Optimalizace inicializace v dynamice grafů: od feromagnetismu k názorovému konsenzu

Jankola, Marek

The analytical study of non-equilibrium properties of dynamical systems is notoriously hard. The backtracking dynamical cavity method (BDCM) is a step forward in understanding such systems by characterizing the properties of attractors on large sparse graphs. In particular, it has allowed us to study majority dynamics, answering questions such as "What is the minimal initial number of +1 nodes needed to end up in a +1 global consensus?". In this thesis, we solve the BDCM equations iteratively on full instances of random regular and Erdős-Rényi graphs, which gives us lower bounds on the minimal fraction of initial +1 nodes necessary for consensus. Furthermore, we aim to find these initial conditions. To this end, we introduce a novel algorithm that we coin history passing reinforcement (HPR). It is an adaptation of the belief propagation reinforcement algorithm to the BDCM framework. We find that our algorithm outperforms standard Monte-Carlo based methods, and comes close to the theoretical limits predicted by BDCM. Notably, we find initial conditions where the final consensus is the original opinion of the minority. While we implement HPR in the setting of majority dynamics on random regular graphs, the algorithm generalizes naturally to broader classes of dynamics and network topologies. Finally, we...

guest :: login Digital Repository
		Search		Submit		Help		About