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空间中的布局问题,简直就是一种艺术!

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

Fake News Network 来源: [3]

2D网络局限性

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

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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

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

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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

如何避免互相穿插

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

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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

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

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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) 所示。

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

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

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

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

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

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

作者通过计算得出,当网络的边的半径与节点的半径的比值Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部小于N^-6时,网络是弱连接的情况(the weakly interacting regime),其中,N是网络中的节点数。当N趋于无穷时,Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部即在热力学极限下,网络不存在弱连接的情况!并且,这一结果与网络的类型、网络度分布、网络的规模无关。

也就是说,当网络节点较多时,传统的网络布局/可视化方法由于不考虑边的粗细,且边大多数情况下保持笔直,会让网络充斥着大量交叉着的边,难以在实际应用中使用。

最后,作者通过柯西应力张量(Cauchy stress tensor)计算了弱连接情况和强连接情况下,网络单位面积所承受的作用力。

在弱连接情况下,网络中的边比较细且几乎保持着笔直的状态,系统中的势能主要为点-点相互作用的弹性势能,以及点-边相连产生的势能。面对外部压力时,网络表现得更像固体(如图Fig. 3 (a)所示)。

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

在强连接情况下,网络中的边比较粗且蜿蜒曲折,几乎占据了整个网络布局的大部分体积。此时,系统中的势能主要包括网络中所有边的总弹性势能,以及边-边相互作用的弹性势能。面对外部压力时,网络表现得更像液体或凝胶(如图Fig. 3 (a)所示)。

图中(d), (e) 分别是用FDL模型、FUEL模型对一个网络的可视化。可以看出,FDL模型中,由于节点位置固定且边比较密集,产生了很多相互穿插的边。这些相互交叉、覆盖的边使人们无法清晰看到网络的详细结构。而FUEL模型则较好地展现了网络结构上的详细细节。

在最后,推荐给大家一个由本文作者建立的、超级炫酷的3D复杂网络可视化网站可以让你和设计师一样,近距离超逼真地观察网络的每一个细节:

http://netwonder.net

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

参考资料:

[1] Dehmamy N., Milanlouei S.& Barabási A. A structural transition in physical networks, Nature 563:676–680 (2018).

[2] https://en.wikipedia.org/wiki/Graph_isomorphism

[3] http://netwonder.net

备注:

本文中的网络数据与代码地址:

https://github.com/nimadehmamy/3D-ELI-FUEL

作者:任晓龙、吴蕾蕾

编辑:王怡蔺

推荐阅读

最先发现无标度网络的人竟然是他!?

优化网络结构最大程度发挥认知潜力

双曲空间中的网络、单词及其知识图谱

作为复杂网络深度学习系统

加入集智,一起复杂!

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

集智AI学园

https://campus.swarma.org


Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

搜索公众号:集智俱乐部

加入“没有围墙的研究所”

Barabási组最新Nature封面文章:复杂网络如何3D打印?-集智俱乐部

让苹果砸得更猛烈些吧!

原文始发于微信公众号( 集智俱乐部 ):集智