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 \(P(x) \sim \frac{1}{x^{3}}\), 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 \(\alpha < \frac{1}{2}\), and is otherwise blue. We show that if \(\alpha \) is sufficiently biased away from \(\frac{1}{2}\), 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 \ge 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 \(\alpha \) for graphs of a given degree sequence studied in [1] (which includes, e.g., random regular graphs).
M.A. Abdullah and N. Fountoulakis—Research supported by the EPSRC Grant No. EP/K019749/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdullah, M.A., Draief, M.: Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Appl. Math. 180, 1–10 (2015)
Abdullah, M.A., Fountoulakis, N.: A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs, arXiv:1404.4070
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs, (in preparation) http://stat-www.berkeley.edu/pub/users/aldous/RWG/book.html
Bollobás, B., Riordan, O.: The diameter of a scale-free random graph. Combinatorica 24, 5–34 (2004)
Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18, 279–290 (2001)
Buckley, P.G., Osthus, D.: Popularity based random graph models leading to a scale-free degree sequence. Discrete Math. 282, 53–68 (2004)
Cooper, C., Elsässer, R., Radzik, T.: The power of two choices in distributed voting. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 435–446. Springer, Heidelberg (2014)
Cooper, C., Frieze, A.: The cover time of the preferential attachment graph. J. Comb. Theor. Ser. B 97, 269–290 (2004)
Cruise, J., Ganesh, A.: Probabilistic consensus via polling and majority rules. In: Proceeidngs of Allerton Conference (2010)
Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Phys. Rev. Lett. 85, 4633–4636 (2000)
Drinea, E., Enachescu, M., Mitzenmacher, M.: Variations on random graph models for the web. Technical report TR-06-01, Harvard University, Department of Computer Science (2001)
Hassin, Y., Peleg, D.: Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput. 171, 248–268 (2001)
van der Hofstad, R.: Random Graphs and Complex Networks (2013). http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf
Mossel, E., Neeman, J., Tamuz, O.: Majority dynamics and aggregation of nformation in social networks (2012). arXiv:1207.0893
Simon, H.A.: On a class of skew distribution functions. Biometrika 42, 425–440 (1955)
Yule, G.U.: A mathematical theory of evolution, based on the conclusions of Dr. J.G. Willis F.R.S. Phil. Trans. Roy. Soc. Lond. B 213, 21–87 (1925)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Abdullah, M.A., Bode, M., Fountoulakis, N. (2015). Local Majority Dynamics on Preferential Attachment Graphs. In: Gleich, D., Komjáthy, J., Litvak, N. (eds) Algorithms and Models for the Web Graph. WAW 2015. Lecture Notes in Computer Science(), vol 9479. Springer, Cham. https://doi.org/10.1007/978-3-319-26784-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-26784-5_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26783-8
Online ISBN: 978-3-319-26784-5
eBook Packages: Computer ScienceComputer Science (R0)