
-
Previous Article
Kinetic modelling of multiple interactions in socio-economic systems
- NHM Home
- This Issue
-
Next Article
Mean field models for large data–clustering problems
Bounded confidence dynamics and graph control: Enforcing consensus
1. | Georgia Institute of Technology, Program in Quantitative Biosciences, Georgia Institute of Technology School of Physics, Atlanta, GA 30332, USA |
2. | Arizona State University, School of Mathematical and Statistical Sciences, Tempe, AZ 85257-1804, USA |
A generic feature of bounded confidence type models is the formation of clusters of agents. We propose and study a variant of bounded confidence dynamics with the goal of inducing unconditional convergence to a consensus. The defining feature of these dynamics which we name the No one left behind dynamics is the introduction of a local control on the agents which preserves the connectivity of the interaction network. We rigorously demonstrate that these dynamics result in unconditional convergence to a consensus. The qualitative nature of our argument prevents us quantifying how fast a consensus emerges, however we present numerical evidence that sharp convergence rates would be challenging to obtain for such dynamics. Finally, we propose a relaxed version of the control. The dynamics that result maintain many of the qualitative features of the bounded confidence dynamics yet ultimately still converge to a consensus as the control still maintains connectivity of the interaction network.
References:
[1] |
M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna and E. Cisbani, et al., Empirical investigation of starling flocks: A benchmark study in collective animal behaviour, Animal Behaviour, 76 (2008), 201–215.
doi: 10.1016/j.anbehav.2008.02.004. |
[2] |
V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis,
On Krause's multi-agent consensus model with state-dependent connectivity, IEEE Trans. Automat. Control, 54 (2009), 2586-2597.
doi: 10.1109/TAC.2009.2031211. |
[3] |
V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis, On the 2R conjecture for multi-agent systems, 2007 European Control Conference (ECC), Kos, Greece, 2007.
doi: 10.23919/ECC.2007.7068885. |
[4] |
J. Buhl, D. J. T. Sumpter, I. D. Couzin, J. J. Hale and E. Despland, et al., From disorder to order in marching locusts, Science, 312 (2006), 1402–1406.
doi: 10.1126/science.1125142. |
[5] |
M. Caponigro, M. Fornasier, B. Piccoli and E. Trélat,
Sparse stabilization and optimal control of the Cucker-Smale model, Math. Control Relat. Fields, 3 (2013), 447-466.
doi: 10.3934/mcrf.2013.3.447. |
[6] |
C. Castellano, S. Fortunato and V. Loreto,
Statistical physics of social dynamics, Rev. Mod. Phys., 81 (2009), 591-646.
doi: 10.1103/RevModPhys.81.591. |
[7] |
G. Deffuant, D. Neau, F. Amblard and G. Weisbuch,
Mixing beliefs among interacting agents, Adv. Complex Syst., 3 (2000), 87-98.
doi: 10.1142/S0219525900000078. |
[8] |
E. Estrada, E. Vargas-Estrada and H. Ando, Communicability angles reveal critical edges for network consensus dynamics, Phys. Rev. E (3), 92 (2015), 10pp.
doi: 10.1103/PhysRevE.92.052809. |
[9] |
K. Garimella, G. De Francisci Morales, A. Gionis and M. Mathioudakis, Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship, Proc. 2018 World Wide Web Conference, 2018, 913–922.
doi: 10.1145/3178876.3186139. |
[10] |
E. Gilbert, T. Bergstrom and K. Karahalios, Blogs are echo chambers: Blogs are echo chambers, 2009 42nd Hawaii International Conference on System Sciences, Big Island, HI, 2009.
doi: 10.1109/HICSS.2009.91. |
[11] |
D. Goldie, M. Linick, H. Jabbar and C. Lubienski, Using Bibliometric and social media analyses to explore the "echo chamber" hypothesis, Educational Policy, 28 (2014).
doi: 10.1177/0895904813515330. |
[12] |
R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence: models, analysis and simulation, J. Artificial Societies Social Simulation, 5 (2002). Google Scholar |
[13] |
J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Grundlehren Text Editions, Springer-Verlag, Berlin, 2001.
doi: 10.1007/978-3-642-56468-0. |
[14] |
P.-E. Jabin and S. Motsch,
Clustering and asymptotic behavior in opinion formation, J. Differential Equations, 257 (2014), 4165-4187.
doi: 10.1016/j.jde.2014.08.005. |
[15] |
D. Kempe, J. Kleinberg and E. Tardos, Maximizing the spread of influence through a social network, Proc. Ninth ACM SIGKDD Internat. Conference Knowledge Discovery Data Mining, 2003, 137–146.
doi: 10.1145/956750.956769. |
[16] |
U. Krause, A discrete nonlinear and non-autonomous model of consensus formation, Communications in Difference Equations, Gordon and Breach, Amsterdam, 2000, 227–236.
doi: 10.1201/b16999-21. |
[17] |
J. Lorenz,
Continuous opinion dynamics under bounded confidence: A survey, Internat. J. Modern Phys. C, 18 (2007), 1819-1838.
doi: 10.1142/S0129183107011789. |
[18] |
J. Lorenz, Consensus strikes back in the Hegselmann-Krause model of continuous opinion dynamics under bounded confidence, J. Artificial Societies Social Simulation, (2006). Google Scholar |
[19] |
S. Motsch and E. Tadmor,
Heterophilious dynamics enhances consensus, SIAM Rev., 56 (2014), 577-621.
doi: 10.1137/120901866. |
[20] |
R. Olfati-Saber, J. A. Fax and R. M. Murray,
Consensus and cooperation in networked multi-agent systems, Proc. IEEE, 95 (2007), 215-233.
doi: 10.1109/TAC.2005.864190. |
[21] |
B. Piccoli, N. Pouradier Duteil and E. Trélat,
Sparse control of Hegselmann–Krause models: Black hole and declustering, SIAM J. Control Optim., 57 (2019), 2628-2659.
doi: 10.1137/18M1168911. |
[22] |
L.-A. Poissonnier, S. Motsch, J. Gautrais, J. Buhl and A. Dussutour, Experimental investigation of ant traffic under crowded conditions, eLife, 8 (2019).
doi: 10.7554/eLife.48945. |
[23] |
W. Quattrociocchi, A. Scala and C. R. Sunstein, Echo Cchambers on Facebook, SSRN, in progress.
doi: 10.2139/ssrn.2795110. |
[24] |
R. O. Saber and R. M. Murray, Consensus protocols for networks of dynamic agents, Proc. 2003 American Control Conference, Denver, CO, 2003.
doi: 10.1109/ACC.2003.1239709. |
[25] |
D. Spanos, R. Olfati-Saber and R. Murray, Dynamic consensus on mobile networks, IFAC World Congress, Citeseer, 2005, 1–6. Google Scholar |
[26] |
T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen and O. Shochet,
Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett., 75 (1995), 1226-1229.
doi: 10.1103/PhysRevLett.75.1226. |
[27] |
D. Weber, R. Theisen and S. Motsch,
Deterministic versus stochastic consensus dynamics on graphs, J. Stat. Phys., 176 (2019), 40-68.
doi: 10.1007/s10955-019-02293-5. |
[28] |
H. Xia, H. Wang and Z. Xuan,
Opinion dynamics: A multidisciplinary review and perspective on future research, Internat. J. Knowledge Syst. Sci. (IJKSS), 2 (2011), 72-91.
doi: 10.4018/978-1-4666-3998-0.ch021. |
[29] |
W. Yu, G. Chen, M. Cao and J. Kurths,
Second-order consensus for multiagent systems with directed topologies and nonlinear dynamics, IEEE Trans. Syst. Man Cybernetics, Part B, 40 (2010), 881-891.
doi: 10.1109/TSMCB.2009.2031624. |
show all references
References:
[1] |
M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna and E. Cisbani, et al., Empirical investigation of starling flocks: A benchmark study in collective animal behaviour, Animal Behaviour, 76 (2008), 201–215.
doi: 10.1016/j.anbehav.2008.02.004. |
[2] |
V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis,
On Krause's multi-agent consensus model with state-dependent connectivity, IEEE Trans. Automat. Control, 54 (2009), 2586-2597.
doi: 10.1109/TAC.2009.2031211. |
[3] |
V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis, On the 2R conjecture for multi-agent systems, 2007 European Control Conference (ECC), Kos, Greece, 2007.
doi: 10.23919/ECC.2007.7068885. |
[4] |
J. Buhl, D. J. T. Sumpter, I. D. Couzin, J. J. Hale and E. Despland, et al., From disorder to order in marching locusts, Science, 312 (2006), 1402–1406.
doi: 10.1126/science.1125142. |
[5] |
M. Caponigro, M. Fornasier, B. Piccoli and E. Trélat,
Sparse stabilization and optimal control of the Cucker-Smale model, Math. Control Relat. Fields, 3 (2013), 447-466.
doi: 10.3934/mcrf.2013.3.447. |
[6] |
C. Castellano, S. Fortunato and V. Loreto,
Statistical physics of social dynamics, Rev. Mod. Phys., 81 (2009), 591-646.
doi: 10.1103/RevModPhys.81.591. |
[7] |
G. Deffuant, D. Neau, F. Amblard and G. Weisbuch,
Mixing beliefs among interacting agents, Adv. Complex Syst., 3 (2000), 87-98.
doi: 10.1142/S0219525900000078. |
[8] |
E. Estrada, E. Vargas-Estrada and H. Ando, Communicability angles reveal critical edges for network consensus dynamics, Phys. Rev. E (3), 92 (2015), 10pp.
doi: 10.1103/PhysRevE.92.052809. |
[9] |
K. Garimella, G. De Francisci Morales, A. Gionis and M. Mathioudakis, Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship, Proc. 2018 World Wide Web Conference, 2018, 913–922.
doi: 10.1145/3178876.3186139. |
[10] |
E. Gilbert, T. Bergstrom and K. Karahalios, Blogs are echo chambers: Blogs are echo chambers, 2009 42nd Hawaii International Conference on System Sciences, Big Island, HI, 2009.
doi: 10.1109/HICSS.2009.91. |
[11] |
D. Goldie, M. Linick, H. Jabbar and C. Lubienski, Using Bibliometric and social media analyses to explore the "echo chamber" hypothesis, Educational Policy, 28 (2014).
doi: 10.1177/0895904813515330. |
[12] |
R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence: models, analysis and simulation, J. Artificial Societies Social Simulation, 5 (2002). Google Scholar |
[13] |
J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Grundlehren Text Editions, Springer-Verlag, Berlin, 2001.
doi: 10.1007/978-3-642-56468-0. |
[14] |
P.-E. Jabin and S. Motsch,
Clustering and asymptotic behavior in opinion formation, J. Differential Equations, 257 (2014), 4165-4187.
doi: 10.1016/j.jde.2014.08.005. |
[15] |
D. Kempe, J. Kleinberg and E. Tardos, Maximizing the spread of influence through a social network, Proc. Ninth ACM SIGKDD Internat. Conference Knowledge Discovery Data Mining, 2003, 137–146.
doi: 10.1145/956750.956769. |
[16] |
U. Krause, A discrete nonlinear and non-autonomous model of consensus formation, Communications in Difference Equations, Gordon and Breach, Amsterdam, 2000, 227–236.
doi: 10.1201/b16999-21. |
[17] |
J. Lorenz,
Continuous opinion dynamics under bounded confidence: A survey, Internat. J. Modern Phys. C, 18 (2007), 1819-1838.
doi: 10.1142/S0129183107011789. |
[18] |
J. Lorenz, Consensus strikes back in the Hegselmann-Krause model of continuous opinion dynamics under bounded confidence, J. Artificial Societies Social Simulation, (2006). Google Scholar |
[19] |
S. Motsch and E. Tadmor,
Heterophilious dynamics enhances consensus, SIAM Rev., 56 (2014), 577-621.
doi: 10.1137/120901866. |
[20] |
R. Olfati-Saber, J. A. Fax and R. M. Murray,
Consensus and cooperation in networked multi-agent systems, Proc. IEEE, 95 (2007), 215-233.
doi: 10.1109/TAC.2005.864190. |
[21] |
B. Piccoli, N. Pouradier Duteil and E. Trélat,
Sparse control of Hegselmann–Krause models: Black hole and declustering, SIAM J. Control Optim., 57 (2019), 2628-2659.
doi: 10.1137/18M1168911. |
[22] |
L.-A. Poissonnier, S. Motsch, J. Gautrais, J. Buhl and A. Dussutour, Experimental investigation of ant traffic under crowded conditions, eLife, 8 (2019).
doi: 10.7554/eLife.48945. |
[23] |
W. Quattrociocchi, A. Scala and C. R. Sunstein, Echo Cchambers on Facebook, SSRN, in progress.
doi: 10.2139/ssrn.2795110. |
[24] |
R. O. Saber and R. M. Murray, Consensus protocols for networks of dynamic agents, Proc. 2003 American Control Conference, Denver, CO, 2003.
doi: 10.1109/ACC.2003.1239709. |
[25] |
D. Spanos, R. Olfati-Saber and R. Murray, Dynamic consensus on mobile networks, IFAC World Congress, Citeseer, 2005, 1–6. Google Scholar |
[26] |
T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen and O. Shochet,
Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett., 75 (1995), 1226-1229.
doi: 10.1103/PhysRevLett.75.1226. |
[27] |
D. Weber, R. Theisen and S. Motsch,
Deterministic versus stochastic consensus dynamics on graphs, J. Stat. Phys., 176 (2019), 40-68.
doi: 10.1007/s10955-019-02293-5. |
[28] |
H. Xia, H. Wang and Z. Xuan,
Opinion dynamics: A multidisciplinary review and perspective on future research, Internat. J. Knowledge Syst. Sci. (IJKSS), 2 (2011), 72-91.
doi: 10.4018/978-1-4666-3998-0.ch021. |
[29] |
W. Yu, G. Chen, M. Cao and J. Kurths,
Second-order consensus for multiagent systems with directed topologies and nonlinear dynamics, IEEE Trans. Syst. Man Cybernetics, Part B, 40 (2010), 881-891.
doi: 10.1109/TSMCB.2009.2031624. |

















