Beliebiger Eintrag,
Bounds on the voting time in terms of the conductance
(2014)
Zusammenfassung
In the voting model each node has an opinion and in every time step each node adopts the opinion of a random neighbour. We show that the consensus time, i.e., expected time required until one opinion prevails, is bounded by O(n / phi) for regular graphs, where phi is the conductance of the graph. This bound is tight for regular expanders. For non-regular graphs we obtain a bound of O( (davg / dmin)(n / phi) ), where davg is the average degree and dmin is the minimum degree. Additionally, we consider a generalization of the model where every opinion has a popularity. Here, every node chooses a neighbour and adopts its opinion with some probability which depends on the popularity of the neighbour's opinion. We show that the expected consensus time for a regular graph having initially two distinct opinions is bounded by O( logn / phi).
