AF: Small: An Algorithmic Approach to Collective Behavior

该提案试图从“算法”的角度来回答关于集体行为的基本问题。 所考虑的系统由相互通信的代理组成，并根据沿着收集的信息采取自主行动。 代理人可以是社会网络的成员，成群的鸟类，闪烁的萤火虫，成群的细菌等，在所有情况下，代理人都配备了自己的（可能是不同的）决策程序，告诉他们在什么条件下做什么，听什么代理人。在这种多样性的局部相互作用中，往往会出现惊人的模式：鸟类会形成三角形;萤火虫会达到完美的同步;细菌会进行群体感应。如何研究这种涌现的自组织呢？这项工作的前提是，集体行为的算法方法拥有独特的新颖和强大的攻击线的承诺。研究复杂系统的传统工具主要来自动力学和统计物理学领域。PI的算法方法将分三个阶段展开。一个是发展将复杂系统分解为简单系统的一般方法。正如图聚类技术是网络分析工具包的重要组成部分一样，“重正化”方法对于分析自组织和集体涌现至关重要。该项目的第二阶段需要为动态网络和时变随机游走设计新的工具。第三阶段是研究集体行为的特定模型，特别是群集和意见动态的经典系统。那里的挑战是分类这些系统的动态政权（有吸引力的，周期性的，混乱的，图灵普遍的，等）。更广泛的影响，包括在这个跨学科领域的课程开发和研究在各级的推广介绍。

This proposal seeks to answer fundamental questions about collective behavior by attacking them from an "algorithmic" perspective. The systems under consideration consist of agents communicating with one another and taking autonomous actions based on the information gathered along the way. The agents could be members of a social network, flocking birds, flashing fireflies, swarming bacteria, etc. In all cases, agents are equipped with their own (possibly distinct) decision procedures that tell them what to do under what conditions and what agents to listen to. Out of this diversity of local interactions, striking patterns will often emerge: birds will form triangles; fireflies will reach perfect synchronization; bacteria will perform quorum sensing. How does one study emergent self-organization of this sort? The premise of this work is that an algorithmic approach to collective behavior holds the promise of a uniquely novel and powerful line of attack. The traditional tools for the study of complex systems draw mostly from the fields of dynamics and statistical physics. The PI's algorithmic approach will unfold in three phases. One is to develop general methods for decomposing complex systems into simpler ones. Just as graph clustering techniques are essential parts of the toolkit of network analysis, so "renormalization" methods are crucial for the analysis of self-organization and collective emergence. The second phase of this project entails the design of new tools for dynamic networks and time-varying random walks. The third phase is to investigate specific models of collective behavior, in particular classical systems for swarming and opinion dynamics. The challenge there is to classify the dynamic regimes of these systems (attractive, periodic, chaotic, Turing-universal, etc).Broader impacts include curriculum development on this inter-disciplinary field and outreach presentations of the research at all levels.