Phase Transitions of BestofTwo and BestofThree on Stochastic Block Models This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the emphBestoftwo and the emphBestofthree. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Bestoftwo) or the opinions of three random neighbors (the Bestofthree). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures.  :90,this paper, we study the Bestoftwo and the Bestofthree on the stochastic block model G(2n,p,q), which is a random graph consisting of two distinct Erdxc5x91sRenyi graphs G(n,p) joined by random edges with density qleq p. We obtain two main results. First, if pomega(log nn) and rqp is a constant, we show that there is a phase transition in r with threshold r* (specifically, r*sqrt52 for the Bestoftwo, and r*17 for the Bestofthree). If ru003er*, the process reaches consensus within O(log log nlog nlog (np)) steps for any initial opinion configuration with a bias of Omega(n). By contrast, if r r*, we show that, for any initial opinion configuration, the process reaches consensus within O(log n) steps. To the best of our knowledge, :90,this is the first result concerning multiplechoice voting for arbitrary initial opinion configurations on noncomplete graphs.

On the benefits of saturating information in consensus networks with noise Abstract   In a consensus network subject to nonzero mean noise, the system state may be driven away even when the disagreement exhibits a bounded response. This is unfavourable in applications since the nodes may not work properly and even be faulty outside their operating region. In this paper, we propose a new control algorithm to mitigate this issue by assigning each node a favourite interval that characterizes the nodes desired convergence region. The algorithm is implemented in a selftriggered fashion. If the nodes do not share a global clock, the network operates in a fully asynchronous mode. By this algorithm, we show that the state evolution is confined around the favourite interval and the node disagreement is bounded by a simple linear function of the noise magnitude, without requiring any priori information on the noise. We also show that if the nodes share some global information, then the algorithm can be adjusted to make the nodes evolve into the favourite interval, improve on the disagreement bound and achieve asymptotic consensus in the noiseless case.