基于混合連邊機制的網絡演化和滲流相變研究

王睿婕

摘 要：隨機演化網絡中的BFW滲流模型具有的強不連續相變以及多重巨型分支穩定共存的特性引起了統計物理學家的廣泛關注。本文基于混合連邊機制，提出了修改的BFW模型。大量模擬實驗表明存在一個調控參數的臨界點。當偏好連邊概率大于該臨界點時，生成網絡的度分布呈現冪律分布；而小于臨界點時，生成網絡的度分布呈現泊松分布。進一步對該模型滲流特性的分析結果表明，當偏好概率大于臨界點時，模型具有多級相變；而小于臨界點時，只有一次相變發生。更有趣的是，當偏好概率小于臨界點時，序參量在熱力學極限下是自平均的。相反，序參量會出現隨機震蕩現象，且在熱力學極限下不具有自平均性質。

關鍵詞：隨機網絡；滲流；多級相變；自平均

中圖分類號：N94；O357.3 文獻標識碼：A 文章編號：2096-4706（2018）02-0085-05

Research on Network Evolution and Seepage Transformation Based on Hybrid Connection Mechanism

WANG Ruijie

（ABA Teachers University，Aba 623002，China）

Abstract：The characteristics of the discontinuous percolation at the transition point and multiple giant components coexist in the supercritical region of the BFW model on random network has attracted much attention from physicists and statisticians. A modified BFW percolation model is proposed by changing the way of selecting the candidate edge. Through large numbers of numerical simulations，we find that there exists a critical point，which separates the type of the network structure. If the probability of the preferential attachment excesses the critical point，the network degree exhibits a power-law distribution. Otherwise，the network degree is poisson distribution. Additionally，the percolation process of the modified BFW model is researched. Simulation results indicate that the percolation undergoes multi-transition when the probability of the preferential attachment excesses the critical point. More interestingly，order parameter has random fluctuations when the probability of the preferential attachment excesses the critical point.

Keywords：random network；percolation；multiple-transition；self-averaging

0 引 言

滲流是統計物理學和概率論中被廣泛研究的基本概念之一[1]，目前滲流模型被廣泛應用于流行病傳播[2]，網絡信息傳播與交互[3]，復合材料的電導[4]，生物蛋白質交互[5]，多孔介質[1]等領域中。

1959年至1961年間，Erd?s和Rényi提出了隨機網絡演化模型[6]，在該模型中，系統開始于N個獨立的頂點，每次以完全隨機的方式選取一條連邊，并加入到系統中，其網絡的滲流相變被認為是連續的二階相變。

直到2009年，文獻[7]對ER滲流模型隨機連邊規則稍作修改，引入競爭加邊的乘積規則，延遲了最大分支的生長，導致網絡序參量（系統最大連通分支的約化尺度）在相變點附近產生急劇變化，并稱這種現象為“爆炸滲流”。

隨后，大量相似或改進的添邊規則被引入不同的網絡結構中[8，9]并且同樣得到了類似的爆炸滲流現象。特別地，文獻[10]研究發現阿赫利過程下的序參量演化曲線具有隨機震蕩現象，而在ER隨機演化模型中序參量在熱力學極限下收斂到一條穩定曲線。此外陳巍等人研究了推廣的BFW模型[11]，發現了多重巨型分支共存現象，并指出這種相變是強不連續的。

本文基于經典BFW模型，研究了在混合選邊機制下，網絡結構和滲流相變的變化情況，并提出了修改的BFW模型中的候選邊的選取方式，并稱之為修改的BFW（簡記為MBFW）模型。數值模擬和理論分析表明存在一個生成網絡結構類型變化的臨界點γc，同時該臨界點也是滲流是否具有多級相變的臨界點。

此外，研究發現了更有趣的現象：實驗表明，隨著控制參量的變化，序參量的自收斂性在臨界點γc處也隨之發生改變。

1 模型介紹

為方便描述，記時刻t=l/N為當前添加到系統中的連邊數與系統尺度比值。將BFW模型中候選邊選取方式進行如下的修改：第一個結點按照隨機的方式從系統中選取，第二個結點以概率γ按度大優先選?。總€頂點被選擇的概率為該頂點的度數與當前系統中節點總度數的比值，，ki（t）為節點i在時刻t時的度數），否則以1-γ的概率從系統中隨機選取。

連接這對頂點得到一條候選邊eu，對得到的候選邊eu按照BFW模型算法判斷該條候選邊是否添加到系統中，BFW算法描述見文獻[11]。

2 網絡結構分析

首先，假設每一條侯選邊在每一步都被接受，即不受階段數K和衰減函數g（K）的限制，稱按照這種方式增長的網絡模型為ER-like模型，在ER-like模型下每添加一條邊，系統中每個頂點被選中的概率為：

（1）

（2）

（3）

為節點i被選中為主節點的概率，為節點i被選中為從節點的概率。我們將表達式（2）與文獻[12]提出的冪指數可調模型中的優先連接機制相聯系，在Price模型中，每個已經存在的節點被新添加邊指向的概率為：

（4）

