problema de gráfico de rede social

Aqui está o problema:

Há um gráfico conectado com nós que representam um número de pessoas. Cada nó / pessoa tem uma opinião sobre um tópico, por exemplo, Trump vs Clinton, livros em papel vs Kindle, etc.

O objetivo é fazer com que todos os nós em um gráfico compartilhem a mesma opinião, selecionando um subconjunto específico de nós, em uma sequência específica.

Se a maioria dos amigos de uma pessoa A apoia trunfo, mas a pessoa A apoia Clinton. se a pessoa A for selecionada, sua opinião mudará para trunfo.

Se as opiniões dos amigos da pessoa estiverem igualmente divididas, você poderá decidir a opinião da pessoa selecionada.

Estou ficando sem idéias sobre como provar que isso é possível. Talvez alguns de vocês possam me dar algumas dicas.

Isso é conhecido como dinâmica majoritária . Normalmente, a suposição é que todos os nós adotam a opinião majoritária simultaneamente, e isso é conhecido como modelo síncrono. Para uma regra arbitrária de desempate, isso converge para um ponto fixo ou para um ciclo de comprimento 2; ver, por exemplo, páginas 5-6 de Ginosar e Holzman de A ação da maioria sobre em gráficos nite: cordas e fantoches . Se você rompe os laços de maneira tendenciosa, a dinâmica provavelmente sempre converge.

O que você descreve é ​​o modelo assíncrono, no qual a regra majoritária é aplicada em sequência e não em paralelo. Nesse caso, o processo sempre converge. Veja, por exemplo, Tamuz e Tesler , embora seus métodos provavelmente sejam um exagero para você, pois no seu caso você escolhe a sequência, enquanto que no caso deles a sequência é escolhida aleatoriamente.

Isso geralmente não é possível. Considere um triângulo azul e vermelho conectado com uma única aresta. Qualquer nó que você selecionar manterá sua cor anterior.

Em geral, se você tiver grandes agrupamentos monocromáticos com poucas conexões entre eles, o gráfico é estável.