• Previous 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
  • DCDS Home
  • This Issue
  • Next Article
    On the asymptotic character of a generalized rational difference equation
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 and Continuous Dynamical Systems, 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 and Heterogeneous Media, 2015, 10 (4) : 877-896. doi: 10.3934/nhm.2015.10.877

[2]

Seung-Yeal Ha, Myeongju Kang, Bora Moon. Uniform-in-time continuum limit of the lattice Winfree model and emergent dynamics. Kinetic and Related Models, 2021, 14 (6) : 1003-1033. doi: 10.3934/krm.2021036

[3]

GuanLin Li, Sebastien Motsch, Dylan Weber. Bounded confidence dynamics and graph control: Enforcing consensus. Networks and Heterogeneous Media, 2020, 15 (3) : 489-517. doi: 10.3934/nhm.2020028

[4]

Magdalena Foryś-Krawiec, Jana Hantáková, Piotr Oprocha. On the structure of α-limit sets of backward trajectories for graph maps. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1435-1463. doi: 10.3934/dcds.2021159

[5]

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

[6]

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

[7]

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

[8]

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

[9]

Pierre Degond, Sophie Hecht, Nicolas Vauchelet. Incompressible limit of a continuum model of tissue growth for two cell populations. Networks and Heterogeneous Media, 2020, 15 (1) : 57-85. doi: 10.3934/nhm.2020003

[10]

Mayte Pérez-Llanos, Juan Pablo Pinasco, Nicolas Saintier. Opinion fitness and convergence to consensus in homogeneous and heterogeneous populations. Networks and Heterogeneous Media, 2021, 16 (2) : 257-281. doi: 10.3934/nhm.2021006

[11]

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

[12]

Hongyong Cui, Peter E. Kloeden, Meihua Yang. Forward omega limit sets of nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (4) : 1103-1114. doi: 10.3934/dcdss.2020065

[13]

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

[14]

Amir Adibzadeh, Mohsen Zamani, Amir A. Suratgar, Mohammad B. Menhaj. Constrained optimal consensus in dynamical networks. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 349-360. doi: 10.3934/naco.2019023

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Rong Rong, Yi Peng. KdV-type equation limit for ion dynamics system. Communications on Pure and Applied Analysis, 2021, 20 (4) : 1699-1719. doi: 10.3934/cpaa.2021037

[20]

Nastassia Pouradier Duteil. Mean-field limit of collective dynamics with time-varying weights. Networks and Heterogeneous Media, 2022, 17 (2) : 129-161. doi: 10.3934/nhm.2022001

2020 Impact Factor: 1.392

Metrics

  • PDF downloads (299)
  • HTML views (294)
  • Cited by (0)

Other articles
by authors

[Back to Top]