Detta dokument handlar om omröstningsprocesser om diagram där varje vertex innehåller en av två olika yttranden. I synnerhet studerar vi de bästa av två och de bästa av tre. Här vid varje synkront och diskret tidssteg uppdaterar varje vertex sin åsikt för att matcha majoriteten bland åsikterna hos två slumpmässiga grannar och sig själv (Best-of-two) eller åsikterna hos tre slumpmässiga grannar (Best-of-Tre). Tidigare studier har undersökt dessa processer på kompletta grafer och expander grafer, men vi förstår betydligt mindre om deras egenskaper på grafer med mer komplicerade strukturer. I detta papper studerar vi Best-av-två och Best-av-tre på den stokastiska blockmodellen G(2n, p, q), som är en slumpmässig graf bestående av två distinkta Erdős-Rényi-grafer G(n, p) förenade med slumpmässiga kanter med densitet q ≤ p. Vi får två huvudsakliga resultat. För det första, om p =  på (log n/n) och r = q/p är konstant, visar vi att det finns en fasövergång i r med tröskel r * (specifikt, r * = ε 5 − 2 för Best-of-two, och r * = 1/7 för Best-of-Tre). Om r > r *, kommer processen att nå samförstånd inom O(log log n + log n/ log (np)) steg för varje inledande yttrande konfiguration med en fördomsfull av  och n. Däremot, om r < r *, så finns det en inledande åsiktskonfiguration med en fördomsfull bild av n, från vilken processen kräver minst 2 steg (n) för att nå samförstånd. För det andra, om p är en konstant och r > r *, Vi visar att för varje inledande åsikt konfiguration, processen når samförstånd inom O(log n) steg. Såvitt vi vet är detta det första resultatet när det gäller omröstningar med flera val för godtyckliga inledande åsiktskonfigurationer om icke-fullständiga diagram.
Shimizu och Shiraga REF fick fasövergångsresultat av bäst-av-två och bäst-av-tre på stokastiska blockmodeller.
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Physics', 'Mathematics', 'Computer Science']}