Barabási组最新Nature封面文章：复杂网络如何3D打印？

原创任晓龙集智俱乐部

采用新提出的3D空间布局模型的两个网络，经3D打印之后的实物图。左：BA网络模型，右：ER网络模型

导语

3D打印复杂网络，不仅是技术，更是艺术。近期Nature杂志以封面文章的形式发表了以复杂网络巨擘 Albert-László Barabási为通讯作者，Dehmamy为第一作者的研究成果[1]，详细讨论了在真实世界中，网络的节点和边所占据的体积、大小不能忽略的情况下，如何在3D空间上对网络进行布局。

论文题目：
A structural transition in physical networks
论文地址：
https://www.nature.com/articles/s41586-018-0726-6

自从1736年欧拉解决柯尼斯堡七桥问题，并创立图论，以及最近几十年复杂网络的研究热潮兴起以来，大多数的研究都基于对现实世界的复杂系统进行抽象，构建相应的图或网络进行理论研究。

而这篇论文反其道而行，探索了如何将比较抽象的网络还原到真实世界中去，着重探索了2D空间的网络在3D空间中的布局问题。通过这篇文章你会发现，如果以前的研究是科学与技术，那么，网络在3D空间中的布局问题，简直就是一种艺术！

Fake News Network 来源: [3]

2D网络局限性

长期以来，为了让理论研究变得简洁方便，我们通常会把实体的复杂系统抽象成网络（或图）的结构——即把系统中的实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，称为边。这样的网络中，节点与边的位置及大小可以随意移动和调整。这给了理论研究非常大的灵活性。如下图中2D布局迥异的两个图实际上拥有相同的结构（即图同构[2]）。

但在实际的一些应用研究中，这种简洁的抽象网络也会存在很大的缺陷。比如，在研究大脑中神经元网络的结构与功能、蛋白质相互作用，3D集成电路等一些网络时，不仅要考虑节点与边的大小、粗细等属性，还要考虑他们的空间3D布局。更严格一点，若要求所构建的复杂系统的边不能有交叉或重叠（overlap），则以前简洁抽象的网络模型就难以直接在现实中使用。

研究表明，当网络中节点的大小和边的粗细不可忽略时，随着节点越来越大，边越来越粗，网络会显得愈加“拥挤”，网络中点边之间的穿插情况会越来越多。如下图所示，在一个20个节点的BA网络中，随着边越来越粗，发生穿插的边数越来越多。由于网络的有限性，在最后阶段发生穿插的边数会趋于稳定。

显然，穿插状况频发的网络在实际应用中（比如3D打印）会有很大局限性，会影响系统的几何结构、演化与动力学功能。

如何避免互相穿插

Dehmamy等人研究了不可穿插条件（non-crossing conditions）如何影响网络的实际结构[1]，特别是如何影响网络中所有边的长度——在实际的复杂系统中，边长越长往往意味着系统成本越高。

Fig.1 (a) 将网络中的的边抽象为可拉伸的塑料圆柱，圆柱内相当于有很多个小弹簧连接在一起。

Dehmamy等人将节点抽象为塑料圆球，边抽象为一个塑料圆柱。这样，边不必保持笔直，节点也不必保持标准的圆球形状，而是可以发生形变。边（或点）通过形变，避免结构上的穿插（如Fig. 1(b) 所示）。

Fig.1(b) 有6个节点的一个网络示意图。

图中几个模型的区别是：

FDL (force-directed layout)中，边-边相互作用的弹性势能=0 (即边不可弯曲)；
ELI (elastic-link model)：节点位置固定，边可以弯曲；
FUEL (fully elastic model)：节点位置可调整，边可以弯曲。其中，发生穿插的边用红色表示了出来。

每条边在发生形变时，每条边受到内部的弹力作用和外部的斥力作用（如Fig. 1(a) 所示）。基于此，作者借用自回避聚合物链（self-avoiding polymer chains）和流形动力学（manifold dynamics）中常用的势能计算方法，定义了网络发生形变之后的总势能V，包括：网络中所有边的总弹性势能，点-点相互作用的弹性势能，边-边相互作用的弹性势能，以及点-边相连产生的势能。

作者认为，当网络的总势能V最小时，网络的总边长最小。要让网络总势能最小，可以将产生形变的网络浸入高粘度介质中，让网络相对稳定地、慢慢地松弛到低能状态，此时便得到了在不可穿插条件下，网络的边长总和最短时的网络结构。

然而，求解全局最小总势能是NP hard问题，所以Dehmamy等人用模拟退火算法寻找局部最优解，结果如Fig. 1(c) 所示。

Fig.1(c)是采用模拟退火算法求解在不可穿插条件下，网络中边长最短时的网络布局的结果。

当调整网络中边的粗细的时候，可以发现(a) 网络中穿插的边数随着塑料圆筒半径r_L的增长而线性增长; (b)在塑料圆筒的半径r_L较小的时候，网络的总边长与圆筒半径的大小无关；(c) 在塑料圆筒的半径r_L较小的时候，网络中的边的曲率变化不是很明显。

这些结果说明，在边的半径比较小的时候，即弱连接情况下(the weakly interacting regime)，边只需要非常小的调整，便可以避免相互穿插。这和我们在网络可视化中经常遇到的情形很像。

强弱连接影响网络3D布局与功能

然而，上图结果也表明，当边的半径超过一个临界值，即强连接情况下(the strongly interacting regime), 一切都会不同。由于边的半径比较大，为了避免边之间的穿插，网络中的边往往不得不在有限的空间内蜿蜒起伏，“在夹缝中求生存”，如图Fig. 2 (f), (g)所示。并且，在半径较大的时候，网络的总边长不再与半径无关，而是随着半径的增长而线性增长。

既然强连接和弱连接情况下的网络布局如此不同，很自然的一个问题就是，当边的半径是多少的时候，网络是强/弱连接的？

作者通过计算得出，当网络的边的半径与节点的半径的比值小于N^-6时，网络是弱连接的情况(the weakly interacting regime)，其中，N是网络中的节点数。当N趋于无穷时，，即在热力学极限下，网络不存在弱连接的情况！并且，这一结果与网络的类型、网络度分布、网络的规模无关。