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.
Citation: |
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.![]() ![]() ![]() |
A plot of the function