世界互联网大会

非0即1:网络中的数学

2021-05-13 10:08 来源:环球科学 作者 凯尔茜·休斯顿-爱德华兹 翻译 蔡格非 冯煜阳 杨鹏

  一个表情包如何一夜间火遍全网?一种产品是怎样闪电般地占据了整个市场?一场疾病又为何会突然全球性暴发?这类问题的答案就藏在经典的数学分支——渗流理论中。

  引言

  当你按下“发送”时,你可能以为短信会直接从自己的手机传输到朋友的手机上。事实上,长途传送信息通常需要通过蜂窝网络或互联网完成,这两种网络都依赖于集中调度的基础设施,而这些设施可能会遭到自然灾害等因素的破坏。现在,有一些应用程序正试图帮助用户与临近的手机实现直接的信息传输。这些应用程序能让加密的信息悄悄地从一部手机传到另一部,从而将发信人和收信人连接起来。换言之,这些手机以网格网络(mesh network)或自组织网络(ad hoc network)的连接方式实现了没有中心调度的灵活通信。在这样的网络中,任意两部手机进行通信时,都需要通过短距离内的相互连接来实现。那么,有一个问题出现了:在一个网格网络中,需要同城有多少人相连接,才能保证全城通信?

  1.突然的巨变

  一门名为渗流理论(percolation theory)的数学分支给了我们出人意料的答案:只需几个人就能让一切变得不同。最早加入这个通信系统的用户会构成若干互不相连的小规模网络。然而一旦用户的密度(单位面积的用户数)超过一个关键的阈值,就会突然出现能够连接远距离用户的信息通道。科学家们将网络连接性的这种快速变化描述为相变(phase transition),这一概念同样也能用来解释冰的融化或水的沸腾等物质状态的突然变化。

  渗流理论能研究在这种网格结构中随机创建或删除连接产生的后果。数学家将网格结构设想为由边(也就是线)连接顶点所形成的网络——每个顶点代表一个对象,例如电话或人,而边则代表其中两个顶点之间的特定关系。渗流理论可以追溯到20世纪50年代,它的基本观点是:随着网络中连接数量的逐渐增加,将存在无穷多个点彼此间有路径相接,或者用数学的语言来讲,一个无穷大的连通簇(infinite cluster)将会在一瞬间突然出现。

  现在,科学家正在致力于回答:这样的相变何时会发生?对于任何一个给定的网络,如何找到相当于冰在0℃融化或是水在100℃沸腾的时刻?一个表情包如何一夜间火遍全网?一种产品是怎样闪电般地占据了整个市场?一场地震在何时降临?一个手机网络如何能在刹那间实现全面连接,或者一种疾病何时开始在全球蔓延?渗流理论能提供解答这类问题的理论基础。

  数学家通常倾向于研究具有几何对称性的无限网络,因为这样便于进行理论计算。一般只有无限网络具有一瞬间发生的相变,术语称为骤然相变(sharp phase transition)。现实世界中的网络计算起来则难度较大,这些网络一般规模有限,且常常非常混乱。不过,这些网络也有相变,只是相变较为平滑。在当下的时代,各种复杂的连接使世界的联系更加紧密,例如为人们提供能源的电网,联系着人们的社交媒体,甚至是传染病的传播网络。因此,渗流理论也与我们愈加息息相关。

  2.牵一发而动全身

  1957年,英国数学家西蒙·拉尔夫·布罗德本特和约翰·迈克·哈默斯利首次将流体的滤过过程(例如油渗入多孔岩或者水渗过咖啡粉)抽象成名为渗流的纯数学问题:用一个网络来代表岩层,岩石结构中的孔隙表示为顶点,允许流体在其间流动的通道或裂缝表示为边。我们很容易想象,石油在裂缝较多的岩石中流动得更远。布罗德本特和哈默斯利通过渗流理论预测,在理想化的情形下,当裂缝的密度超过一定的阈值,石油将突然渗透到几乎整个岩层而不再仅限于一些小区域。

  地质学家曾使用渗流理论的一个版本来研究有裂缝的岩石中岩团的大小,这些研究与水力压裂法开采石油以及理解地震发生的原理息息相关。为了建立地震模型,地震学家会创建与观测到的裂缝规模和密度相匹配的渗流网络,然后根据调整不同裂缝连接起来的概率来解释应力。随着应力增加,裂缝集群扩大,地震在倏忽之间不可预测地产生。研究者可以通过调整渗流过程的参数,使缝隙愈合或是再次裂开,以模拟余震或者更长期的变化。

  渗流理论还可用于阐明更小规模的物理和化学过程。以聚合过程为例:在这个过程中,单体,也就是小而简单的分子结合在一起,形成更大的集群,称为聚合物。在渗流理论的框架中,每个单体可以作为一个节点,两个相邻的单体可能会自发地形成化学键,对应着网络中的一条边。如果它们连接的可能性不断增加,系统最终会达到渗流阈值,形成远比单体分子庞大的聚合物。这也是明胶粉溶于水能凝固形成果冻的原因。

  岩石裂缝或构成聚合物的网络极其复杂。尽管我们几乎不可能精确描述它们的结构,但布罗德本特和哈默斯利表示可以将其近似地描述成一些更加易于分析的重复图样。最简单的例子是由一个个正方形组成的格点网格,它看起来就像一张无尽的图纸:网格中顶点依次排列,并由四条边连接到邻侧的点。

  为了理解液体是如何穿过这个网格的,不妨将网格中的边想象成一条要么开放要么闭合的水管。所有水管都独立地以相同的概率开放或闭合。于是,所有或开或闭的水管将形成一个随机的网络,其中包含一些连通的区域(连通簇),所有的顶点都由一系列开放的水管连接。如果你往这种连通簇的任何一个节点中注水,那么水流就会通过那些开放的水管流到这个簇中的所有其他节点。

  渗流理论关注的就是网络的连通性,即上述的连通簇究竟有多大。但“大”是一个模糊的概念,并不容易得到形式化的数学表述,因此数学家常常用无穷大来替代那些很大的数。那么,我们讨论的核心问题就变成了:是否存在一个无穷大的连通簇?德国魏尔斯特拉斯应用分析和随机过程研究所(WIAS)的数学家贝内迪克特·雅内尔说:“对我们来说,回答‘是否存在这种簇’比回答‘有多少这种簇’,或者‘这些簇有多大’要容易得多。”

  事实上,一个无限大的网络中包含一个无穷大的连通簇(以下简称为“无穷簇”)的概率总是0或1,这是由于渗流过程会受到概率论中一个一般性理论的制约。该理论叫作零一律,由苏联数学家安德里·柯尔莫哥洛夫在20世纪30年代提出。

  零一律告诉我们,有限的改变无法干扰本质上是无限的现象。所以,在无限大的网络中找到一个无穷簇的概率必须处于某个极端的位置——不是0就是1。这一概率不会产生更细微的改变,比如从0.81变为0.82。换句话说,一个无限大的网络要么一定有一个无穷簇,要么一定没有,非此即彼。因此,将有限条水管闭合或开放,对是否存在无穷簇没有任何影响。找到无穷簇的概率要么是0,要么是1。那么到底是哪一种呢?

  3.找出阈值

  答案取决于水管开放的概率。想象你有一个用于控制这个概率的表盘。当表盘的指针转到最左端时,代表概率为0,水管总会闭合。一旦所有的管道都被关闭,灌入某个节点的水不会往任何地方流,这时找到一个无穷簇的概率为0。当你顺时针转动指针,水管开放的概率会增加,开放管道的总数也越来越多。当指针转到最右端时,该概率为1,所有水管都开放,并且灌入某一个节点的水最终会流入所有其他节点,此时找到无限簇的概率为1。

  如果你将指针缓慢地从关到开转动,管道打开的概率会逐渐增大,看起来找到无限簇的概率也会从0到1逐渐变化。但事实上,这一变化是瞬间发生的。零一律指出,该概率不会取0到1之间的值。对于正方形网格而言,存在无限簇的概率会在指针恰好处于正中央时突变,这时水管开放与闭合的概率相等。拨盘上这个关键的位置被称作渗流阈值。不论网络的形状是什么样的——例如三角网格或三维正方体网格——渗流理论的基本问题仍然相同:阈值在哪?管道开放的概率需要多大,才会有足够多的开放连接来保证无穷簇的存在?

  答案取决于无限网格网络的精确形状,而要找到它并非易事。即使要证明几乎最简单的系统——正方形网格——的阈值是1/2也是一项令人望而却步的挑战。正方形网格的这个问题最终在1980年被数学家哈利·凯斯滕解决。现在,尽管经过了数十年的努力,但我们仅能在少数极其简单的网络上精确地计算渗流阈值。“仅仅是寻找阈值就耗费了大量的工作,”密歇根大学的统计物理学家罗伯特·齐夫说,“难以想象的是,人们已经研究了这么多不同种类的系统。”齐夫整理了一个维基百科页面,记录了数百种不同网络的渗流阈值。三角网格的阈值约等于0.347,这是一个经过精确计算得出的数字,但该页面上大量的数值(包括三维正方体网格的阈值)是通过计算机模拟而得到的近似解。

  4.连通网格网络

  在物理系统中,格点网格(lattice)是很好的渗流模型。以断裂的岩石为例,孔隙的位置是固定的,但它们之间的裂缝是随机形成的。现实世界中其他的网络甚至还要复杂得多,比如前面提到的网格网络,这一网络中顶点的位置会不断变化,而其中的边,或者说连接,只有在两部手机彼此足够接近(蓝牙通信的有效范围约为10米)的情况下才能形成。类似这样的网络中,顶点可以存在于连续空间中的任何地方。因此我们需要用另一种被称作连续渗流(continuum percolation)的模型来描述它们。

  像任何数学模型一样,这种网络模型仍然进行了一定程度的简化。作为通信节点的智能手机是随机分布的,它们的位置并没有模仿自然情况下行人自动产生的集群模式;两个节点仅根据它们之间的距离进行连接,没有考虑墙壁或其他干扰源。尽管如此,该模型还是凸显了渗流理论在真实世界的网格网络中的重要作用。

  有两种方法可以增加这种连续渗流网络的连通程度:在更远的距离实现直接连接;或者增加节点数,即用户密度。这些变动都可以被理解成水管系统中那个控制表的旋钮,顺时针任意转动一下都会增加连通程度。在这些模型中,“存在一个开关,你可以‘咔嗒’一下就实现从局部到全面的连接。”雅内尔说。

  对于网格网络应用程序的设计者来说,找到渗流阈值是一个非常实际的工程问题。想要调控这个网络中的旋钮,一种方式是改变设备的功率。网格网络公司goTenna的首席科学家拉姆·拉玛纳坦说:“关键问题是,为了保证网络连接,你应该如何设定传输功率?”如果功率和连通程度存在线性关系的话,答案就相当直观了——每一次小幅增加功率都会导致连通程度按一定比例增加。但是,渗透阈值的存在意味着,随着人们的移动而断开部分连接,网络有可能会突然失去连通性。因此最佳的功率是在不浪费能源的情况下,始终保证网络的连接性。

  另一种拨动旋钮的方式是控制节点的密度。具有固定范围的网格网络需要一个用户密度的临界值,这种网络最有可能在音乐节、足球比赛等人员拥挤的活动中提供范围较广的连接。纽约布鲁克林的Red Hook等社区正在使用网格网络,他们将永久性节点固定在建筑物的顶部,从而增强互联网接入。网络中许多必要的硬件和路由技术仍在发展中,但这并不妨碍我们对未来应用的一些大胆设想,比如在无须依赖任何额外基础设施的前提下,自动驾驶车辆可以利用网格网络直接进行通信交流,分享交通状况或道路障碍的信息。

标签: 编辑:潘洁

声明:

凡注明“来源:世界互联网大会”的所有作品,版权均属于本网。稿件注明来源非本网作品,均转载自其它媒体,不代表本网观点,本网不对稿件内容真实性和图文版权负责。

关注我们