複雜網絡上的爆發現象綜述：相變、爆發、生命起源有何共同之處_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！2019-08-14 09:49
撰文|郭瑞東
審校|劉培源****編輯|張爽
**來源：**集智俱樂部
社會運動在失控前經歷了怎樣的演變過程？冷門話題為何在某個時間點突然引爆社交網絡？遺傳變異在然顯現之前必須經過長期積累？2019國際網絡科學大會的一篇綜述文章，從滲流和同步現象出發，詳細討論了複雜網絡上爆發現象的特徵、成因和應用，揭開了爆發現象的謎題一角。
誰不想一夜成名？格拉德維爾在暢銷書《引爆點》中介紹了創造流行的三原則——個別人物，附着力及環境的威力。然而在複雜網絡的研究中，爆發現象 (Explosive phenomena)有着不同的定義。
今年5月，在網絡科學的頂會netsci2019上，展示了一篇針對複雜網絡中的爆發現象的綜述論文，從現象，建模，應用等多個視角，論述了對網絡中的滲流（Percolation），同步（Synchronization），擁堵（congestion）等現象的研究進展。本文從該綜述中選取對研究者有用，對科學愛好者有趣的內容，帶你初探網絡上的爆發現象，篇幅限制，這裏主要談滲流相關的現象。
論文題目：Explosive phenomena in complex networks
論文地址：https://arxiv.org/abs/1907.09957
1 何謂網絡上的爆發現象
統計物理中有個很有逼格的詞——“相變”（phase transitions），其實就是描述水結冰，變成蒸汽這樣温度一變性質就完全變化的現象，可如果變化本身是連續的（可微分的），沒有涉及形態上的劇變，就被細分成了二階相變（second-order phase transitions），例如温度降低後變成超導體。
將相變這個統計力學的概念應用到複雜網絡上，就可以用來描述那問題來了，複雜網絡中是否存在相變現象了，相變是連續的還是“躍遷”式的？
複雜網絡上的爆發現象，就是一種網絡的相變。在09年，Achlioptas首次開啓了對網絡中爆發現象的探索。之後的研究指出，網絡中的爆發現象不止和生命的誕生相關，還有諸如“怎樣最高效地控制虛假信息在網絡中傳播”這樣實際的應用。
網絡中的爆發現象，不論其場景如何，其成因的本質在於微觀演化中的動力學，會阻礙宏觀現象的出現。也就是説，不同的網絡初始結構和網絡中連接的生成機制，會影響網絡中各個局部區域變化及連接生長的方式，而當節點互相爭搶額外的連接機會時，就會暫時讓網絡整體不呈現特定的宏觀上的特徵，例如整個網絡中所有節點完全連接。但暫時的阻礙畢竟不會持久，總會有一個時刻，網絡發生了相變，上述現象，就被稱為網絡中的爆發現象。
2 網絡中的滲流與爆發現象
圖1：網絡上的滲流現象示意圖，來源：http://www.johnkerl.org/rcm/doc/about_rsp.html
滲流最初的場景是液體在一個隨機無序多孔的介質中，如何擴展和流動，後來被用於描述在各類網絡，信息如何傳播。滲流聽起來好專業啊，但看了上面的動圖，你可以形象地理解何為滲流。
圖2a：網絡滲流的生成機制（Product Rule）示意圖
圖2b：展示網絡隨時間演變下宏觀特徵變化
圖2c：為Product Rule生成的網絡舉例
而所謂網絡滲流中的爆發現象，上圖給出了一個最簡單易懂的例子。中間的圖b，橫軸是用於生成該網絡的當前已用時間，縱軸是網絡中連接最多節點的組件（component）的節點個數，與網絡中全部節點個數的比值，也是我們關注的網絡的宏觀特徵。其中的藍色和黑色分別代表的是ER（Erdos-R´enyi）和BF（Bohman Frieze），這是用於生成隨機網絡的兩種經典模型，其中ER方法是以概率p連接N個節點中的每一對節點，而PR（Product rule）是一種新的生成隨機網絡的方式。可以很直觀地看到，PR模型下，變化看起來是不連續的，突發的。
什麼樣的規則，能產生上述的爆發現象呢？總體來看，這個規則，要使用全局信息來指導局部連接的生成，以阻止網絡中節點數較大的組件的誕生。據此，就有了左邊圖a展示的規則，在當前網絡中隨機連接兩組點，每組兩個，然後分別計算每組兩個點相連的網絡組件（componment）的節點數的乘積，選擇該乘積較小的點，如果乘積相同，則隨機選擇一個，上圖A的例子中，圖中就選了e2（2×2）而不是e1（3×12）作為加入節點的邊。
3 更多的網絡生成模型
接下來讀者可以發揮想象力，看看基於上述的原則，還能設計出怎樣的網絡生成規則。不同的網絡生成規則，代表了對不同現實中各類現象，以不同的側重點進行的通用簡化，也是用來和真實現象進行對比的空模型（Null model），並不只是數學家的智力遊戲。
圖3：網絡生成模型示例：dCDGM 模型
上圖展示了dCDGM 模型，每步選取隨機2個包含m個組件的集合，對兩個集合中節點數最少的組件，隨機添加一條邊，將其連起來。
圖4：網絡生成模型示例：DS 模型
另一種Devil’s staircase（DS） 模型，隨機選擇k條邊，然後選擇k條邊中連接的組件節點個數最相近的那個，如上圖中，k為3，選擇了實線而非虛線的邊。
也不是所有的生成都需要網絡中局部結構之間的互動，例如高斯模型，就是隨機在網絡中增加一條邊，如果該邊會增加網絡中最大組件的節點數，該邊就按高斯定律，有一定的可能被抹去。
但不管生成模型是怎樣的，我們關注的都是網絡宏觀的特徵，下表整理了各種網絡中的生成模型，圖中最右邊一欄指出了當網絡趨於無限大時，依據數學推演出的，在網絡無窮大時的網絡演變（最大組件節點所佔比）折線圖，由於網絡中的爆發現象會導致網絡具有不可均一性（後文會詳細論述），因此比較有限網絡和無限網絡的演變曲線的區別，可以用來評價模型在小數據集上的代表性。
圖5：各類網絡生成模型的對比
4 真實世界中和滲流有關的爆發現象
在社交網絡和國際貿易網絡中，出現類似上述模型描述的爆發現象並不奇怪，真正有意思的是在蛋白質的相似性網絡中，也存在着爆發現象。
HPHN（Human Protein Homology Network） 是對人類體內的蛋白質，按照其相似性連接，組成的網絡，描述了蛋白質通過複製和突變，能怎樣一步步地從一種形態變為另一種形態，該網絡的結構，決定了生命進化的路徑。而真實的蛋白質相似網絡，是先形成一個個大小相似，但互不連接（無法通過突變轉化）的多個組件，之後再通過類似社交網絡中的“弱連接”讓組件連接起來。
圖6：通過對比根據蛋白質相似性排序組成的HPHN網絡和不同生成模型，説明HPHN網絡呈現爆發現象
如圖所示，縱軸是最大組件節點數佔全網絡總節點數的比例，紅色和藍色分別代表了上述的PR模型及ER模型，黑色是將蛋白質按相似度高到低連接起來形成的網絡，可以看出圖中黑線更接近紅線。這説明生物的進化過程中，蛋白質要從一種功能進化到另一個功能，花了很多時間，累計突變，看似沒用，但卻是在為爆發做準備。
上述通用的現象，也可以解釋為何癌症的發現往往沒有前兆：有害突變的積累，最終導致了蛋白質網絡中的某兩個點，最終連接到了，也就是通過突變成為致癌蛋白。
5 爆發現象呈現的非自我均一性（Non-self average）
管中窺豹説的是從一個局部無法推出整體的性質，學術界將其稱為非自我均一性。而展現出爆發現象的網絡，也無法根據從中抽取的一個子網絡的性質，來預估網絡整體的性質。在這樣的網絡上，當觀察的子網絡變大，觀察得出的統一值，例如平均值、最大值、最小值，不會趨近於整個網絡的對應值。也就是説，對於展現爆發現象的網絡，你取其中10%的節點來分析，我取其中90%的節點來分析，兩人分析的結果從理論上，在對網絡真實的狀況的代表性上沒有好壞之分。
圖7：展示不同大小的網絡在多次隨機模擬中呈現的最大組件大小的不穩定性
上圖中的橫軸是時間，縱軸是最大組件節點數佔總節點數的比例在多次模擬中的方差，圖中不同的顏色代表不同大小的網絡。可以看到在爆發現象出現之前，不同大小的網絡，在多次模擬中，其最大節點的變異性隨時間有顯著的波動，直觀地看，紅線和藍線的差距，與綠線和藍線的差距，並沒有顯著的區別，這説明了在前文所述的DS生成模型下，網絡呈現非自我均一性。
圖8：鹼基鏈通過自催化而連接的過程，來源：https://journals.aps.org/pre/abstract/10.1103/PhysRevE.98.022408
生命從原始湯（primordial soup）中誕生的過程，在理論模擬中，也展示了爆發現象。例如，鹼基鏈通過自催化（autocatalysis）而連接（ligation）。
而在模擬環境下，不同鹼基鏈組成的連接網絡，網絡中最大的組件節點數所佔的比例呈現爆發現象。
圖9：鹼基連接網絡的宏觀特徵，來源：https://journals.aps.org/pre/abstract/10.1103/PhysRevE.98.022408
如上圖所示，該研究還觀察到了鹼基連接網絡展現瞭如非自我均一性等和爆發現象有關的宏觀特徵，由此推斷，早期的可自我複製的分子是持續湧現出的多個有限大小的鹼基序列，之後爆發式的產生連接多串序列的複雜大分子。這項研究説明自我複製這一和生命誕生有密切聯繫的特徵，與網絡中的爆發現象有關。
6 研究網絡中的爆發現象的實際應用
社交網絡中傳遞的虛假信息，對於保持社會穩定有巨大的危害，顏色革命的爆發看似沒有徵兆，但若是瞭解了網絡滲流中的爆發現象，就可以將其看成是假信息傳播累積帶來的必然會發生的“相變”。
通過對網絡進行模擬，例如講PR模型中用於判斷是否加入一條邊的規則由節點數乘積較小改為節點數之和較小（Sum Rule），可以模擬社交網絡中的信息的傳遞，從而可以預估網絡中爆發現象出現的時間，以提前進行預警。相近的應用場景是通過模擬，找出預期能夠更高效的阻止網絡中最大組件組件變大的節點。
這類似本文開頭提到的《引爆點》這本書提到的個別人物原則，只是書中是用來引爆潮流，而這裏是如何高效的讓網絡獲得對某種謠言或病菌的“抗體”，讓網絡具有羣體免疫力。除了對特定節點進行干預，爆發行為的研究，對如何最高效的將網絡拆分成多個部分，也有指導意義。
7 網絡中的爆發現象還有哪些？
除了滲流，網絡中的節點振盪的頻率同步隨時間的變化，也會由於局部節點的相互作用，展現出爆發現象，也就是突然間網絡中的節點都同步了。目前已有很多模型，對其進行建模，也有很多具體應用場景。例如大腦中神經元網絡在自發同步過程中展示的爆發現象，和意識的產生有關，而心跳節律的維持，也和網絡中的爆發現象有關。電網中不同節點間，也會出現爆發性的同步現象，從而更好的理解與同步有關的爆發現象，有助於能源的調控。
在交通網絡中，擁堵來得悄無聲息，這想必很多人都有所體會。而傳染病的突然流行，則是疾病傳播場景下的爆發現象。而在多層網絡上，例如不同類型的交通工具（飛機、大巴、火車）共同組成的交通網，也會出現爆發現象，如下圖所示：
圖10：航空、公路、鐵路交通網絡中的爆發現象對比
回顧這項研究工作，首先要指出，爆發現象是複雜網絡中普遍存在的一種現象，就如同標度不變性（scale-free）一樣。透過這個角度，可以對不同類型的網絡，進行統一的建模，從中找出不同學科的共有邏輯。其次要強調的是，當前的研究，尚且缺少對爆發現象程度的定量分析，也沒有對網絡中局部接受到多少全局信息和網絡中爆發現象的激烈程度進行關聯，這是未來研究的重點。
網絡中的爆發行為背後，都是來自局部網絡節點間微小但持續的改變，由於節點的選擇，導致了看起來沒有效果，但累積終會帶來爆發這一現象，這正應了“功不唐捐”這個詞，也就是所謂的“勿以善小而不為，勿以惡小而為之”。人類社會的諸多行為表象，背後深層規律都在網絡科學中。
本文經授權轉載自微信公眾號“集智俱樂部”。
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。
相關閲讀