# American Institute of Mathematical Sciences

September  2020, 15(3): 489-517. doi: 10.3934/nhm.2020028

## 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

Received  December 2019 Revised  July 2020 Published  September 2020 Early access  September 2020

Fund Project: The second author wishes to thank Benedetto Picolli for helpful discussions

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.

Citation: 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
##### 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). [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). [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. [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). [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). [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. [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.
The movement of an agent according to the bounded confidence dynamics (2.3)
Simulation of the opinion dynamics without and with control (resp. left and right figure), e.g. solving resp. (2.3) and Model 1 with $r_{*} = \frac12$. With the control (right), the dynamics converge to a consensus
Illustration of the critical regions (3.1) in $\mathbb{R}$ (interval behind ${\bf x}_i$) and $\mathbb{R}^2$ (semi-annulus region). The opinion ${\bf x}_i$ is attracted toward the local average $\overline{\bf x}_i$ and hence moves with velocity $\overline{\bf x}_i-{\bf x}_i$. In the "No-left behind dynamics" (1), ${\bf x}_i$ can only move only if there is no one in its critical region $\mathcal{B}_i$. Thus, ${\bf x}_i$ freezes whereas ${\bf x}_j$ is free to move in the left illustration
A configuration of agents (top) and the resulting interaction graph (edge set E, black) and behind graph (edge set $E^{\mathcal{B}})$, light blue). Note that the behind graph is a directed subgraph of the interaction graph
Counter-example in multi-dimension. Blue arrow is the velocity of each cluster. In this setting, every agent has someone in its critical region $\mathcal{B}_i$. Thus, the naive control in Model 1 would prevent anyone from moving
The velocity of agent $i$ is the projection of the desired velocity $\overline{\bf x}_i-{\bf x}_i$ onto the cone of admissible velocity $\mathcal{C}_{i}$
2D simulation of opinion dynamics without and with control (resp, top and bottom figure), e.g. solving resp. (1) and (3.5) with $r_* = \frac12$. With the control (bottom), the dynamics converge to a consensus
Preserving connectivity does not imply the convergence to a consensus. Here, when $r_* = 1$, the extreme points $x_1$ and $x_4$ will converge towards $x_2$ and $x_3$ respectively. However, $x_2$ and $x_3$ cannot move since $x_1$ and $x_4$ are always in their respective critical regions
The convex hull $\Omega(t_n)$ has to converge to a limit configuration $\Omega^\infty$. The dynamics converge to a consensus if $\Omega^\infty$ is reduced to a single point which we prove by contradiction. We distinguish three cases of limit configuration $\Omega^\infty$ depending on if the extreme point ${\bf x}_p^\infty$ has a so-called extreme neighbor $j$, i.e. $\|{\bf x}_p^\infty-{\bf x}_j^\infty\| = 1$
If the limit configuration $\{{\bf x}_k^\infty\}_k$ is not a consensus, the extreme point ${\bf x}_p(t_n)$ will eventually get inside the convex hull $\Omega^\infty$ which gives a contradiction
Situation in the case 2. The extreme point $x_p$ needs $x_{p_2}$ the neighbor of its neighbor $x_{p_1}$ to be pushed further to the right
The decay of the diameter $d(t)$ is first linear and then exponential after the diameter $d(t)$ becomes less than $1$
Left: diameter $d(t)$ over time for $100$ realizations (quantile representation). Right: stopping time $\tau$ (4.28) depending on the size of the critical region $r_*$
An example of how the behind graph can be relaxed while still ensuring that the interaction graph remains connected. The interaction graph is represented by undirected and directed edges, the behind graph is represented by only the blue directed edges. Agent 3 is in the behind region of both agent 2 and agent 4 and agents 2 and 4 are connected in the interaction graph therefore we may remove the edge from agent 4 to agent 3
The NOLB dynamics do not allow the red agent to disconnect from the blue agent (illustrated with a purple chain). The RNOLB dynamics allow this disconnection to occur but maintain connectivity of the whole configuration
The RNOLB dynamics can be seen as an interpolation between NOLB and bounded confidence
Diameter, $d(t)$ over time for 100 realizations of the RNOLB dynamics (quantile representation)
 [1] Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic and 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 and Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020 [4] Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks and Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373 [5] 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 [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 and Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061 [9] 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 [10] 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 [11] Domenica Borra, Tommaso Lorenzi. Asymptotic analysis of continuous opinion dynamics models under bounded confidence. Communications on Pure and 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 and Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074 [13] Prateek Kunwar, Oleksandr Markovichenko, Monique Chyba, Yuriy Mileyko, Alice Koniges, Thomas Lee. A study of computational and conceptual complexities of compartment and agent based models. Networks and Heterogeneous Media, 2022, 17 (3) : 359-384. doi: 10.3934/nhm.2022011 [14] Cristina Cross, Alysse Edwards, Dayna Mercadante, Jorge Rebaza. Dynamics of a networked connectivity model of epidemics. Discrete and Continuous Dynamical Systems - B, 2016, 21 (10) : 3379-3390. doi: 10.3934/dcdsb.2016102 [15] 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 [16] Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393 [17] Rosa M. Benito, Regino Criado, Juan C. Losada, Miguel Romance. Preface: "New trends, models and applications in complex and multiplex networks". Networks and Heterogeneous Media, 2015, 10 (1) : i-iii. doi: 10.3934/nhm.2015.10.1i [18] 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 [19] Robert Carlson. Myopic models of population dynamics on infinite networks. Networks and Heterogeneous Media, 2014, 9 (3) : 477-499. doi: 10.3934/nhm.2014.9.477 [20] Suoqin Jin, Fang-Xiang Wu, Xiufen Zou. Domain control of nonlinear networked systems and applications to complex disease networks. Discrete and Continuous Dynamical Systems - B, 2017, 22 (6) : 2169-2206. doi: 10.3934/dcdsb.2017091

2020 Impact Factor: 1.213