基于混合連邊機(jī)制的網(wǎng)絡(luò)演化和滲流相變研究

王睿婕

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

關(guān)鍵詞：隨機(jī)網(wǎng)絡(luò)；滲流；多級相變；自平均

中圖分類號：N94；O357.3 文獻(xiàn)標(biāo)識碼：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 引 言

滲流是統(tǒng)計物理學(xué)和概率論中被廣泛研究的基本概念之一[1]，目前滲流模型被廣泛應(yīng)用于流行病傳播[2]，網(wǎng)絡(luò)信息傳播與交互[3]，復(fù)合材料的電導(dǎo)[4]，生物蛋白質(zhì)交互[5]，多孔介質(zhì)[1]等領(lǐng)域中。

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

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

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

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

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

1 模型介紹

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

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

2 網(wǎng)絡(luò)結(jié)構(gòu)分析

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

（1）

（2）

（3）

為節(jié)點i被選中為主節(jié)點的概率，為節(jié)點i被選中為從節(jié)點的概率。我們將表達(dá)式（2）與文獻(xiàn)[12]提出的冪指數(shù)可調(diào)模型中的優(yōu)先連接機(jī)制相聯(lián)系，在Price模型中，每個已經(jīng)存在的節(jié)點被新添加邊指向的概率為：

（4）

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

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

由公式（2）、（3），并結(jié)合Price模型優(yōu)先連接機(jī)制可知，當(dāng)N→∞，其生成網(wǎng)絡(luò)結(jié)構(gòu)為無標(biāo)度網(wǎng)絡(luò)和均勻網(wǎng)絡(luò)的組合，當(dāng)只考慮時，按照無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)增長，冪指數(shù)隨的γ調(diào)節(jié)而變化，當(dāng)只考慮時，生成網(wǎng)絡(luò)為均勻網(wǎng)絡(luò)，其度分布也被證明服從泊松分布[13]。

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

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

4 結(jié) 論

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

以上研究結(jié)果表明：通過控制BFW模型候選邊結(jié)點的選取方式，可以有效控制生成網(wǎng)絡(luò)結(jié)構(gòu)類型。但是對MBFW模型加邊數(shù)為1.5N之后的滲流現(xiàn)象仍有待進(jìn)一步的研究，并且對異質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)下的滲流相變機(jī)理還需更嚴(yán)格的理論加以研究論證。

參考文獻(xiàn)：

[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.