• Previous Article
    On the asymptotic character of a generalized rational difference equation
  • DCDS Home
  • This Issue
  • 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
April 2018, 38(4): 1719-1744. doi: 10.3934/dcds.2018071

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

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

Received  May 2016 Revised  October 2017 Published  January 2018

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: Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071
References:
[1]

D. Aldous, Interacting particle systems as stochastic social dynamics, Bernoulli, 19 (2013), 1122-1149. doi: 10.3150/12-BEJSP04.

[2]

C. BorgsJ. ChayesL. LovászV. 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.

[3]

C. BorgsJ. ChayesL. LovászV. 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.

[4]

C. BorgsJ. ChayesL. LovászV. 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.

[5]

R. Diestel, Graph Theory, Fifth edition. Graduate Texts in Mathematics, 173. Springer, Berlin, 2017. doi: 10.1007/978-3-662-53622-3.

[6]

M. DyerG. IstrateL. A. GoldbergC. Greenhill and M. Jerrum, Convergence of the iterated prisoner's dilemma game, Combin. Probab. Comput., 11 (2002), 135-147. doi: 10.1017/S096354830100503X.

[7]

G. B. Folland, Real Analysis: Modern Techniques and Their Applications, Wiley-Interscience Publication, 2nd ed., 1999.

[8]

D. A. FrenchZ. TeymurogluT. 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.

[9]

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.

[10]

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.

[11]

S. Janson, Connectedness in graph limits, U. U. D. M. report, ISSN 1101-3591, Department of Mathematics, Uppsala University, 2008.

[12]

S. Janson, T. Ɫuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000. doi: 10.1002/9781118032718.

[13]

U. KangB. 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.

[14]

L. Lovász, Large Networks and Graph Limits, American Mathematical Society, Rhode Island, 2012. doi: 10.1090/coll/060.

[15]

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.

[16]

J. Lunze and F. Lamnabhi-Lagarrigue, Handbook of Hybrid Systems Control: Theory, Tools, Applications, Cambridge University Press, 2009. doi: 10.1017/CBO9780511807930.

[17]

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.

[18]

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.

[19]

G. S. Medvedev, Small-world networks of Kuramoto oscillators, Phys. D, 266 (2014), 13-22. doi: 10.1016/j.physd.2013.09.008.

[20]

G. S. Medvedev, Stochastic stability of continuous time consensus protocols, SIAM J. Control Optim., 50 (2012), 1859-1885. doi: 10.1137/100801457.

[21]

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.

[22]

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.

[23]

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.

[24]

R. Olfati-SaberJ. 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.

[25]

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.

[26]

W. RenR. 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.

[27]

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.

[28]

D. Williams, Probability with Martingales, Cambridge University Press, Cambridge, 1991. doi: 10.1017/CBO9780511813658.

show all references

References:
[1]

D. Aldous, Interacting particle systems as stochastic social dynamics, Bernoulli, 19 (2013), 1122-1149. doi: 10.3150/12-BEJSP04.

[2]

C. BorgsJ. ChayesL. LovászV. 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.

[3]

C. BorgsJ. ChayesL. LovászV. 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.

[4]

C. BorgsJ. ChayesL. LovászV. 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.

[5]

R. Diestel, Graph Theory, Fifth edition. Graduate Texts in Mathematics, 173. Springer, Berlin, 2017. doi: 10.1007/978-3-662-53622-3.

[6]

M. DyerG. IstrateL. A. GoldbergC. Greenhill and M. Jerrum, Convergence of the iterated prisoner's dilemma game, Combin. Probab. Comput., 11 (2002), 135-147. doi: 10.1017/S096354830100503X.

[7]

G. B. Folland, Real Analysis: Modern Techniques and Their Applications, Wiley-Interscience Publication, 2nd ed., 1999.

[8]

D. A. FrenchZ. TeymurogluT. 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.

[9]

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.

[10]

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.

[11]

S. Janson, Connectedness in graph limits, U. U. D. M. report, ISSN 1101-3591, Department of Mathematics, Uppsala University, 2008.

[12]

S. Janson, T. Ɫuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000. doi: 10.1002/9781118032718.

[13]

U. KangB. 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.

[14]

L. Lovász, Large Networks and Graph Limits, American Mathematical Society, Rhode Island, 2012. doi: 10.1090/coll/060.

[15]

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.

[16]

