漫步的蚂蚁如何激发出更好的网络算法

文章：Larry SuffeSty

事实证明，蚂蚁真的很擅长很多事情 - 而不仅仅是举起和沟通。似乎蚂蚁也有整个投票的事情，可以选择新的巢穴到科学。生物学家长期以来怀疑蚂蚁基于它们的人口密度估计，在随机探索其环境的同时，它们对其实际上撞到其他蚂蚁的频率。

这种长期研究的能力最近得到了麻省理工学院计算机科学和人工智能实验室(CSAIL)研究人员的新支持，他们创造了一种算法，在计算机中复制蚂蚁的行为，证明它可以准确地预测网络的种群密度。

"It’s intuitive that if a bunch of people are randomly walking around an area, the number of times they bump into each other will be a surrogate of the population density," said Cameron Musco, an MIT graduate student in electrical engineering and computer science and a co-author on the new paper. "What we’re doing is giving a rigorous analysis behind that intuition, and also saying that the estimate is a very good estimate, rather than some coarse estimate. As a function of time, it gets more and more accurate, and it goes nearly as fast as you would expect you could ever do."

随机散步

Musco and his co-authors—his advisor, NEC Professor of Software Science and Engineering Nancy Lynch, and Hsin-Hao Su, a postdoc in Lynch’s group—characterise an ant’s environment as a grid, with some number of other ants scattered randomly across it. The ant of interest—call it the explorer—starts at some cell of the grid and, with equal probability, moves to one of the adjacent cells. Then, with equal probability, it moves to one of the cells adjacent to that one, and so on. In statistics, this is referred to as a “random walk.” The explorer counts the number of other ants inhabiting every cell it visits.

在纸质中，研究人员将随机步行与随机采样进行比较，其中，从网格中随机选择小区，并且计算的蚂蚁数量。两种方法的准确性随着每个额外的样本而改善，但显着地，随机步道几乎与随机抽样一样快地收敛于真正的人口密度。

这很重要，因为在许多实际情况下，随机抽样不是一个选择。例如，假设您希望编写算法来分析在线社交网络 - 说，估计网络自我描述的一部分作为共和党。网络成员没有公开名单;探索它的唯一方法是选择一个单独的成员并开始跟踪连接。

类似地，在自组织网络中，一个给定的设备只知道其邻近设备的位置;它并不知道整个网络的布局。一个使用随机漫步来聚合来自多个设备的信息的算法将比一个必须将网络作为一个整体来描述的算法更容易实现。

Musco说，他和他的同事最初认为，这是一个估计人口密度的算法必须克服的不利条件。但是他们过滤过采样数据的尝试似乎使算法的性能恶化，而不是改善。最终，他们从理论上解释了原因。

穆斯科说:“如果你在一个网格中随机行走，你不可能碰到每一个人，因为你不可能穿过整个网格。”“所以有个人在电网的另一边，我几乎有百分之零的几率撞到他。虽然我遇到这些人的机会少了，但我遇到当地人的机会多了。我需要计算我和当地人的所有互动来弥补那些遥远的人我永远不会碰到的事实。这是完全平衡的。这真的很容易证明，但不是很直观，所以我们花了一段时间才意识到这一点。”

用于模拟蚂蚁环境的研究人员的网格只是一个称为图形的数据结构的特殊实例。图表由节点组成，通常由圆形表示，并且边缘，通常表示为连接节点的线段。在网格中，每个单元格是节点，并且它只共享边缘，只与紧接在其相邻的那些单元。

但是该技术适用于任何图形，例如描述社交网络的哪个成员连接的一个图表，或者在ad hoc网络中的哪些设备在彼此的通信范围内。

“如果他们是机器人而不是蚂蚁，他们就可以通过互相交谈并说'哦，这是我的估计，”这是我的估计“。”