problème de graphique de réseau social

Voici le problème:

Il y a un graphe connecté avec des nœuds représentant un certain nombre de personnes. Chaque nœud / personne a une opinion sur un sujet, par exemple Trump vs Clinton, livres papier vs Kindle, etc.

L'objectif est de faire en sorte que chaque nœud d'un graphique partage la même opinion, en sélectionnant un sous-ensemble spécifique de nœuds, dans une séquence particulière.

Si la majorité des amis d'une personne A soutiennent Trump, mais la personne A soutient Clinton. si la personne A est sélectionnée, son opinion changera en atout.

Si les opinions des amis de la personne sont également partagées, vous pouvez décider de l'opinion de la personne sélectionnée.

Je suis à court d'idées sur la façon de prouver que cela est réalisable. Peut-être que certains d'entre vous peuvent me donner quelques conseils.

C'est ce qu'on appelle la dynamique majoritaire . Habituellement, l'hypothèse est que tous les nœuds adoptent simultanément l'opinion majoritaire, et ceci est connu comme le modèle synchrone. Pour une règle de bris d'égalité arbitraire, cela converge soit vers un point fixe, soit vers un cycle de longueur 2; voir par exemple les pages 5-6 de Ginosar et Holzman L'action majoritaire sur les graphiques in nis: cordes et marionnettes . Si vous rompez les liens de manière biaisée, la dynamique converge probablement toujours.

Ce que vous décrivez est le modèle asynchrone, dans lequel la règle de la majorité est appliquée en séquence plutôt qu'en parallèle. Dans ce cas, le processus converge toujours. Voir par exemple Tamuz et Tesler , bien que leurs méthodes soient probablement exagérées pour vous, car dans votre cas, vous pouvez choisir la séquence, alors que dans leur cas, la séquence est choisie au hasard.

Ce n'est généralement pas réalisable. Considérez un triangle bleu et rouge connecté avec un seul bord. Quel que soit le nœud que vous sélectionnez, il conservera sa couleur précédente.

En général, si vous avez de grands clusters monochromes avec peu de connexions entre eux, le graphique est stable.