Local majority dynamics on preferential attachment graphs

Mohammed Amin Abdullah, Michel Bode, Nikolaos Fountoulakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

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(logd logd 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 languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph - 12th International Workshop, WAW 2015, Proceedings
EditorsDavid F. Gleich, Nelly Litvak, Júlia Komjáthy
PublisherSpringer Verlag
Pages95-106
Number of pages12
ISBN (Print)9783319267838
DOIs
Publication statusPublished - 2015
Event12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015 - Eindhoven, Netherlands
Duration: 10 Dec 201511 Dec 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9479
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015
Country/TerritoryNetherlands
CityEindhoven
Period10/12/1511/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)

Fingerprint

Dive into the research topics of 'Local majority dynamics on preferential attachment graphs'. Together they form a unique fingerprint.

Cite this