problem z wykresem sieci społecznościowej

Oto problem:

Jest połączony wykres z węzłami reprezentującymi wiele osób. Każdy węzeł / osoba ma opinię na dany temat, np. Atut vs clinton, papierowe książki kontra kindle itp

Celem jest, aby każdy węzeł na wykresie podzielał tę samą opinię, wybierając konkretny podzbiór węzłów, w określonej kolejności.

Jeśli większość przyjaciół osoby A popiera atut, ale osoba A wspiera clintona. jeśli zostanie wybrana osoba A., jej opinia zmieni się na atut.

Jeśli opinie znajomych danej osoby są równo podzielone, możesz zdecydować o opinii wybranej osoby.

Brakuje mi pomysłów, jak udowodnić, że można to osiągnąć. Może niektórzy z was mogą dać mi wskazówki.

Jest to znane jako dynamika większości . Zwykle zakłada się, że wszystkie węzły przyjmują jednocześnie opinię większości, co jest znane jako model synchroniczny. W przypadku dowolnej reguły zerwania powiązania jest ona zbieżna albo w stałym punkcie, albo w cyklu o długości 2; patrz na przykład strony 5-6 Ginosara i Holzmana Większość akcji na niezliczonych grafach: struny i lalki . Jeśli zerwiesz więzi w sposób stronniczy, wówczas dynamika prawdopodobnie zawsze będzie zbieżna.

To, co opisujesz, to model asynchroniczny, w którym reguła większości jest stosowana kolejno, a nie równolegle. W takim przypadku proces zawsze jest zbieżny. Zobacz na przykład Tamuz i Tesler , chociaż ich metody są prawdopodobnie dla ciebie przesadne , ponieważ w twoim przypadku możesz wybrać sekwencję, podczas gdy w ich przypadku sekwencja jest wybierana losowo.

Zasadniczo nie jest to możliwe. Rozważ niebieski i czerwony trójkąt połączony jedną krawędzią. Niezależnie od wybranego węzła zachowany zostanie jego poprzedni kolor.

Ogólnie rzecz biorąc, jeśli masz duże klastry monochromatyczne z kilkoma połączeniami między nimi, wykres jest stabilny.