Consensus and voting on large graphs: An application of graph limit theory

Barton E. Lee

doi:10.3934/dcds.2018071

Article Contents

2018, Volume 38, Issue 4: 1719-1744. Doi: 10.3934/dcds.2018071

This issue Previous Article On the asymptotic character of a generalized rational difference equation Next Article A formula for the boundary of chaos in the lexicographical scenario and applications to the bifurcation diagram of the standard two parameter family of quadratic increasing-increasing Lorenz maps

Consensus and voting on large graphs: An application of graph limit theory

Barton E. Lee

School of Mathematics and Statistics, The University of New South Wales, Sydney NSW 2052, Australia

Received: April 30, 2016

Revised: September 30, 2017

Published: June 2018

Abstract Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

Building on recent work by Medvedev (2014) we establish new connections between a basic consensus model, called the voting model, and the theory of graph limits. We show that in the voting model if consensus is attained in the continuum limit then solutions to the finite model will eventually be close to a constant function, and a class of graph limits which guarantee consensus is identified. It is also proven that the dynamics in the continuum limit can be decomposed as a direct sum of dynamics on the connected components, using Janson's definition of connectivity for graph limits. This implies that without loss of generality it may be assumed that the continuum voting model occurs on a connected graph limit.

Keywords:

Mathematics Subject Classification: Primary: 45J05, 45M05; Secondary: 93C15, 93C20, 94C15.

Citation:

Full Text(HTML)

Figure 1. A plot of the function $W$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

	D. Aldous , Interacting particle systems as stochastic social dynamics, Bernoulli, 19 (2013) , 1122-1149. doi: 10.3150/12-BEJSP04.
	C. Borgs , J. Chayes , L. Lovász , V. T. Sós and K. Vesztergombi , Convergent sequences of dense graphs. I. subgraph frequencies, metric properties, and testing, Adv. Math., 219 (2008) , 1801-1851. doi: 10.1016/j.aim.2008.07.008.
	C. Borgs , J. Chayes , L. Lovász , V. T. Sós and K. Vesztergombi , Convergent sequences of dense graphs. Ⅱ. multiway cuts and statistical physics, Ann. of Math., 176 (2012) , 151-219. doi: 10.4007/annals.2012.176.1.2.
	C. Borgs , J. Chayes , L. Lovász , V. T. Sós and K. Vesztergombi , Limits of randomly grown graph sequences, Eur. J. Comb., 32 (2011) , 985-999. doi: 10.1016/j.ejc.2011.03.015.
	R. Diestel, Graph Theory, Fifth edition. Graduate Texts in Mathematics, 173. Springer, Berlin, 2017. doi: 10.1007/978-3-662-53622-3.
	M. Dyer , G. Istrate , L. A. Goldberg , C. Greenhill and M. Jerrum , Convergence of the iterated prisoner's dilemma game, Combin. Probab. Comput., 11 (2002) , 135-147. doi: 10.1017/S096354830100503X.
	G. B. Folland, Real Analysis: Modern Techniques and Their Applications, Wiley-Interscience Publication, 2nd ed., 1999.
	D. A. French , Z. Teymuroglu , T. J. Lewis and R. J. Braun , An integro-differential equation model for the spread of alcohol abuse, J. Integral Equations Appl., 22 (2010) , 443-464. doi: 10.1216/JIE-2010-22-3-443.
	B. Golub and M. O. Jackson , Naive learning in social networks: Convergence, influence and the wisdom of crowds, American Economic Journal: Microeconomics, 2 (2010) , 112-149. doi: 10.1257/mic.2.1.112.
	L. I. Ignat and J. D. Rossi , Decay estimates for nonlocal problems via energy methods, J. Math. Pures Appl., 92 (2009) , 163-187. doi: 10.1016/j.matpur.2009.04.009.
	S. Janson, Connectedness in graph limits, U. U. D. M. report, ISSN 1101-3591, Department of Mathematics, Uppsala University, 2008.
	S. Janson, T. Ɫuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000. doi: 10.1002/9781118032718.
	U. Kang , B. Meeder and C. Faloutsos , Spectral analysis for billion-scale graphs: Discoveries and implementation, PAKDD'11 Proceedings of the 15th Pacific-Asia conference on Advances in knowledge discovery and data mining, (2011) , 13-25. doi: 10.1007/978-3-642-20847-8_2.
	L. Lovász, Large Networks and Graph Limits, American Mathematical Society, Rhode Island, 2012. doi: 10.1090/coll/060.
	L. Lovász and B. Szegedy , Limits of dense graph sequences, J. Combin. Theory Ser. B, 96 (2006) , 933-957. doi: 10.1016/j.jctb.2006.05.002.
	J. Lunze and F. Lamnabhi-Lagarrigue, Handbook of Hybrid Systems Control: Theory, Tools, Applications, Cambridge University Press, 2009. doi: 10.1017/CBO9780511807930.
	G. S. Medvedev , The nonlinear heat equation on dense graphs and graph limits, SIAM J. Math. Anal., 46 (2014) , 2743-2766. doi: 10.1137/130943741.
	G. S. Medvedev , The nonlinear heat equation on $W$ -random graphs, Archive for Rational Mechanics and Analysis, 212 (2014) , 781-803. doi: 10.1007/s00205-013-0706-9.
	G. S. Medvedev , Small-world networks of Kuramoto oscillators, Phys. D, 266 (2014) , 13-22. doi: 10.1016/j.physd.2013.09.008.
	G. S. Medvedev , Stochastic stability of continuous time consensus protocols, SIAM J. Control Optim., 50 (2012) , 1859-1885. doi: 10.1137/100801457.
	G. S. Medvedev and X. Tang , Stability of twisted states in the Kuramoto model on Cayley and random graphs, J. Nonlinear Sci., 25 (2015) , 1169-1208. doi: 10.1007/s00332-015-9252-y.
	G. S. Medvedev and S. Zhuravytska , The geometry of spontaneous spiking in neuronal networks, J. Nonlinear Sci., 22 (2012) , 689-725. doi: 10.1007/s00332-012-9125-6.
	R. Olfati-Saber and R. M. Murray, Consensus protocols for networks of dynamics agents Proceedings of the American Control Conference, June (2003). doi: 10.1109/ACC.2003.1239709.
	R. Olfati-Saber , J. A. Fax and R. M. Murray , Consensus and cooperation in networked multi-agent systems, Proceedings of the IEEE, 95 (2007) , 215-233. doi: 10.1109/JPROC.2006.887293.
	O. E. Omelchenko, M. Wolfrum, S. Yanchuk, Y. Maistrenko and O. Sudakov, Stationary patterns of coherence and incoherence in two-dimensional arrays of non-locally-coupled phase oscillators, Phys. Rev. E, 85 (2012), 036210.
	W. Ren , R. W. Beard and E. M. Atkins , Information consensus in multivehicle cooperative control, IEEE Control Syst. Mag., 27 (2007) , 71-82. doi: 10.1109/MCS.2007.338264.
	D. A. Wiley, S. H. Strogatz and M. Girvan, The size of the sync basin Chaos, 16 (2006), 015103, 8pp. doi: 10.1063/1.2165594.
	D. Williams, Probability with Martingales, Cambridge University Press, Cambridge, 1991. doi: 10.1017/CBO9780511813658.