J. Lunze and F. Lamnabhi-Lagarrigue, Handbook of Hybrid Systems Control: Theory, Tools, Applications, Cambridge University Press, 2009. doi: 10.1017/CBO9780511807930.

[17]

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.

[18]

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.

[19]

G. S. Medvedev, Small-world networks of Kuramoto oscillators, Phys. D, 266 (2014), 13-22. doi: 10.1016/j.physd.2013.09.008.

[20]

G. S. Medvedev, Stochastic stability of continuous time consensus protocols, SIAM J. Control Optim., 50 (2012), 1859-1885. doi: 10.1137/100801457.

[21]

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.

[22]

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.

[23]

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.

[24]

R. Olfati-SaberJ. 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.

[25]

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.

[26]

W. RenR. 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.

[27]

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.

[28]

D. Williams, Probability with Martingales, Cambridge University Press, Cambridge, 1991. doi: 10.1017/CBO9780511813658.

Figure 1.  A plot of the function $W$
[1]

Marina Dolfin, Mirosław Lachowicz. Modeling opinion dynamics: How the network enhances consensus. Networks & Heterogeneous Media, 2015, 10 (4) : 877-896. doi: 10.3934/nhm.2015.10.877

[2]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279

[3]

Dorota Bors, Robert Stańczy. Dynamical system modeling fermionic limit. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 45-55. doi: 10.3934/dcdsb.2018004

[4]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361

[5]

Helge Holden, Nils Henrik Risebro. The continuum limit of Follow-the-Leader models — a short proof. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 715-722. doi: 10.3934/dcds.2018031

[6]

Valery A. Gaiko. The geometry of limit cycle bifurcations in polynomial dynamical systems. Conference Publications, 2011, 2011 (Special) : 447-456. doi: 10.3934/proc.2011.2011.447

[7]

Ben Niu, Weihua Jiang. Dynamics of a limit cycle oscillator with extended delay feedback. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1439-1458. doi: 10.3934/dcdsb.2013.18.1439

[8]

Luca Dieci, Cinzia Elia, Dingheng Pi. Limit cycles for regularized discontinuous dynamical systems with a hyperplane of discontinuity. Discrete & Continuous Dynamical Systems - B, 2017, 22 (8) : 3091-3112. doi: 10.3934/dcdsb.2017165

[9]

Oliver Díaz-Espinosa, Rafael de la Llave. Renormalization and central limit theorem for critical dynamical systems with weak external noise. Journal of Modern Dynamics, 2007, 1 (3) : 477-543. doi: 10.3934/jmd.2007.1.477

[10]

Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022

[11]

Michael Herty, Mattia Zanella. Performance bounds for the mean-field limit of constrained dynamics. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 2023-2043. doi: 10.3934/dcds.2017086

[12]

Zhi-An Wang, Kun Zhao. Global dynamics and diffusion limit of a one-dimensional repulsive chemotaxis model. Communications on Pure & Applied Analysis, 2013, 12 (6) : 3027-3046. doi: 10.3934/cpaa.2013.12.3027

[13]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001

[14]

Robin Cohen, Alan Tsang, Krishna Vaidyanathan, Haotian Zhang. Analyzing opinion dynamics in online social networks. Big Data & Information Analytics, 2016, 1 (4) : 279-298. doi: 10.3934/bdia.2016011

[15]

Aylin Aydoğdu, Sean T. McQuade, Nastassia Pouradier Duteil. Opinion Dynamics on a General Compact Riemannian Manifold. Networks & Heterogeneous Media, 2017, 12 (3) : 489-523. doi: 10.3934/nhm.2017021

[16]

Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533

[17]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

[18]

Jory Griffin, Jens Marklof. Limit theorems for skew translations. Journal of Modern Dynamics, 2014, 8 (2) : 177-189. doi: 10.3934/jmd.2014.8.177

[19]

Franco Flandoli, Matti Leimbach. Mean field limit with proliferation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3029-3052. doi: 10.3934/dcdsb.2016086

[20]

John Guckenheimer, Hinke M. Osinga. The singular limit of a Hopf bifurcation. Discrete & Continuous Dynamical Systems - A, 2012, 32 (8) : 2805-2823. doi: 10.3934/dcds.2012.32.2805

2016 Impact Factor: 1.099

Metrics

  • PDF downloads (45)
  • HTML views (175)
  • Cited by (0)

Other articles
by authors

[Back to Top]