（4）式可以理解為：1）以概率p按照度大優先選擇，每個節點被選中的概率為，其中p∈（0，1）為可調節參數；2）以概率1-p按照完全隨機地方式選取已有節點，此時每個節點被選中的概率為1/N，Nt為當前時刻添加到網絡中的節點數。通過主方程方法可以計算出，其中α為可調節參數，為第i個節點的入度，λ=2+α/m，m為每次添邊數，λ∈（2，∞）。如果把Price模型中的每一條有向邊改為無向邊，可得pk～（k-m+α）-λ，其中λ=2+α/m，且λ∈（2，∞）。

圖1所示為MBFW模型生成網絡度分布，系統尺度均為N=106。（a）γ=0.5，0.7，t=1.5時度分布圖，插圖為γ=0.84度分布圖；（b）為γ=0.86，t=1.5時度分布情況，插圖為雙對數坐標下度分布情況；（c）γ=0.90，0.94，0.96，0.98，t=1.5時的度分布以及雙對數坐標下的度分布情況；（d）ER模型和BFW模型在t=1.5時生成網絡度分布對比圖。

由公式（2）、（3），并結合Price模型優先連接機制可知，當N→∞，其生成網絡結構為無標度網絡和均勻網絡的組合，當只考慮時，按照無標度網絡結構增長，冪指數隨的γ調節而變化，當只考慮時，生成網絡為均勻網絡，其度分布也被證明服從泊松分布[13]。

而BFW模型中在階段數K和衰減函數g（K）的限制下，大分支的生長被一定程度的抑制，滲流相變點之前，添加到系統中的隨機連邊主要位于孤立節點或小連通分支當中，因此與ER隨機網絡度分布相比，BFW模型下節點的度數會更集中于平均度數附近，大量數值模擬也證明了我們的分析結論，圖1（d）為ER滲流模型和BFW滲流模型下t=1.5時的度分布對比，BFW模型節點度分布更集中于平均度

以上實驗結果表明，γ<γc時，序參量具有自平均特性，而γ>γc時，序參量不具有自平均特性。該結論與經典ER滲流模型以及阿赫利過程下的滲流相變相比具有非常顯著的差別。

4 結 論

本文基于混合連邊機制提出了MBFW模型，并且研究了該模型下的網絡結構變化以及滲流相變性質。大量實驗結果表明，網絡結構隨著γ的增大而發生改變，在添邊數為1.5N時，存在臨界點γc∈（8.84，0.86），在和γ∈（γc，1），生成網絡結構分別具有均勻網絡特性和無標度網絡特性。研究發現，γ對滲流過程具有顯著地影響，結果表明當γ<γc時，MBFW模型只有一次相變；而當γ∈（γc，1）時，MBFW模型具有多級相變。此外，通過對比實驗表明，在MBFW模型中，序參量的自平均性質也隨控制參量γ的改變而變化，當 時，序參量具有自平均性；而當γ∈（γc，1）時，序參量具有隨機震蕩現象，不具備自平均性。該結論與經典ER模型以及阿赫利過程下的滲流相變相比具有非常明顯的差別。

以上研究結果表明：通過控制BFW模型候選邊結點的選取方式，可以有效控制生成網絡結構類型。但是對MBFW模型加邊數為1.5N之后的滲流現象仍有待進一步的研究，并且對異質網絡結構下的滲流相變機理還需更嚴格的理論加以研究論證。

參考文獻：

[1] AHARONY A，STAUFFER D.Introduction to percolation theory [M].S.l.：Taylor and Francis，2003.

[2] Klaus Dietz.Infectious diseases of humans：dynamics and control [J].Trends Parasitol，1992，8（5）：179.

[3] David Strang，SOULE saraha.Diffusion in organizations and social movements：from hybrid corn to poison pills [J].Annu Rev Sociol，1998，24.

[4] SAHINI M，SAHIMI M.Applications of percolation theory [M].S.l.：Taylor and Francis，2014.

[5] ROZENFELD HD，SONG C，MAKSE HA.Small-world to fractal transition in complex networks：a renormalization group approach [J].Phys Rev Lett，2010，104（2）.

[6] ERD?S P，R?NYI A. On the evolution of random graphs [J].Bull.Inst.Internat. Statist.，1961.

[7] D.ACHLIOPTAS，R M.D'SOUZA，J.SPENCER. Explosive percolation in random networks [J].Science，2009，323（3）：1453-1455.

[8] ZIFF RM. Explosive growth in biased dynamic percolation on two-dimensional regular lattice networks [J].Phys Rev Lett，2009，103（4）.

[9] CHO YS，KAHNG B，KIM D.Cluster aggregation model for discontinuous percolation transitions [J].Physical Review E，2010，81（3）.

[10] Oliver RiordanLutz Warnke.Achlioptas processes are not always self-averaging [J].Phys. Rev.E，2012.

[11] Chen，Wei，D'SOUZA R M.Explosive percolation with multiple giant components [J] Phys Rev Lett，2011，106（11）.

[12] PRICE D D S. Networks of scientific papers [J].Science，1965，149（3683）：510-515.

[13] Noga Alon，Joel H. Spencer.Random graphs [M].Hoboken，NJ，USA：John Wiley & Sons，Inc.，2000：155-181.