Bernard Chazelle
Abstract
Algorithms offer a rich, expressive language for modelers of biological and social systems. They lay the grounds for numerical simulations and, crucially, provide a powerful framework for their analysis. The new area of natural algorithms may reprise in the life sciences the role differential equations have long played in the physical sciences. For this to happen, however, an "algorithmic calculus" is needed. We discuss what this program entails in the context of influence systems, a broad family of multiagent models arising in social dynamics.
- Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z. A biological solution to a fundamental distributed computing problem. Science 331 (2011), 183--185.Google Scholar
Cross Ref
- Bonifaci, V., Mehlhorn, K., Varma, G. Physarum can compute shortest paths. In Proceedings of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012), 233--240. Google ScholarDigital Library
- Camazine, S., Deneubourg, J.L., Franks, N., Sneyd, J., Bonabeau, E., Theraulaz, G. Self-Organization in Biological Systems, Princeton University Press, 2001. Google ScholarDigital Library
- Chazelle, B. The convergence of bird flocking, arXiv:0905.4241vl, 2009. Prelim, version in Proceedings of SIAM SODA 2009, with improvements in Proceedings of ACM SoCG 2010.Google Scholar
- Chazelle, B. The total s-energy of a multiagent system, SIAM J. Control Optim. 49 (2011), 1680--1706.Google ScholarCross Ref
- Chazelle, B. The dynamics of influence systems, arXiv:1204.3946v2, 2012. Prelim, version in Proceedings of 53rd FOCS, 2012. Google ScholarDigital Library
- Collins, G. E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Proceedings of 2nd GI Conference on Automata Theory and Formal Languages (1975), Springer-Verlag, New York, 134--183. Google ScholarDigital Library
- Cucker, F., Smale, S. Emergent behavior in flocks. IEEE Trans. Automatic Control 52 (2007), 852--862.Google ScholarCross Ref
- Fisher, J., Harel, D., Henzinger, T.A. Biology as reactivity. Commun. ACM 54 (2011), 72--82. Google ScholarDigital Library
- Hegselmann, R., Krause, U. Opinion dynamics and bounded confidence models, analysis, and simulation. J. Artif. Soc. Soc. Simulat. 5 (2002), 3.Google Scholar
- Hegselmann R, Krause U. Truth and cognitive division of labor: first steps towards a computer aided social epistemology. J. Artif. Soc. Soc. Simulat. 9 (2006).Google Scholar
- Hendrickx, J.M., Blondel, V.D. Convergence of different linear and non-linear Vicsek models. In Proceedings of 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS2006) (July 2006, Kyoto, Japan), 1229--1240.Google Scholar
- Jadbabaie, A., Lin, J., Morse, A.S. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automatic Control 48 (2003), 988--1001.Google ScholarCross Ref
- Lorenz, J. A stabilization theorem for dynamics of continuous opinions. Phys. Stat. Mech. Appl. 355 (2005), 217--223.Google ScholarCross Ref
- Lynch, N.A. Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996. Google ScholarDigital Library
- Moreau, L. Stability of multiagent systems with time-dependent communication links. IEEE Trans. Automatic Control 50 (2005), 169--182.Google ScholarCross Ref
- Navlakha, S., Bar-Joseph, Z. Algorithms in nature: the convergence of systems biology and computational thinking. Mol. Syst. Biol. 7 (2011), 546.Google ScholarCross Ref
- Okubo, A., Levin, S.A. Diffusion and Ecological Problems, 2nd edn, Springer, 2002.Google Scholar
- Parrish, J.K., Hamner, W.M. Animal Groups in Three Dimensions, Cambridge University Press, 1997.Google ScholarCross Ref
- Prusinkiewicz, P., Lindenmayer, A., Hanan, J.S., Fracchia, F.D. The Algorithmic Beauty of Plants, Springer-Verlag, 1996. Google ScholarDigital Library
- Reynolds, C.W. Flocks, herds, and schools: a distributed behavioral model. Comput. Graph. 21 (1987), 25--34. Google ScholarDigital Library
- Seneta, E. Non-Negative Matrices and Markov Chains, 2nd edn, Springer, 2006.Google Scholar
- Strogatz, S.H. From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators. Physica D 143 (2000), 1--20. Google ScholarDigital Library
- Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., Shochet, O. Novel type of phase transition in a system, of self-driven particles. Phys. Rev. Lett. 75 (1995), 1226--1229.Google ScholarCross Ref
- Winfree, A.T. Biological rhythms and the behavior of populations of coupled oscillators. J. Theoret. Biol. 16, 1 (1967), 15--42.Google ScholarCross Ref
Index Terms
- Natural algorithms and influence systems
Recommendations
Models and algorithms for social influence analysis
WSDM '13: Proceedings of the sixth ACM international conference on Web search and data miningSocial influence is the behavioral change of a person because of the perceived relationship with other people, organizations and society in general. Social influence has been a widely accepted phenomenon in social networks for decades. Many applications ...
Peirce's rule in natural deduction
In stark contrast to Natural Deduction for Intuitionistic Logic, Natural Deduction for Classical Logic suffers from some well-known limitations: although normalisation can be proved, the standard proof of Prawitz (Natural deduction. A proof Theoretical ...
Unification Algorithms for Eliminating and Introducing Quantifiers in Natural Deduction Automated Theorem Proving
A natural deduction system was adapted from Gentzen system. It enables valid wffs to be deduced in a very ‘natural’ way. One need not transform a formula into other normal forms. Robinson’s unification algorithm is used to handle clausal formulas. ...
Comments