## Abstract

Suppose in a graph G vertices can be either red or blue. Let k be odd. At each time step, each vertex v in G polls k random neighbours and takes the majority colour. If it doesn’t have k neighbours, it simply polls all of them, or all less one if the degree of v is even. We study this protocol on the preferential attachment model of Albert and Barabási [3], which gives rise to a degree distribution that has roughly power-law (Formula Presented.), as well as generalisations which give exponents larger than 3. The setting is as follows: Initially each vertex of G is red independently with probability (Formula Presented.), and is otherwise blue. We show that if α is sufficiently biased away from (Formula Presented.), then with high probability, consensus is reached on the initial global majority within O(log_{d} log_{d} t) steps. Here t is the number of vertices and d ≥ 5 is the minimum of k and m (or m−1 if m is even), m being the number of edges each new vertex adds in the preferential attachment generative process. Additionally, our analysis reduces the required bias of α for graphs of a given degree sequence studied in [1] (which includes, e.g., random regular graphs).

Original language | English |
---|---|

Title of host publication | Algorithms and Models for the Web Graph - 12th International Workshop, WAW 2015, Proceedings |

Editors | David F. Gleich, Nelly Litvak, Júlia Komjáthy |

Publisher | Springer Verlag |

Pages | 95-106 |

Number of pages | 12 |

ISBN (Print) | 9783319267838 |

DOIs | |

Publication status | Published - 2015 |

Event | 12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015 - Eindhoven, Netherlands Duration: 10 Dec 2015 → 11 Dec 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9479 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015 |
---|---|

Country/Territory | Netherlands |

City | Eindhoven |

Period | 10/12/15 → 11/12/15 |

### Bibliographical note

Funding Information:M.A. Abdullah and N. Fountoulakis—Research supported by the EPSRC Grant No. EP/K019749/1.

Publisher Copyright:

© Springer International Publishing Switzerland 2015.

## Keywords

- Consensus
- Local majority dynamics
- Powerlaw graphs
- Preferential attachment
- Voting

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)