Grafikproblem des sozialen Netzwerks

Hier ist das Problem:

Es gibt verbundene Graphen mit Knoten, die eine Anzahl von Personen darstellen. Jeder Knoten / jede Person hat eine Meinung zu einem Thema, z. B. Trump gegen Clinton, Papierbücher gegen Kindle usw.

Das Ziel besteht darin, dass jeder Knoten in einem Diagramm dieselbe Meinung teilt, indem eine bestimmte Teilmenge von Knoten in einer bestimmten Reihenfolge ausgewählt wird.

Wenn die Mehrheit der Freunde einer Person A Trump unterstützt, aber Person A Clinton unterstützt. Wenn Person A ausgewählt wird, ändert sich ihre Meinung zu Trump.

Wenn die Meinungen der Freunde einer Person gleichermaßen geteilt sind, können Sie die Meinung der ausgewählten Person festlegen.

Mir gehen die Ideen aus, wie man beweisen kann, dass dies erreichbar ist. Vielleicht können einige von Ihnen mir einige Hinweise geben.

Dies ist als Mehrheitsdynamik bekannt . Normalerweise wird davon ausgegangen, dass alle Knoten gleichzeitig die Mehrheitsmeinung übernehmen, und dies wird als synchrones Modell bezeichnet. Für eine beliebige Regel zum Brechen von Bindungen konvergiert dies entweder zu einem festen Punkt oder zu einem Zyklus der Länge 2; siehe zum Beispiel die Seiten 5-6 von Ginosar und Holzman ist die Mehrheit Aktion auf unendliche Graphen: Strings und Puppen . Wenn Sie die Verbindungen voreingenommen lösen, konvergiert die Dynamik wahrscheinlich immer.

Was Sie beschreiben, ist das asynchrone Modell, bei dem die Mehrheitsregel nicht parallel, sondern nacheinander angewendet wird. In diesem Fall konvergiert der Prozess immer. Siehe zum Beispiel Tamuz und Tesler , obwohl ihre Methoden für Sie wahrscheinlich übertrieben sind, da Sie in Ihrem Fall die Sequenz auswählen können, während in ihrem Fall die Sequenz zufällig ausgewählt wird.

Dies ist im Allgemeinen nicht erreichbar. Stellen Sie sich ein blaues und ein rotes Dreieck vor, die mit einer einzelnen Kante verbunden sind. Unabhängig davon, welchen Knoten Sie auswählen, bleibt die vorherige Farbe erhalten.

Wenn Sie große monochromatische Cluster mit wenigen Verbindungen zwischen ihnen haben, ist der Graph im Allgemeinen stabil.