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.
graphs
graph-theory
social-networks
spinacz do papieru
źródło
źródło
Odpowiedzi:
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.
źródło
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.
źródło