[1] |
Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic & Related Models, 2017, 10 (1) : 1-32. doi: 10.3934/krm.2017001 |
[2] |
Holly Gaff. Preliminary analysis of an agent-based model for a tick-borne disease. Mathematical Biosciences & Engineering, 2011, 8 (2) : 463-473. doi: 10.3934/mbe.2011.8.463 |
[3] |
Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020 |
[4] |
Gianluca D'Antonio, Paul Macklin, Luigi Preziosi. An agent-based model for elasto-plastic mechanical interactions between cells, basement membrane and extracellular matrix. Mathematical Biosciences & Engineering, 2013, 10 (1) : 75-101. doi: 10.3934/mbe.2013.10.75 |
[5] |
Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks & Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373 |
[6] |
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 |
[7] |
Marco Sarich, Natasa Djurdjevac Conrad, Sharon Bruckner, Tim O. F. Conrad, Christof Schütte. Modularity revisited: A novel dynamics-based concept for decomposing complex networks. Journal of Computational Dynamics, 2014, 1 (1) : 191-212. doi: 10.3934/jcd.2014.1.191 |
[8] |
Bingru Zhang, Chuanye Gu, Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs†. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061 |
[9] |
Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295 |
[10] |
Michael Gekhtman, Michael Shapiro, Serge Tabachnikov, Alek Vainshtein. Higher pentagram maps, weighted directed networks, and cluster dynamics. Electronic Research Announcements, 2012, 19: 1-17. doi: 10.3934/era.2012.19.1 |
[11] |
Domenica Borra, Tommaso Lorenzi. Asymptotic analysis of continuous opinion dynamics models under bounded confidence. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1487-1499. doi: 10.3934/cpaa.2013.12.1487 |
[12] |
Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial & Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074 |
[13] |
Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292 |
[14] |
Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393 |
[15] |
Cristina Cross, Alysse Edwards, Dayna Mercadante, Jorge Rebaza. Dynamics of a networked connectivity model of epidemics. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3379-3390. doi: 10.3934/dcdsb.2016102 |
[16] |
Rosa M. Benito, Regino Criado, Juan C. Losada, Miguel Romance. Preface: "New trends, models and applications in complex and multiplex networks". Networks & Heterogeneous Media, 2015, 10 (1) : i-iii. doi: 10.3934/nhm.2015.10.1i |
[17] |
Suoqin Jin, Fang-Xiang Wu, Xiufen Zou. Domain control of nonlinear networked systems and applications to complex disease networks. Discrete & Continuous Dynamical Systems - B, 2017, 22 (6) : 2169-2206. doi: 10.3934/dcdsb.2017091 |
[18] |
Shouying Huang, Jifa Jiang. Epidemic dynamics on complex networks with general infection rate and immune strategies. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2071-2090. doi: 10.3934/dcdsb.2018226 |
[19] |
Robert Carlson. Myopic models of population dynamics on infinite networks. Networks & Heterogeneous Media, 2014, 9 (3) : 477-499. doi: 10.3934/nhm.2014.9.477 |
[20] |
Nataša Djurdjevac Conrad, Ralf Banisch, Christof Schütte. Modularity of directed networks: Cycle decomposition approach. Journal of Computational Dynamics, 2015, 2 (1) : 1-24. doi: 10.3934/jcd.2015.2.1 |
2019 Impact Factor: 1.053
Tools
Metrics
Other articles
by authors
[Back to Top]