Dinâmicas de Maioria Assíncronas em Grafos Aleatórios Binomiais

Estudamos a agregação de informações em redes quando os agentes interagem para aprender um estado binário do mundo. Inicialmente, cada agente observa privadamente um sinal independente que está correto com probabilidade \ (12+ \) para algum δ > 0. A cada rodada, um nó é selecionado uniformemente ao acaso para atualizar sua opinião pública para coincidir com a maioria de seus vizinhos (desempate a favor de seu sinal privado inicial). Nosso principal resultado mostra que para grafos aleatórios binomiais esparsos e conectados \ ({G} (n, p) \) o processo se estabiliza em um consenso correto em \ (O (n ² n/ n) \) passos com alta probabilidade. De fato, quando log n / n ≪ p = o (1) o processo termina no tempo \ (T = (1+o (1) ) n n \), onde \ (T \) é o primeiro momento em que todos os nós foram selecionados pelo menos uma vez. No entanto, em grafos aleatórios binomiais densos com p = Ω (1), ocorre uma cascata de informações onde o processo termina no consenso incorreto com probabilidade afastada de zero.