AF: Small: Natural Algorithms and Dynamic Networks

从局部相互作用中出现大规模秩序是计算和生活系统的共同主题。自然算法领域试图发现这种现象背后的基本原理，这些原理具有惊人的多样性。简单的算法规则能解释鸟类如何成群、白蚁如何合作、观点如何两极分化、振荡器如何自同步、语言如何通过迭代学习进化，或者自适应系统如何产生健壮性？除了为这些具体问题提供答案外，该项目更广泛的雄心是在算法和动力系统领域之间架起桥梁。几乎所有考虑的过程都涉及动态网络，其节点代表在时变拓扑下交互的自治代理。通常，以尊重动态的方式对此类系统执行降维是至关重要的。这项任务是通过“语义重整化”的镜头来实现的，这是一个涉及到对动态图形进行分层聚类的过程。该项目的主题是高度多学科的，并形成了研究生研讨会和本科生项目的基础，参与的学科包括计算机科学、数学、统计学、神经科学、基因组学、进化生物学和机械工程。该项目利用了动力系统、机器学习、统计力学和网络理论等多个领域的广泛技术。它由四个主要部分组成：(A)“迭代学习”特征是学生作为贝叶斯主体，从教师那里学习，然后成为教师自己；(B)“动态随机行走”模型通过反馈环在拓扑随时间变化的图上随机行走；(C)“观点动力学”研究自主主体如何通过相互的、受限的交互来达成共识；(D)“平均系统”是由嵌入式动态网络上的凸组合更新驱动的耦合动态系统。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The emergence of large-scale order from local interactions is a theme common to computing and living systems. The field of natural algorithms seeks to discover the fundamental principles that underlie this phenomenon in all its remarkable diversity. Can simple algorithmic rules explain how birds flock, how termites cooperate, how opinions polarize, how oscillators self-synchronize, how languages evolve through iterated learning, or how robustness emerges from adaptive systems? Beyond providing answers to these specific questions, the broader ambition of this project is to build bridges between the fields of algorithms and dynamical systems. Nearly all of the processes under consideration involve dynamic networks whose nodes represent autonomous agents interacting under time-varying topologies. It is often crucial to perform dimension reduction on such systems in a manner respectful of the dynamics. This task is approached through the lens of “semantic renormalization,” a process that involves clustering dynamic graphs hierarchically. The theme of the project is highly multidisciplinary and forms the basis of graduate seminars and undergraduate projects with participation from computer science, mathematics, statistics, neuroscience, genomics, evolutionary biology, and mechanical engineering. The project draws upon a wide range of techniques from areas as diverse as dynamical systems, machine learning, statistical mechanics, and network theory. It consists of four main parts: (a) “iterated learning” features students who, acting as Bayesian agents, learn from teachers and then, in turn, become teachers themselves; (b) “dynamic random walks” model random walks over graphs whose topology changes over time via a feedback loop; (c) “opinion dynamics” investigates how autonomous agents can reach consensus through mutual, constrained interaction; (d) “averaging systems” are coupled dynamical systems driven by convex combination updates over embedded dynamic networks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.