Bounds on the voting time in terms of the conductance

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2014-08-20
Authors/Contributors
Abstract
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).
Document
Identifier
etd8557
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed, but not for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Berenbrink, Petra
Member of collection
Attachment Size
etd8557_FMallmann-Trenn.pdf 1.17 MB