• 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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[12]

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

[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.  Google Scholar

[14]

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

[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.  Google Scholar

[16]

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

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

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

show all references

References:
[1]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

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

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[12]

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

[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.  Google Scholar

[14]

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

[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.  Google Scholar

[16]

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

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

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

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

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[2]

Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316

[3]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[4]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[5]

Shao-Xia Qiao, Li-Jun Du. Propagation dynamics of nonlocal dispersal equations with inhomogeneous bistable nonlinearity. Electronic Research Archive, , () : -. doi: 10.3934/era.2020116

[6]

Ebraheem O. Alzahrani, Muhammad Altaf Khan. Androgen driven evolutionary population dynamics in prostate cancer growth. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020426

[7]

José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020376

[8]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (154)
  • HTML views (282)
  • Cited by (0)

Other articles
by authors

[Back to Top]