ACM通信
研究突出了
技术视角:网络世界中的自然算法
鸟是如何群居的，鱼是如何成群的?在一个社交网络中的个体如何达成一致，即使他们通常只受其他志同道合的个体的影响?萤火虫是如何同步闪光的?如何设计一群机器人，让它们像鸟群一样行动?
在过去的20年里，从计算机图形学到统计物理学到进化生物学，从控制理论到机器人、数学和计算机科学，这些问题占据了许多不同学科的研究人员的头脑。大部分早期的研究发生在计算机图形学和统计物理学领域，是关于集体行为的建模和模拟。在过去的十年中，焦点已经转移到严谨的理论，导致了人们可能称之为多主体系统中的集体现象理论。该理论融合了动力系统、图论、马尔可夫链和算法。
集体现象通常被建模为多自由度(离散时间或连续时间)动力系统，附加了一个附加的扭曲，即个体动力系统之间的相互连接结构变化，因为群体中每个节点的运动(或个体的意见)主要受节点的运动的影响当地社区．这里的扭曲之处在于，局部邻居不是固定的:邻居是根据系统的实际状态定义的:例如，在意见动态的情况下，社会学模型表明，个人经常受到意见接近的人的影响。换句话说，随着意见的演变，邻里结构也会随着意见的演变而变化，这就导致了两难的局面。同样地，当鸟类将它们的方向与它们的邻居聚合在一起时，它们的邻居集合也会发生变化。
当邻域结构在整个动力学演化过程中保持不变时，模型的行为就很容易分析。使用Perron-Frobenius理论，人们可以很容易地表明，由局部邻域关系引起的网络连通性实际上足以导致全局一致(在意见、群的运动方向或耦合振荡器的振荡频率方面)。我们可以将分析扩展到时变或交换网络的情况。如果网络变化是外生建模的，为了获得一致，所需要的就是确保对邻域结构进行编码的底层图保持不变随着时间的推移连接，也就是说，随着时间的推移，结果图的边的并集在任何时候都对应于一个连通图。关注邻域变化是外生的情况并非没有优点，但这样做主要是为了方便。我们如何能考虑到图对进化动力系统状态的显式依赖?这就是Bernard Chazelle的论文做出的主要贡献。
这篇论文是文献中一个独特的例外，其中内生变化被明确考虑在内，导致了一个普遍的理论的开端影响系统:其中，一个动态系统位于图节点的顶部，图的边缘作为节点状态的函数内生性地变化。这个(无疑是复杂的)动力系统的行为是什么?我们需要什么工具来分析这样的系统?这些都是这篇论文要解决的问题。事实证明，即使在最简单的情况下(图是一维几何图，更新是分段线性的)，这也不是一个容易回答的问题。
首先，沙泽勒向我们介绍了年代能源: Lyapunov函数的参数化族，表示群体伙伴之间全局失调的演化。通过对动态系统、计算几何、组合学、复杂性理论和算法的精彩体验，Chazelle创造了一种“算法微积分”扩散影响系统他令人惊讶地向我们表明，在双向情况下，这类系统的轨道或流动被吸引到一个固定点，以及几乎所有任意小的随机扰动的极限环。但是等等，还有更多的收敛时间在这两种情况下都是有界的而且边界本质上是最优的。
Chazelle开发的扩散影响系统的令人印象深刻的设置创建了一个几乎通用的设置，用于分析网络多智能体系统中涉及集体行为的各种问题，从群集、意见动态、信息聚合到同步问题。这是对此类网络系统进行的最接近于领域独立分析。总之，我们需要更多这样的工具和方法来进行研究自然的算法在一个日益网络化的世界里。为了在自然算法上取得进展，我们可能需要重新思考将教育划分为当前学术部门的竖井观点。Chazelle的工作表明，我们不能再把算法、复杂性、组合学和图从系统理论和动力系统中分离出来。
©2012 0001 - 0782/12/12 ACM
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2012 ACM, Inc.
没有发现记录