採用新提出的3D空間布局模型的兩個網路，經3D列印之後的實物圖。左：BA網路模型，右：ER網路模型

導語

3D列印複雜網路，不僅是技術，更是藝術。近期Nature雜誌以封面文章的形式發表了以複雜網路巨擘 Albert-László Barabási為通訊作者，Dehmamy為第一作者的研究成果[1]，詳細討論了在真實世界中，網路的節點和邊所佔據的體積、大小不能忽略的情況下，如何在3D空間上對網路進行布局。論文題目：

A structural transition in physical networks論文地址：

nature.com/articles/s41

自從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趨於無窮時，

，即在熱力學極限下，網路不存在弱連接的情況！並且，這一結果與網路的類型、網路度分布、網路的規模無關。

也就是說，當網路節點較多時，傳統的網路布局/可視化方法由於不考慮邊的粗細，且邊大多數情況下保持筆直，會讓網路充斥著大量交叉著的邊，難以在實際應用中使用。最後，作者通過柯西應力張量（Cauchy stress tensor）計算了弱連接情況和強連接情況下，網路單位面積所承受的作用力。

在弱連接情況下，網路中的邊比較細且幾乎保持著筆直的狀態，系統中的勢能主要為點-點相互作用的彈性勢能，以及點-邊相連產生的勢能。面對外部壓力時，網路表現得更像固體（如圖Fig. 3 (a)所示）。

在強連接情況下，網路中的邊比較粗且蜿蜒曲折，幾乎佔據了整個網路布局的大部分體積。此時，系統中的勢能主要包括網路中所有邊的總彈性勢能，以及邊-邊相互作用的彈性勢能。面對外部壓力時，網路表現得更像液體或凝膠（如圖Fig. 3 (a)所示）。

圖中(d), (e) 分別是用FDL模型、FUEL模型對一個網路的可視化。可以看出，FDL模型中，由於節點位置固定且邊比較密集，產生了很多相互穿插的邊。這些相互交叉、覆蓋的邊使人們無法清晰看到網路的詳細結構。而FUEL模型則較好地展現了網路結構上的詳細細節。在最後，推薦給大家一個由本文作者建立的、超級炫酷的3D複雜網路可視化網站可以讓你和設計師一樣，近距離超逼真地觀察網路的每一個細節：netwonder.net

參考資料：

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

[3] netwonder.net

備註：

本文中的網路數據與代碼地址：github.com/nimadehmamy/作者：任曉龍、吳蕾蕾 推薦閱讀

最先發現無標度網路的人竟然是他！？

優化網路結構最大程度發揮認知潛力

雙曲空間中的網路、單詞及其知識圖譜

作為複雜網路的深度學習系統加入集智，一起複雜！

集智AI學園：

campus.swarma.org

集智俱樂部QQ群｜877391004

商務合作及投稿轉載｜[email protected]◆ ◆ ◆搜索公眾號：集智俱樂部加入「沒有圍牆的研究所」

讓蘋果砸得更猛烈些吧！

推薦閱讀：

相关文章