Diffusive influence systems. (English) Zbl 1323.93004
Summary: Influence systems seek to model how influence, broadly defined, spreads across a dynamic network. We build a general analytical framework which we then use to prove that, while Turing-complete, influence dynamics of the diffusive type is almost surely asymptotically periodic. In addition to resolving the dynamics of a widely used family of multiagent systems, we introduce a general renormalization method for the bifurcation analysis of multiagent systems.
MSC:
| 93A14 | Decentralized systems |
| 34H10 | Chaos control for problems involving ordinary differential equations |
| 37G15 | Bifurcations of limit cycles and periodic orbits in dynamical systems |
Keywords:
influence systems; natural algorithms; dynamical systems; dynamic networks; renormalization; limit cycles; chaosSoftware:
BoidsReferences:
| [1] | D. Acemoglu, M. A. Dahleh, I. Lobel, and A. Ozdaglar, {\it Bayesian learning in social networks}, Laboratory for Information and Decision Systems report 2780, Massachusetts Institute of Technology, Cambridge, MA, 2009. |
| [2] | R. Alur, T. A. Henzinger, and E. D. Sontag, {\it Hybrid Systems \textupIII. Verification and Control}, Lecture Notes in Comput. Sci. 1066, Springer-Verlag, Berlin, 1996. |
| [3] | D. Acemoglu, G. Como, F. Fagnani, and A. E. Ozdaglar, {\it Opinion fluctuations and disagreement in social networks}, Math. Oper. Res., 38 (2013), pp. 1-27. · Zbl 1297.91130 |
| [4] | M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna, E. Cisbani, I. Giardina, V. Lecomte, A. Orlandi, G. Parisi, A. Procaccini, M. Viale, and V. Zdravkovic, {\it Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study}, Proc. Natl. Acad. Sci. USA, 105 (2008), pp. 1232-1237. |
| [5] | A. Bhattacharyya, M. Braverman, B. Chazelle, and H. L. Nguyen, {\it On the convergence of the Hegselmann-Krause system}, in Proceedings of the 4th Innovations in Theoretical Computer Science Conference, ACM, New York, 2013, pp. 61-66. · Zbl 1361.68106 |
| [6] | V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. N. Tsitsiklis, {\it Convergence in multiagent coordination, consensus, and flocking}, in Proceedings of the 44th IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2005, pp. 2996-3000. |
| [7] | V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, {\it On the \textup2R conjecture for multi-agent systems}, in Proceedings of the European Control Conference 2007 (ECC 2007), IEEE Press, Piscataway, NJ, 2007, pp. 874-881. |
| [8] | V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, {\it On Krause’s multi-agent consensus model with state-dependent connectivity}, IEEE Trans. Automat. Control, 54 (2009), pp. 2586-2597. · Zbl 1367.93426 |
| [9] | V. D. Blondel and J. N. Tsitsiklis, {\it A survey of computational complexity results in systems and control}, Automatica, 36 (2000), pp. 1249-1274. · Zbl 0989.93006 |
| [10] | H. Bruin and J. H. B. Deane, {\it Piecewise contractions are asymptotically periodic}, Proc. Amer. Math. Soc., 137 (2009), pp. 1389-1395. · Zbl 1174.37005 |
| [11] | F. Bullo, J. Cortés, and S. Martinez, {\it Distributed Control of Robotic Networks}, Appl. Math. Ser., Princeton University Press, Princeton, NJ, 2009. · Zbl 1193.93137 |
| [12] | J. Buzzi, {\it Piecewise isometries have zero topological entropy}, Ergodic Theory Dynam. Systems, 21 (2001), pp. 1371-1377. · Zbl 0993.37012 |
| [13] | S. Camazine, J. L. Deneubourg, N. Franks, J. Sneyd, E. Bonabeau, and G. Theraulaz, {\it Self-Organization in Biological Systems}, Princeton University Press, Princeton, NJ, 2001. · Zbl 1130.92009 |
| [14] | M. Cao, D. A. Spielman, and A. S. Morse, {\it A lower bound on convergence of a distributed network consensus algorithm}, in Proceedings of the 44th IEEE Conference on Decision and Control/European Control Conference 2005, IEEE Press, Piscataway, NJ, 2005, pp. 2356-2361. |
| [15] | C. Castellano, S. Fortunato, and V. Loreto, {\it Statistical physics of social dynamics}, Rev. Modern Phys., 81 (2009), pp. 591-646. |
| [16] | E. Catsigeras and R. Budelli, {\it Topological dynamics of generic piecewise continuous contractive maps in \(n\) dimensions}, Internat. J. Pure Appl. Math., 68 (2011), pp. 61-83. · Zbl 1225.37019 |
| [17] | B. Cessac, {\it A discrete time neural network model with spiking neurons: Rigorous results on the spontaneous dynamics}, J. Math. Biol., 56 (2008), pp. 311-345. · Zbl 1145.37342 |
| [18] | B. Chazelle, {\it The convergence of bird flocking}, J. ACM, to appear; available online at arXiv: 0905.4241v1. · Zbl 1321.92080 |
| [19] | B. Chazelle, {\it The total \(s\)-energy of a multiagent system}, SIAM J. Control Optim., 49 (2011), pp. 1680-1706. · Zbl 1226.93007 |
| [20] | B. Chazelle, {\it Natural algorithms and influence systems}, Comm. ACM, 55 (2012), pp. 101-110. |
| [21] | G. E. Collins, {\it Quantifier elimination for real closed fields by cylindrical algebraic decomposition}, in Automata Theory and Formal Languages (2nd GI conference), Springer-Verlag, New York, 1975, pp. 134-183. · Zbl 0318.02051 |
| [22] | L. Conradt and T. J. Roper, {\it Group decision making in animals}, Nature, 421 (2003), pp. 155-158. |
| [23] | F. Cucker and S. Smale, {\it Emergent behavior in flocks}, IEEE Trans. Automat. Control, 52 (2007), pp. 852-862. · Zbl 1366.91116 |
| [24] | R. L. Devaney, {\it An Introduction to Chaotic Dynamical Systems}, 2nd ed., Westview Press, Boulder, CO, 2003. · Zbl 1025.37001 |
| [25] | J. C. Dittmer, {\it Consensus formation under bounded confidence}, Nonlinear Anal., 47 (2001), pp. 4615-4622. · Zbl 1042.91567 |
| [26] | M. G. Earl and S. H. Strogatz, {\it Synchronization in oscillator networks with delayed coupling: A stability criterion}, Phys. Rev. E, 67 (2003), 036204. |
| [27] | V. Gazi and K. M. Passino, {\it Stability analysis of swarms}, IEEE Trans. Automat. Control, 48 (2003), pp. 692-697. · Zbl 1365.92143 |
| [28] | R. Hegselmann and U. Krause, {\it Opinion dynamics and bounded confidence: Models, analysis, and simulation}, J. Artificial Societies and Social Simulation, 5 (2002), 3. |
| [29] | R. Hegselmann and U. Krause, {\it Truth and cognitive division of labour: First steps towards a computer aided social epistemology}, J. Artificial Societies and Social Simulation, 9 (2006), 3. |
| [30] | J. M. Hendrickx and V. D. Blondel, {\it Convergence of different linear and non-linear Vicsek models}, in Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS2006), 2006, pp. 1229-1240. |
| [31] | A. Jadbabaie, J. Lin, and A. S. Morse, {\it Coordination of groups of mobile autonomous agents using nearest neighbor rules}, IEEE Trans. Automat. Control, 48 (2003), pp. 988-1001. · Zbl 1364.93514 |
| [32] | P. Koiran, M. Cosnard, and M. Garzon, {\it Computability with low-dimensional dynamical systems}, Theoret. Comput. Sci. A, 132 (1994), pp. 113-128. · Zbl 0821.68053 |
| [33] | U. Krause, {\it A discrete nonlinear and non-autonomous model of consensus formation}, in Communications in Difference Equations, Gordon and Breach, Amsterdam, 2000, pp. 227-236. · Zbl 0988.39004 |
| [34] | B. Kruglikov and M. Rypdal, {\it A piecewise affine contracting map with positive entropy}, Discrete Contin. Dyn. Systems, 16 (2006), pp. 393-394. · Zbl 1108.37013 |
| [35] | S. Kurz and J. Rambau, {\it On the Hegselmann-Krause conjecture in opinion dynamics}, J. Difference Equ. Appl., 17 (2011), pp. 859-876. · Zbl 1216.91023 |
| [36] | J. Lorenz, {\it Multidimensional opinion dynamics when confidence changes}, in Economic Complexity, Aix-en-Provence, 2003. |
| [37] | J. Lorenz, {\it A stabilization theorem for dynamics of continuous opinions}, Phys. A, 355 (2005), pp. 217-223. |
| [38] | J. Lorenz, {\it Bounds of confidence: Meet, discuss and find consensus!}, Complexity, 4 (2010), pp. 43-52. |
| [39] | S. Martinez, F. Bullo, J. Cortés, and E. Frazzoli, {\it On synchronous robotic networks–Part II: Time complexity of rendezvous and deployment algorithms}, IEEE Trans. Automat. Control, 52 (2007), pp. 2214-2226. · Zbl 1366.93389 |
| [40] | R. E. Mirollo and S. H. Strogatz, {\it Synchronization of pulse-coupled biological oscillators}, SIAM J. Appl. Math., 50 (1990), pp. 1645-1662. · Zbl 0712.92006 |
| [41] | A. Mirtabatabaei and F. Bullo, {\it Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems}, SIAM J. Control Optim., 50 (2012), pp. 2763-2785. · Zbl 1258.91191 |
| [42] | L. Moreau, {\it Stability of multiagent systems with time-dependent communication links}, IEEE Trans. Automat. Control, 50 (2005), pp. 169-182. · Zbl 1365.93268 |
| [43] | A. Nedic, A. Olshevsky, A. E. Ozdaglar, and J. N. Tsitsiklis, {\it On distributed averaging algorithms and quantization effects}, IEEE Trans. Automat. Control, 54 (2009), pp. 2506-2517. · Zbl 1367.93405 |
| [44] | A. Okubo and S. A. Levin, {\it Diffusion and Ecological Problems}, 2nd ed., Springer, New York, 2002. · Zbl 1027.92022 |
| [45] | A. Olshevsky and J. N. Tsitsiklis, {\it Convergence speed in distributed consensus and averaging}, SIAM J. Control Optim., 48 (2009), pp. 33-55. · Zbl 1182.93008 |
| [46] | J. K. Parrish and W. M. Hamner, {\it Animal Groups in Three Dimensions}, Cambridge University Press, Cambridge, UK, 1997. |
| [47] | A. Papachristodoulou and A. Jadbabaie, {\it Synchronization in oscillator networks: Switching topologies and non-homogeneous delays}, in Proceedings of the 44th IEEE Conference on Decision and Control/European Control Conference, IEEE Press, Piscataway, NJ, 2005, pp. 5692-5697. |
| [48] | A. Pikovsky, M. Rosenblum, and J. Kurths, {\it Synchronization: A Universal Concept in Nonlinear Sciences}, Cambridge University Press, Cambridge, UK, 2001. · Zbl 0993.37002 |
| [49] | C. W. Reynolds, {\it Flocks, herds, and schools: A distributed behavioral model}, Comput. Graphics, 21 (1987), pp. 25-34. |
| [50] | M. Roozbehani, A. Megretski, and E. Frazzoli, {\it Lyapunov analysis of quadratically symmetric neighborhood consensus algorithms}, in Proceedings of the 47th IEEE Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2008, pp. 2252-2257. |
| [51] | L. Scardovi, A. Sarlette, and R. Sepulchre, {\it Synchronization and balancing on the N-torus}, Systems Control Lett., 56 (2007), pp. 335-341. · Zbl 1111.68007 |
| [52] | H. T. Siegelmann and E. D. Sontag, {\it On the computational power of neural nets}, J. Comput. System Sci., 50 (1995), pp. 132-150. · Zbl 0826.68104 |
| [53] | E. D. Sontag, {\it Nonlinear regulation: The piecewise linear approach}, IEEE Trans. Automat. Control, 26 (1981), pp. 346-358. · Zbl 0474.93039 |
| [54] | D. A. Spielman and S. Teng, {\it Smoothed analysis: Why the simplex algorithm usually takes polynomial time}, J. ACM, 51 (2004), pp. 385-463. · Zbl 1192.90120 |
| [55] | S. H. Strogatz, {\it From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators}, Phys. D, 143 (2000), pp. 1-20. · Zbl 0983.34022 |
| [56] | J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, {\it Distributed asynchronous deterministic and stochastic gradient optimization algorithms}, IEEE Trans. Automat. Control, 31 (1986), pp. 803-812. · Zbl 0602.90120 |
| [57] | T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, {\it Novel type of phase transition in a system of self-driven particles}, Phys. Rev. Lett., 75 (1995), pp. 1226-1229. |
| [58] | T. J. Walker, {\it Acoustic synchrony: Two mechanisms in the snowy tree cricket}, Science, 166 (1969), pp. 891-894. |
| [59] | A. T. Winfree, {\it Biological rhythms and the behavior of populations of coupled oscillators}, J. Theoret. Biol., 16 (1967), pp. 15-42. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
