陳小龍，楊 春，李志鵬，付傳技,，楊宏春，楊宇明，史曉紅，賈 嘯,

?

復(fù)雜網(wǎng)絡(luò)爆炸滲流研究綜述

陳小龍1,2，楊 春1,2，李志鵬1，付傳技1,3，楊宏春3，楊宇明2，史曉紅1,2，賈 嘯1,3

(1. 電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國(guó)家重點(diǎn)實(shí)驗(yàn)室 河南洛陽(yáng) 471003；2. 電子科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院 成都 611731； 3. 電子科技大學(xué)物理電子學(xué)院 成都 610054)

該文對(duì)近幾年來(lái)國(guó)內(nèi)外學(xué)者關(guān)于爆炸滲流的相關(guān)研究作了詳細(xì)的綜述，總結(jié)了網(wǎng)絡(luò)滲流研究中提出的典型模型及其主要結(jié)果，展示了關(guān)于爆炸滲流類(lèi)型研究的主要結(jié)論，介紹了爆炸滲流在真實(shí)復(fù)雜網(wǎng)絡(luò)中的應(yīng)用研究狀況，同時(shí)對(duì)未來(lái)爆炸滲流的研究提出了展望。

爆炸滲流; 相變; 隨機(jī)網(wǎng)絡(luò); 魯棒性

滲流是統(tǒng)計(jì)物理學(xué)和概率論中的基本概念之一，網(wǎng)絡(luò)滲流一直被認(rèn)為是非平衡相變的基礎(chǔ)性模型[1]。文獻(xiàn)[2]于1957年引入了滲流概念，用于描述流體在無(wú)序多孔介質(zhì)中的流動(dòng)行為。1959～1961年間，文獻(xiàn)[3-4]提出了隨機(jī)網(wǎng)絡(luò)演化模型(ER模型)：模型開(kāi)始于個(gè)完全孤立的頂點(diǎn)組成的系統(tǒng)，以完全隨機(jī)的方式從系統(tǒng)中選取節(jié)點(diǎn)添加連邊。其重點(diǎn)關(guān)注序參量(order parameter)隨添邊密度的演化行為。其中，表示系統(tǒng)中最大連通分支尺度，表示添邊數(shù)。數(shù)值和解析研究結(jié)果表明，熱力學(xué)極限下，當(dāng)＜1/2時(shí)，～；當(dāng)時(shí)，；當(dāng)＞1/2時(shí)，～，其中是一個(gè)常數(shù)，即存在一個(gè)臨界值，系統(tǒng)的連通性質(zhì)在該點(diǎn)處發(fā)生相變。

研究ER滲流模型的滲流過(guò)程具有重要的理論意義：其一，其相變過(guò)程可以通過(guò)數(shù)學(xué)方法得到論證，這就為用數(shù)學(xué)和統(tǒng)計(jì)物理方法研究自然界中廣泛存在的相變現(xiàn)象提供了理論基礎(chǔ)，對(duì)理解各種推廣模型有著指導(dǎo)作用；其二，對(duì)真實(shí)系統(tǒng)來(lái)說(shuō)，ER模型不可能都適合，但對(duì)它的研究可能成為研究復(fù)雜系統(tǒng)的切入點(diǎn)。同時(shí)，研究網(wǎng)絡(luò)中最大分支尺度隨邊密度的變化規(guī)律也具有重要的實(shí)際意義：它可以作為解釋很多真實(shí)系統(tǒng)連通性突變的理想模型，如多孔巖石[1]、電阻網(wǎng)絡(luò)[5]、森林火災(zāi)[6]，甚至社會(huì)網(wǎng)絡(luò)[1,7]等。特別地，如果把網(wǎng)絡(luò)進(jìn)化過(guò)程中的“添邊連桿”考慮為傳播疾病的接觸方式，那么網(wǎng)絡(luò)中最大連通分支的出現(xiàn)意味著該疾病疫情的傳播[8]。因此，各種類(lèi)型的隨機(jī)圖模型及其相變問(wèn)題得到了廣泛的研究[9-13]。研究的關(guān)鍵問(wèn)題是：1) 不同相變模型之間的關(guān)系；2) 隨機(jī)圖模型相變的主要特征及其普適性問(wèn)題。

2007年，文獻(xiàn)[10]引進(jìn)了一個(gè)很廣泛的隨機(jī)網(wǎng)絡(luò)模型族。文中對(duì)模型族中的每個(gè)模型，存在描述網(wǎng)絡(luò)中最大分支的連續(xù)函數(shù)，以及存在一個(gè)臨界點(diǎn)，使得當(dāng)時(shí)，，而在時(shí)，＞0，對(duì)于BJR模型族中所有模型來(lái)說(shuō)，是一個(gè)連續(xù)函數(shù)，但是在靠近臨界點(diǎn)時(shí)，可能存在差異很大的臨界行為。文獻(xiàn)[10]中，對(duì)任意的臨界指數(shù)，給出了當(dāng)時(shí)，～的例子，其中是常數(shù)。于是，的連續(xù)性似乎是網(wǎng)絡(luò)滲流的唯一性質(zhì)，它不隨模型的變化而改變。但是，2009年，文獻(xiàn)[14]對(duì)ER滲流模型隨機(jī)連邊規(guī)則進(jìn)行了簡(jiǎn)單的動(dòng)力學(xué)修改，引進(jìn)了抑制最大連通分支生長(zhǎng)的乘積規(guī)則(PR規(guī)則)，導(dǎo)致網(wǎng)絡(luò)序參量在相變點(diǎn)附近產(chǎn)生急劇變化，并稱這種現(xiàn)象為“爆炸滲流”(explosive percolation，EP)，且進(jìn)一步指出這種滲流相變屬于不連續(xù)的一階相變。PR乘積規(guī)則下的滲流相變與發(fā)生在傳統(tǒng)的ER隨機(jī)網(wǎng)絡(luò)中的滲流相變是完全不同的?！氨B流”的發(fā)現(xiàn)立即引起了人們的廣泛關(guān)注，成為2009年以來(lái)復(fù)雜網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)問(wèn)題，并取得了一系列研究成果。研究主要集中在如下3個(gè)方面：1) 構(gòu)建不同類(lèi)型的Achlioptas模型，借助于廣泛數(shù)值模擬、適當(dāng)?shù)臄?shù)學(xué)分析或采用有限標(biāo)度理論方法研究爆炸滲流的豐富行為，特別是在臨界點(diǎn)附近的臨界行為，揭示爆炸滲流的產(chǎn)生機(jī)制[14-26,30-36,38-44]；2) 研究爆炸滲流所屬相變類(lèi)型[28,45,58-66]；3) 爆炸滲流的應(yīng)用研究[7,57,75-78]。

1 Achlioptas過(guò)程下典型爆炸滲流模型

Achlioptas過(guò)程是一個(gè)競(jìng)爭(zhēng)過(guò)程[14]，在該過(guò)程下可以構(gòu)造許多競(jìng)爭(zhēng)規(guī)則。這些規(guī)則又可分為有界尺度規(guī)則與無(wú)界尺度規(guī)則兩大類(lèi)。

文獻(xiàn)[12]中提出的BF規(guī)則模型為典型的有界尺度規(guī)則。在BF規(guī)則模型中，開(kāi)始于個(gè)孤立頂點(diǎn)，候選邊是，當(dāng)時(shí)，如果連接的兩個(gè)分支尺度均為1，那么被選擇；否則，被選擇。有界尺度規(guī)則是經(jīng)得起嚴(yán)格的數(shù)學(xué)檢驗(yàn)的，且文獻(xiàn)[12-13]指出有界尺度規(guī)則既可以延遲也可以促進(jìn)滲流的發(fā)生。特別地，人們推測(cè)所有有界尺度規(guī)則的滲流相變?yōu)檫B續(xù)的[13]，并且這種推測(cè)得到了數(shù)值驗(yàn)證和一定的理論支撐，但是仍然有待嚴(yán)格的數(shù)學(xué)證明。

圖1 PR規(guī)則下連邊選擇示意圖[14]

a. PR規(guī)則下臨界窗長(zhǎng)度與系統(tǒng)尺度比值曲線～1

b. ER和BF規(guī)則下臨界窗長(zhǎng)度與系統(tǒng)尺度比值曲線

圖2 不同加邊規(guī)則下臨界窗長(zhǎng)度與系統(tǒng)尺度比值關(guān)系曲線[14]

對(duì)于無(wú)界尺度規(guī)則，則很難利用數(shù)學(xué)理論去解釋?zhuān)湫偷臒o(wú)界尺度規(guī)則有PR乘積規(guī)則[14]和SR和規(guī)則，并且在兩個(gè)規(guī)則下都可以得到“爆炸滲流”現(xiàn)象。在PR乘積規(guī)則中，系統(tǒng)開(kāi)始于個(gè)孤立頂點(diǎn)，每一步都隨機(jī)選取兩條候選邊，將每條候選邊相關(guān)聯(lián)的兩個(gè)分支的尺度作乘積，取乘積最小者對(duì)應(yīng)的邊加入到系統(tǒng)中，另一條邊則被丟棄(如圖1所示，，，因此被選擇，被舍棄)。而SR和規(guī)則中，將候選邊分別關(guān)聯(lián)的兩個(gè)分支的尺度作和，取和值最小者對(duì)應(yīng)的邊加入到系統(tǒng)中，另一條邊則被丟棄。為了研究無(wú)界尺度規(guī)則下的滲流相變情況，文獻(xiàn)[14]提出了“臨界窗”的概念，定義為最大連通分支包含節(jié)點(diǎn)數(shù)目小于時(shí)系統(tǒng)中添加的連邊數(shù)所能達(dá)到的最大值，為最大連通分支包含節(jié)點(diǎn)數(shù)目大于時(shí)添加到系統(tǒng)中的連邊數(shù)所能達(dá)到的最小值，其中，為兩個(gè)參量。，為兩個(gè)狀態(tài)之間加入的連邊數(shù)量，稱為“臨界窗”長(zhǎng)度。通過(guò)數(shù)值模擬發(fā)現(xiàn)，當(dāng)參數(shù)，，時(shí)，對(duì)于ER滲流模型和BF規(guī)則模型來(lái)說(shuō)，臨界窗長(zhǎng)度與系統(tǒng)尺度成明顯的線性關(guān)系，如圖2b所示；而對(duì)于PR積規(guī)則來(lái)說(shuō)，～，即臨界窗長(zhǎng)度與系統(tǒng)尺度成亞線性關(guān)系，如圖2a所示。

1.1 局部分支聚集模型

在爆炸滲流模型構(gòu)建中，一些學(xué)者將連邊的選取限制到具有共同頂點(diǎn)的邊，這樣候選邊涉及3個(gè)及以上的分支，這類(lèi)模型叫作局部分支聚集模型。文獻(xiàn)[15]提出了兩種局部分支聚集模型，即：鄰接邊模型(AE)和三角形規(guī)則模型(TR)。

AE是最簡(jiǎn)單的局部分支聚集模型，該規(guī)則仍然屬于抑制大分支生長(zhǎng)的模型，但其對(duì)大分支的抑制作用較SR和規(guī)則與PR乘積規(guī)則更弱。

局部分支聚集模型的優(yōu)點(diǎn)在于可以用數(shù)學(xué)方程描述進(jìn)化過(guò)程，也就是可以建立進(jìn)化過(guò)程中的微分方程，并通過(guò)Euler方法對(duì)微分方程數(shù)值求解來(lái)粗略地獲得相變點(diǎn)位置，這樣的局部過(guò)程似乎可以為分析不連續(xù)滲流提供幫助。

1.2 無(wú)標(biāo)度網(wǎng)絡(luò)滲流模型

在大量關(guān)于隨機(jī)網(wǎng)絡(luò)爆炸滲流研究展開(kāi)的同時(shí)，無(wú)標(biāo)度網(wǎng)絡(luò)上的爆炸滲流也得到了廣泛的關(guān) 注[17-19]。文獻(xiàn)[17-18]幾乎同時(shí)研究了在網(wǎng)絡(luò)結(jié)構(gòu)高度異質(zhì)的無(wú)標(biāo)度網(wǎng)絡(luò)上的滲流現(xiàn)象[19]。文獻(xiàn)[17]研究了PR規(guī)則在無(wú)標(biāo)度網(wǎng)絡(luò)上的爆炸滲流，他們根據(jù)CL(Chung and Lu)模型[20]以及PR規(guī)則得到了控制參數(shù)為(常規(guī)的CL模型中該值為無(wú)標(biāo)度網(wǎng)絡(luò)的度分布指數(shù))的無(wú)標(biāo)度網(wǎng)絡(luò)。他們發(fā)現(xiàn)在無(wú)標(biāo)度網(wǎng)絡(luò)中，AP過(guò)程對(duì)巨型分支形成的抑制作用和中心節(jié)點(diǎn)對(duì)巨型分支形成的促進(jìn)作用相互競(jìng)爭(zhēng)導(dǎo)致不連續(xù)相變不總是會(huì)發(fā)生。數(shù)值結(jié)果顯示，存在臨界點(diǎn)2.3＜＜2.4，當(dāng)2＜＜時(shí)，熱力學(xué)極限下，即網(wǎng)絡(luò)滲流過(guò)程是二階連續(xù)的，但在有限尺度下，＜時(shí)也為一階相變；當(dāng)＞時(shí)，隨系統(tǒng)規(guī)模趨于無(wú)窮的時(shí)候，收斂到一個(gè)非零常數(shù)，說(shuō)明在這種情況下，變換是非連續(xù)的一階相變！

1.3 最大分支控制模型與高斯模型

1.3.1 最大分支控制模型

在系統(tǒng)中隨機(jī)選取一條邊，如果接受它不會(huì)引起最大分支的生長(zhǎng)或新的最大分支的形成，那么該邊被添加到系統(tǒng)中；否則，該邊被接受的概率為：

1.3.2 高斯模型

1.4 BFW模型

BFW模型是網(wǎng)絡(luò)滲流研究中非常典型的模型之一，它由文獻(xiàn)[22]在2004年提出。通過(guò)引入階段數(shù)和衰減函數(shù)來(lái)判定每次從完全圖中隨機(jī)選擇的邊是否接受(見(jiàn)算法1)，并且用嚴(yán)格的數(shù)學(xué)方法證明了在BFW模型中從隨機(jī)選擇的條邊中，用任意方法選(＞)條邊加入圖中時(shí)，圖中存在巨大連通分支的概率在熱力學(xué)極限下趨近于1，并用數(shù)值方法證明了從隨機(jī)選擇的條邊中，添加條邊到圖中時(shí)，在熱力學(xué)極限下，圖中不存在巨大連通分支的概率趨近于1。文獻(xiàn)[23-27]對(duì)BFW模型進(jìn)行了深入的研究，運(yùn)用數(shù)值模擬方法發(fā)現(xiàn)原始BFW模型在滲流相變點(diǎn)附近有兩個(gè)巨分支同時(shí)出現(xiàn)(每個(gè)分支尺度大于系統(tǒng)尺度的40%)，并運(yùn)用概率論和微積分學(xué)的基本原理和方法分析證明了在超臨界區(qū)域內(nèi)，兩個(gè)巨分支穩(wěn)定存在并保持分離[23]。在此基礎(chǔ)上，將BFW模型進(jìn)行了推廣，將漸進(jìn)篩邊比例參數(shù)化，使衰減函數(shù)變?yōu)椋?/p>

文獻(xiàn)[24]又將篩邊比例控制函數(shù)的收斂速度參數(shù)化，引進(jìn)參數(shù)，得到：

并且基于“臨界窗”概念[14]和隨機(jī)圖滲流相變強(qiáng)弱不連續(xù)性與最大連通分支增長(zhǎng)方式之間的關(guān)系[28]，考察了參數(shù)對(duì)推廣的BFW模型滲流相變連續(xù)性的影響。發(fā)現(xiàn)如果＜1，最大分支的生長(zhǎng)機(jī)制以超越增長(zhǎng)為主，即兩個(gè)較小的分支合并成為一個(gè)新的最大分支，由文獻(xiàn)[28]可知其滲流相變類(lèi)型為不連續(xù)相變；而當(dāng)＞1，如果，滲流相變類(lèi)型為弱不連續(xù)相變。

a. 系統(tǒng)演化過(guò)程中巨型分支數(shù)量與參數(shù)關(guān)系圖[23]

b. 時(shí)，系統(tǒng)中共有3個(gè)巨型分支穩(wěn)定存在

此外，文獻(xiàn)[25]研究了BFW滲流模型在超臨界區(qū)域內(nèi)的滲流演化現(xiàn)象，并且發(fā)現(xiàn)存在參數(shù)臨界點(diǎn)，在和內(nèi)，具有完全不同的演化現(xiàn)象。文獻(xiàn)[26]總結(jié)了BFW模型滲流演化過(guò)程中的穩(wěn)定與不穩(wěn)定區(qū)間。文獻(xiàn)[68]則通過(guò)理論和數(shù)值研究提出了BFW模型中多個(gè)巨型分支穩(wěn)定共存的充分條件。

BFW模型的巨大連通分支性質(zhì)對(duì)研究網(wǎng)絡(luò)模塊結(jié)構(gòu)的形成過(guò)程，網(wǎng)絡(luò)結(jié)構(gòu)探測(cè)[29]等方面均有重要的作用。此外，多重巨大連通分支的發(fā)現(xiàn)在疾病傳播學(xué)、高分子聚合、通信網(wǎng)絡(luò)等方面也有一定的應(yīng)用前景[27]。

算法1 BFW模型算法

1) 初始化

2) 添邊過(guò)程

1.5 爆炸滲流相關(guān)模型及研究結(jié)果

以上對(duì)于Achlioptas過(guò)程下的爆炸滲流模型及研究結(jié)果的介紹主要基于無(wú)窮維隨機(jī)網(wǎng)絡(luò)結(jié)構(gòu)。同時(shí)，相關(guān)學(xué)者對(duì)有限維網(wǎng)絡(luò)結(jié)構(gòu)下的“爆炸滲流”也進(jìn)行了大量的研究并取得了豐富的研究成果[21,30-34,36-38,46,65]。文獻(xiàn)[31]首先將“乘積規(guī)則”引入到二維正方形網(wǎng)格的隨機(jī)滲流模型中，同樣得到了爆炸滲流現(xiàn)象；文獻(xiàn)[35]對(duì)“乘積規(guī)則”的非局部效應(yīng)與不連續(xù)相變的關(guān)系進(jìn)行了研究；文獻(xiàn)[37,71]提出了廣義Achlioptas過(guò)程，并給出了在廣義連續(xù)滲流和不連續(xù)滲流相變參數(shù)區(qū)間。文獻(xiàn)[38]等對(duì)二維和三維網(wǎng)格上的非限制性BFW模型以及高維(二維至七維)限制性BFW模型的滲流相變問(wèn)題進(jìn)行了深入的研究。

文獻(xiàn)[39-41]重點(diǎn)關(guān)注和討論了網(wǎng)絡(luò)滲流中的三相點(diǎn)問(wèn)題，三相點(diǎn)是指網(wǎng)絡(luò)滲流變化過(guò)程中某個(gè)參數(shù)的變化導(dǎo)致滲流相變由不連續(xù)相變轉(zhuǎn)換為連續(xù)相變的分界點(diǎn)，三相點(diǎn)問(wèn)題的研究一直以來(lái)是統(tǒng)計(jì)物理學(xué)和數(shù)學(xué)領(lǐng)域有趣但又具有挑戰(zhàn)性的問(wèn)題之一。文獻(xiàn)[39]提出了一個(gè)混合模型，通過(guò)調(diào)節(jié)控制參量來(lái)控制滲流相變類(lèi)型，控制參量的變化使得滲流由“爆炸滲流”到經(jīng)典滲流類(lèi)型轉(zhuǎn)換，并通過(guò)準(zhǔn)確的數(shù)值模擬找到了非平衡三相點(diǎn)；文獻(xiàn)[40]在ER模型和二維網(wǎng)格的“k-核”滲流里發(fā)現(xiàn)了三相點(diǎn)的存在性；另外，文獻(xiàn)[41]也通過(guò)構(gòu)造混合模型，并利用數(shù)值模擬和理論分析找到了經(jīng)典滲流和爆炸滲流轉(zhuǎn)換的三相點(diǎn)。

文獻(xiàn)[42]通過(guò)擴(kuò)展局域競(jìng)爭(zhēng)機(jī)制提出了獲取強(qiáng)不連續(xù)滲流模型，而且在系統(tǒng)進(jìn)化過(guò)程中得到了多個(gè)穩(wěn)定巨分支的共存現(xiàn)象。

而文獻(xiàn)[43]將Achlioptas過(guò)程擴(kuò)展到有向網(wǎng)絡(luò)中，并研究了有向網(wǎng)絡(luò)中的的爆炸滲流現(xiàn)象，得到PR乘積規(guī)則在有向網(wǎng)絡(luò)中的滲流相變類(lèi)型介于經(jīng)典滲流類(lèi)型和爆炸滲流之間，并稱之為“弱爆炸滲流”。

文獻(xiàn)[44-46]采用了不同的數(shù)值模擬方法對(duì)不同網(wǎng)絡(luò)上的爆炸滲流現(xiàn)象進(jìn)行了相應(yīng)的研究，并指出爆炸滲流是一種奇異滲流，雖然序參量具有不連續(xù)特征，但是包括尺度分布在內(nèi)的其他特征物理量卻具有冪律標(biāo)度行為[44]，因此爆炸滲流相變既不是標(biāo)準(zhǔn)的不連續(xù)相變，又與常規(guī)隨機(jī)滲流表現(xiàn)出的連續(xù)相變處于不同的普適類(lèi)[45]。進(jìn)一步，文獻(xiàn)[46]指出：爆炸滲流相變其實(shí)為連續(xù)滲流相變。文獻(xiàn)[47]研究了二維網(wǎng)格上乘積規(guī)則下的點(diǎn)滲流，并指出了其滲流相變?yōu)椴贿B續(xù)的。文獻(xiàn)[48]給出了AP規(guī)則下，爆炸滲流相變發(fā)生的必要條件。文獻(xiàn)[50]在研究Achlioptas過(guò)程下的滲流相變過(guò)程中提出了“火藥桶”的概念，并且指出，“火藥桶”內(nèi)的節(jié)點(diǎn)數(shù)在熱力學(xué)極限下為，并且在的時(shí)間內(nèi)形成一個(gè)巨型分支，導(dǎo)致了不連續(xù)相變發(fā)生。文獻(xiàn)[51]提出了Hamiltonian函數(shù)，并證明對(duì)于較小的參數(shù)，滲流相變?yōu)槎A連續(xù)的，對(duì)于較大的參數(shù)，滲流相變?yōu)橐浑A不連續(xù)的[51,87]。文獻(xiàn)[54]給出了滲流相變?yōu)檫B續(xù)相變和不連續(xù)相變的普適條件。文獻(xiàn)[69]研究了在最優(yōu)規(guī)則中，滲流臨界點(diǎn)與系統(tǒng)平均度的關(guān)系以及發(fā)生不連續(xù)滲流相變的條件。

此外，文獻(xiàn)[57]通過(guò)研究網(wǎng)絡(luò)最大特征根在AP過(guò)程下的變化情況來(lái)研究信息或物質(zhì)的傳播效率，他們發(fā)現(xiàn)在具有爆炸滲流相變的演化過(guò)程下，信息或物質(zhì)的傳播效率明顯降低。

2 爆炸滲流類(lèi)型

雖然Achlioptas過(guò)程下的隨機(jī)網(wǎng)絡(luò)滲流展現(xiàn)出“爆炸滲流”現(xiàn)象，并且其滲流相變類(lèi)型也被認(rèn)為是一階相變，但是人們對(duì)其不連續(xù)性的驗(yàn)證主要停留在數(shù)值模擬上，而并沒(méi)有建立嚴(yán)格的數(shù)學(xué)理論分析。然而Achlioptas過(guò)程下的隨機(jī)圖模型、二維網(wǎng)格模型、無(wú)標(biāo)度網(wǎng)絡(luò)模型及其他相似的爆炸性滲流模型下的序參量及其他特征物理量仍具有連續(xù)相變的冪律標(biāo)度行為[15,17-18,21,47-48]，這與“爆炸滲流”的不連續(xù)相變結(jié)論相矛盾，從而引起了學(xué)者們對(duì)“爆炸滲流”相變到底是不連續(xù)的一階相變還是連續(xù)的二階相變問(wèn)題的廣泛的討論與研究。

2010年，文獻(xiàn)[58]指出“爆炸滲流”相變其實(shí)是連續(xù)的。其首先構(gòu)造了一個(gè)的簡(jiǎn)單的滲流模型(CDGM模型)，模型中，首先從系統(tǒng)中隨機(jī)選擇一對(duì)分支，且選出它們中的較小者，不妨設(shè)為，再?gòu)南到y(tǒng)中隨機(jī)選出另一對(duì)分支，且選出它們中的較小者，不妨設(shè)為；其次，從,中分別隨機(jī)選出一個(gè)頂點(diǎn)，然后將兩頂點(diǎn)連接起來(lái)。顯然，CDGM模型相比PR積規(guī)則來(lái)說(shuō)，它提供了一個(gè)更直接的對(duì)應(yīng)于最小分支的選擇，PR規(guī)則是從兩種可能性中選擇尺度乘積最小者，而CDGM模型相當(dāng)于是從四種可能性中選擇乘積最小者。因此，CDGM模型對(duì)大分支生長(zhǎng)的壓制應(yīng)該比PR規(guī)則更強(qiáng)烈。所以，如果能夠說(shuō)明CDGM模型是連續(xù)滲流模型，那么，也就可以認(rèn)定PR規(guī)則滲流是連續(xù)滲流。

文獻(xiàn)[58]首先通過(guò)數(shù)值實(shí)驗(yàn)方法指出CDGM模型滲流變換符合連續(xù)相變特征，但是要說(shuō)明滲流相變的連續(xù)性必須要在無(wú)限系統(tǒng)下經(jīng)過(guò)嚴(yán)格的數(shù)學(xué)證明，文獻(xiàn)[58]在無(wú)限系統(tǒng)下通過(guò)建立在時(shí)刻系統(tǒng)中分支尺度分布滿足的微分方程并對(duì)其數(shù)值求解，獲得了的臨界行為滿足：，即在相變點(diǎn)，分支尺度分布具有冪律特征，然后通過(guò)證明指出：如果，則說(shuō)明滲流變化是連續(xù)的。這樣，文獻(xiàn)[58]證明了PR乘積規(guī)則下的滲流屬于二階連續(xù)相變。雖然文獻(xiàn)[58]對(duì)于“爆炸滲流”相變是連續(xù)相變的結(jié)論仍需進(jìn)一步的理論檢驗(yàn)，但是其仍然引起了統(tǒng)計(jì)物理學(xué)家的廣泛關(guān)注并為進(jìn)一步的研究提供了理論基礎(chǔ)。

2011年，文獻(xiàn)[59]指出爆炸滲流相變是連續(xù)的，但具有不尋常的有限尺度行為。通過(guò)使用有限尺度標(biāo)度理論，對(duì)PR乘積規(guī)則，二維網(wǎng)格(2d)，鄰接邊規(guī)則(AE)及CDGM規(guī)則的臨界行為進(jìn)行了廣泛的數(shù)值實(shí)驗(yàn)和理論分析，并發(fā)現(xiàn)這4種規(guī)則下的滲流的確具有連續(xù)性，但它們每一個(gè)都處在不同的普適類(lèi)中，并且均顯示出不尋常的有限尺度行為，具有一個(gè)非解析的標(biāo)度函數(shù)。

文獻(xiàn)[60]進(jìn)一步驗(yàn)證了乘積規(guī)則下的滲流相變?yōu)檫B續(xù)相變，但是隨機(jī)圖上的“爆炸滲流”相變連續(xù)性問(wèn)題的研究和討論仍然以數(shù)值模擬為主，理論分析具有相當(dāng)?shù)木窒扌曰蚪⒃谳^強(qiáng)的假設(shè)之上。

2011年，文獻(xiàn)[61]解決了“爆炸滲流”相變連續(xù)性問(wèn)題。盡管AP過(guò)程在一定系統(tǒng)規(guī)模下確實(shí)能夠展示爆炸滲流，但該過(guò)程的確有連續(xù)的相變。文獻(xiàn)[62]把滲流過(guò)程分成AP過(guò)程、混合-頂點(diǎn)規(guī)則(ML)及一般的-頂點(diǎn)規(guī)則(GL)3類(lèi)。同時(shí)，考慮兩種不同形式的連續(xù)性：首次連通性連續(xù)(fc)與全局連通性連續(xù)(gc)。通過(guò)較為嚴(yán)格的分析，得到上面3類(lèi)過(guò)程均是fc連續(xù)的，同時(shí)，AP過(guò)程與ML規(guī)則還是gc連續(xù)的。文獻(xiàn)[62]研究最終指出兩點(diǎn)：1) 任意一個(gè)基于選擇一個(gè)固定數(shù)量的隨機(jī)頂點(diǎn)的規(guī)則給出連續(xù)滲流變換；2) 爆炸滲流是連續(xù)的。

一切競(jìng)爭(zhēng)添邊規(guī)則下的滲流相變都是連續(xù)的嗎？文獻(xiàn)[61]已經(jīng)證明，對(duì)于3種類(lèi)型的滲流過(guò)程，在相變點(diǎn)處展示的變換是連續(xù)的，且AP與ML過(guò)程是全局連續(xù)的。但是，他們沒(méi)有對(duì)GL過(guò)程在相變點(diǎn)之后的情況說(shuō)明什么。

2012年，文獻(xiàn)[63]構(gòu)造了一個(gè)所謂的推廣三角形規(guī)則。通過(guò)廣泛的數(shù)值實(shí)驗(yàn)和現(xiàn)象分析，得到的結(jié)論是：1)首次變換的連續(xù)性并不意味連續(xù)發(fā)散性的存在；2) 極大連通集團(tuán)可以通過(guò)多個(gè)小的連通集團(tuán)來(lái)涌現(xiàn)，但多不連續(xù)跳躍仍然出現(xiàn)；3) 序參量可以出現(xiàn)無(wú)限層次的不連續(xù)跳躍。推廣的三角形規(guī)則為“競(jìng)爭(zhēng)滲流總是連續(xù)的”論斷提供了一個(gè)反例。

此外，文獻(xiàn)[28]在研究不連續(xù)相變的微觀機(jī)制的過(guò)程中提出了“強(qiáng)不連續(xù)”和“弱不連續(xù)”的概念。他們指出，在滲流演化過(guò)程中，由單條連邊引起的最大連通分支尺度變化與系統(tǒng)尺度比值在熱力學(xué)極限下為一非零常數(shù)，那么該滲流模相變?yōu)椤皬?qiáng)不連續(xù)”相變，否則為弱不連續(xù)相變，即，如果

則為“強(qiáng)不連續(xù)”相變。

由于隨機(jī)網(wǎng)絡(luò)只是歐式晶格上的平均場(chǎng)描述，而對(duì)于整個(gè)歐式空間上的“爆炸滲流”相變問(wèn)題卻沒(méi)有一個(gè)統(tǒng)一的判定框架和理論基礎(chǔ)，雖然對(duì)歐式空間上的EP問(wèn)題已經(jīng)有了相應(yīng)的研究，并且數(shù)值結(jié)果表明其為不連續(xù)滲流[14]，但是由于缺乏分析結(jié)果，歐式空間上的“爆炸滲流”相變階數(shù)還不能確定?；诖?，文獻(xiàn)[64]引入了一個(gè)隨機(jī)滲流模型，該模型中通過(guò)候選邊競(jìng)爭(zhēng)機(jī)制抑制連通分支之間的合并，并且通過(guò)啟發(fā)式論點(diǎn)表明熱力學(xué)極限下如果＜，“爆炸滲流”相變依競(jìng)爭(zhēng)邊數(shù)的不同而可以為連續(xù)相變，也可以為不連續(xù)相變；如果＞，那么“爆炸滲流”相變?yōu)檫B續(xù)相變。其中，為歐式空間維數(shù)，為維數(shù)的上臨界點(diǎn)。

為了進(jìn)一步理解爆炸滲流性質(zhì)對(duì)空間維數(shù)的依賴關(guān)系，在二維與三維網(wǎng)格上，文獻(xiàn)[65]對(duì)在文獻(xiàn)[34]中提出的6個(gè)不同模型的割邊數(shù)(割點(diǎn)數(shù))和臨界生成分支(CSC)的分形維數(shù)進(jìn)行了研究。他們發(fā)現(xiàn)，對(duì)于在尺度是的二維方格上的優(yōu)先填內(nèi)部邊模型和優(yōu)先填內(nèi)部點(diǎn)模型來(lái)說(shuō)，。與之相反，對(duì)于壓制填充內(nèi)部邊的模型來(lái)說(shuō)，的標(biāo)度為～，其中。對(duì)于優(yōu)先填內(nèi)部邊邊模型和優(yōu)先填內(nèi)部點(diǎn)模型來(lái)說(shuō)，他們獲得了，而對(duì)于二維的壓制填充內(nèi)部邊的模型來(lái)說(shuō)，＜。這些結(jié)果強(qiáng)烈地支持了在2D網(wǎng)格上的優(yōu)先填內(nèi)部邊邊模型和優(yōu)先填內(nèi)部點(diǎn)模型來(lái)說(shuō)經(jīng)歷了不連續(xù)變換，而對(duì)2D網(wǎng)格上壓制填充內(nèi)部邊的模型來(lái)說(shuō)卻經(jīng)歷了連續(xù)相變。在三維網(wǎng)格上，他們發(fā)現(xiàn)，對(duì)于所有6種模型來(lái)說(shuō)，＞0且＜，這表明模型滲流經(jīng)歷了連續(xù)相變?；谄骄种С叨群托騾⒘康挠邢蕹叨葮?biāo)度分析，在3D網(wǎng)格上，所有6種模型在數(shù)值誤差范圍內(nèi)幾乎展示同樣的臨界現(xiàn)象。

文獻(xiàn)[58]指出，爆炸滲流實(shí)際上是連續(xù)的，但是具有不尋常的滲流分支尺度分布的較小臨界指數(shù)。文獻(xiàn)[66]通過(guò)進(jìn)一步的研究，提出了一個(gè)有效的基于分支尺度分布的進(jìn)化方程的數(shù)值解，結(jié)合其冪律漸進(jìn)的方法，發(fā)現(xiàn)了一系列典型爆炸滲流模型的相變是二階相變的特征，且以較高的精度獲得了每個(gè)模型的臨界指數(shù)、振幅與臨界點(diǎn)。

對(duì)于不同類(lèi)型的代表性爆炸滲流模型，文獻(xiàn)[67]提出了一個(gè)關(guān)于爆炸滲流相變的嚴(yán)格的標(biāo)度理論，該理論提供了一系列完整的標(biāo)度函數(shù)和臨界指數(shù)。理論指出了與連續(xù)性問(wèn)題相關(guān)的序參量與敏感度，解釋了變換的連續(xù)性質(zhì)和變換的不尋常特性。文獻(xiàn)[72]則通過(guò)建立微分方程，并且尋找相應(yīng)方程解的存在性來(lái)判定AP規(guī)則相變是否連續(xù)。

從目前情況看，關(guān)于爆炸滲流類(lèi)型，有3種觀點(diǎn)：1) 爆炸滲流是非連續(xù)的，并且大多數(shù)學(xué)者是這樣認(rèn)為的；2) 爆炸滲流是連續(xù)的，但具有不尋常的有限尺度行為；3) 爆炸滲流是一種混合相變，既具有連續(xù)性特征，又具有許多不連續(xù)性特征，有著十分豐富的臨界行為。值得指出的是在爆炸滲流是否連續(xù)性滲流的問(wèn)題研究中，我國(guó)相關(guān)領(lǐng)域的學(xué)者[23-27,38,42-44,68-71]也取得了重要的進(jìn)展。

3 爆炸滲流的應(yīng)用

網(wǎng)絡(luò)的爆炸滲流現(xiàn)象反映的是一種突發(fā)事件。突發(fā)事件在自然、科學(xué)和人類(lèi)社會(huì)中是司空見(jiàn)慣的，在某些場(chǎng)合下需要?jiǎng)?chuàng)造條件使系統(tǒng)產(chǎn)生突變，而在另外的場(chǎng)合下又需要抑制突變。近幾年來(lái)，有部分學(xué)者結(jié)合真實(shí)世界網(wǎng)絡(luò)研究爆炸滲流，發(fā)現(xiàn)了Achlioptas滲流過(guò)程和一些真實(shí)網(wǎng)絡(luò)進(jìn)化過(guò)程十分類(lèi)似，從而開(kāi)啟了網(wǎng)絡(luò)爆炸滲流的應(yīng)用研究。

2010年，文獻(xiàn)[75]研究了人類(lèi)蛋白質(zhì)同源性網(wǎng)絡(luò)拓?fù)?H-PHN)進(jìn)化過(guò)程中的爆炸滲流現(xiàn)象，通過(guò)真實(shí)數(shù)據(jù)和同源蛋白質(zhì)網(wǎng)絡(luò)的生物學(xué)演化特征，首先在一定蛋白質(zhì)規(guī)模上建模了網(wǎng)絡(luò)，然后通過(guò)研究指出：蛋白質(zhì)同源性網(wǎng)絡(luò)的進(jìn)化機(jī)制能夠通過(guò)生長(zhǎng)遲緩的分支來(lái)描述，也就是這些分支一直保持緩慢生長(zhǎng)，直到過(guò)程的最后狀態(tài)，當(dāng)添加少量邊時(shí)，會(huì)導(dǎo)致這些分支的迅速合并而產(chǎn)生巨型分支。所以他們指出，通過(guò)分叉復(fù)制事件而形成的H-PHN拓?fù)涞倪M(jìn)化過(guò)程可能發(fā)生在突然的幾步中，這與在一階相變中看到的情形一致。

2011年，文獻(xiàn)[7]把爆炸滲流用于好幾個(gè)真實(shí)網(wǎng)絡(luò)的分析中。他們選擇了移動(dòng)電話網(wǎng)絡(luò)(MPC)，大型的論文合著網(wǎng)絡(luò)(CA)和小型的論文合著網(wǎng)絡(luò)(SCA)。通過(guò)研究，他們指出：1) 當(dāng)把爆炸滲流規(guī)則用到實(shí)證社會(huì)網(wǎng)絡(luò)時(shí)，Achlioptas過(guò)程能夠引起爆炸滲流變換；2) 使用修改的最小化分支和規(guī)則(MC)，即把連桿添加過(guò)程中的連桿比較數(shù)目設(shè)置為參數(shù)，如表示每步從10條候選連桿中按照連桿連接的分支和最小規(guī)則選取連桿，而表示從所有可能連桿中按照連桿連接的分支和最小規(guī)則選取連桿。得出網(wǎng)絡(luò)的結(jié)構(gòu)與連桿比較數(shù)對(duì)滲流變換的普適類(lèi)產(chǎn)生重要的影響作用；3) 確證了滲流過(guò)程間，通過(guò)MC規(guī)則選擇的連桿與網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)之間的聯(lián)系，即在滲流臨界點(diǎn)，由MC規(guī)則決定的分支結(jié)構(gòu)反映網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

文獻(xiàn)[7]的研究實(shí)際上關(guān)注了兩個(gè)問(wèn)題：1) 是否真實(shí)網(wǎng)絡(luò)的拓?fù)涮卣髟诰W(wǎng)絡(luò)爆炸滲流中扮演了一個(gè)十分重要的角色？這些特征包括高聚集性、度相關(guān)性、社區(qū)結(jié)構(gòu)和加權(quán)拓?fù)涞龋?) 是否可以通過(guò)跟蹤網(wǎng)絡(luò)滲流過(guò)程本身，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)認(rèn)識(shí)帶來(lái)一些重要信息？他們研究的結(jié)果得到了令人興奮的結(jié)論。

從孤立系統(tǒng)出發(fā)，按照Achliopts過(guò)程下的某種添加邊規(guī)則可以產(chǎn)生爆炸滲流，那么，一個(gè)真實(shí)系統(tǒng)由于受到隨機(jī)失靈或惡意攻擊后，系統(tǒng)中最大連通分支是否也會(huì)隨著時(shí)間的變化而產(chǎn)生爆炸性突變呢？2010年，文獻(xiàn)[79]以2003年9月28日發(fā)生在意大利電力網(wǎng)與信息網(wǎng)絡(luò)間的級(jí)聯(lián)失效為背景，對(duì)耦合基礎(chǔ)設(shè)施的級(jí)聯(lián)失效過(guò)程展開(kāi)研究，提出了級(jí)聯(lián)失效模型。借助于隨機(jī)圖度分布的母函數(shù)方法，提出了分析級(jí)聯(lián)失效相變過(guò)程的數(shù)學(xué)框架，獲取了相變點(diǎn)的解析計(jì)算方法。同時(shí)，如果兩個(gè)耦合的網(wǎng)絡(luò)均為隨機(jī)圖，在給出的耦合方式下，得到了相變滲流為爆炸滲流。類(lèi)似于上面模型的方法，文獻(xiàn)[80-81]提出了部分耦合的兩個(gè)網(wǎng)絡(luò)模型，得到兩個(gè)依存網(wǎng)絡(luò)間的耦合強(qiáng)度對(duì)相變類(lèi)型產(chǎn)生重大影響，減小耦合強(qiáng)度，可以使?jié)B流相變由一階相變過(guò)度到聯(lián)系相變。兩個(gè)相互耦合的網(wǎng)絡(luò)之間的邊可以是依賴邊也可以是連接邊。一個(gè)更現(xiàn)實(shí)的兩個(gè)耦合網(wǎng)絡(luò)系統(tǒng)既有依賴邊又有連接邊。利用滲流理論，文獻(xiàn)[82]發(fā)現(xiàn)了一個(gè)豐富和不尋常的混合相變現(xiàn)象，既有連續(xù)相變也有不連續(xù)相變。這種混合相變主要表現(xiàn)在系統(tǒng)首先出現(xiàn)了一級(jí)的跳變(不連續(xù))，隨后又緩慢的變?yōu)榱?連續(xù))。文獻(xiàn)[83-84]研究了相依邊的長(zhǎng)度及地理位置限制等對(duì)網(wǎng)絡(luò)級(jí)聯(lián)失效過(guò)程的影響，研究結(jié)果表明在某種條件下表現(xiàn)的更為脆弱。文獻(xiàn)[85]研究給出了相互依賴網(wǎng)絡(luò)級(jí)聯(lián)失效過(guò)程中巨分支存在變化緩慢平臺(tái)的原因。

4 回顧與展望

本文對(duì)近年來(lái)國(guó)內(nèi)外關(guān)于網(wǎng)絡(luò)爆炸滲流的研究作了比較全面的綜述。網(wǎng)絡(luò)演化過(guò)程中的爆炸滲流現(xiàn)象是一驚人的發(fā)現(xiàn)。該發(fā)現(xiàn)豐富了傳統(tǒng)的滲流理論，將為物理學(xué)、網(wǎng)絡(luò)科學(xué)等的相變理論的研究提供新的視野、新的方法以及新的手段。同時(shí)，研究網(wǎng)絡(luò)爆炸滲流現(xiàn)象，揭示其產(chǎn)生機(jī)理，發(fā)現(xiàn)其豐富的臨界行為等又將對(duì)復(fù)雜網(wǎng)絡(luò)控制、魯棒性設(shè)計(jì)、動(dòng)力學(xué)行為的研究等提供廣闊的前景。

爆炸滲流的發(fā)現(xiàn)到研究雖然只有短短的幾年，但卻獲得了許多不同凡響的成果，單在Science，Nature，PRL三大刊物上發(fā)表的相關(guān)論文就有數(shù)十篇。但是，爆炸滲流研究仍然面臨許多挑戰(zhàn)性工 作[86-87]，例如，1) 目前采用的研究方法仍然以數(shù)值模擬為主，這必然受到規(guī)模效應(yīng)的巨大約束，能否開(kāi)發(fā)有效的爆炸滲流數(shù)學(xué)物理研究方法，將是一個(gè)長(zhǎng)期的艱巨任務(wù)；2) 爆炸滲流類(lèi)型的爭(zhēng)議目前仍然沒(méi)有定論，到底爆炸滲流現(xiàn)象與傳統(tǒng)的相變理論有何聯(lián)系仍然值得進(jìn)一步探索；3) Achlioptas過(guò)程下還會(huì)產(chǎn)生哪些奇特現(xiàn)象，這些現(xiàn)象對(duì)應(yīng)什么樣的真實(shí)物理過(guò)程，值得進(jìn)一步探索；4) 爆炸滲流與真實(shí)網(wǎng)絡(luò)的聯(lián)系研究還需要進(jìn)一步深入，等等。

[1] STAUFFER D, AHARONY A. Introduction to percolation theory[M]. London: Taylor&Francis, 1994.

[2] BROADBENT S R, HAMMERSLY J M.Percolation processes I. Crystals and Mazes[J].Proceedings of the Cambridge Philosophical Society, 1957, 53(3): 629-641.

[3] ERD?S P, RéNYI A. On the evolution of random graphs[J]. Publ Math Inst Hungar Acad Sci, 1960, 5(1): 17-61.

[4] ERD?S P, RéNYI A. On the evolution of random graphsII [J]. Bull Inst Int Stat, 1961, 38(4): 343-347.

[5] DE ARCANGELIS L, REDNER L, CONIGLIO A. Anomalous voltage distribution of random resistor networks and a new model for the backbone at the percolation threshold. [J]. Phys Rev B, 1985, 31(7):4725-4727.

[6] HENLEY C L. Statics of a “self-organized” percolation model [J].Phys Rev Lett, 1993, 71(1): 2741-2744.

[7] PAN R K, KIVELA M, SARAMAKI J, et al. Using explosive percolation in analysis of real-world networks[J]. Phys Rev E, 2011, 83(4): 046112.

[8] MOORE C, NEWMAN M E J. Epidemics and percolation in small-world networks[J]. Phys Rev E, 2000, 61(5): 5678-5682.

[9] GILBERT E N. Random graphs[J]. Ann Math Statist, 1959, 30(4): 1141-1144.

[10] BOLLOBáS B, JANSON S, RIORDAN O. The phase transition in inhomogeneous random graphs[J].Random Structures & Algorithms,2007, 31(1): 3-122.

[11] YANG Y, WANG J H. Network observability transitions [J]. Phys Rev Lett, 2012, 109(25): 258701.

[12] BOHMAN T, FRIEZE A.Avoiding a giant component[J]. Random Structures & Algorithms, 2001, 19(1), 75-85.

[13] SPENCER J, WORMALD N. Birth control for giants[J]. Combinatorica, 2007, 27(5): 587-628.

[14] ACHLIOPTAS D, D’SOUZA R M, SPENCER J. Explosive percolation in random networks[J]. Science, 2009, 323(5920): 1453-1555.

[15] D’SOUZA R M, MITZENMACHER M .Local cluster aggregation models of explosive percolation[J]. Phys Rev Lett, 2010, 104(19): 195702 .

[16] CHO Y S, KAHNG B, KIM D. Cluster aggregation model for discontinuous percolation transition [J]. Phys Rev E, 2010, 81(3): 030103.

[17] CHO Y S, KIM J S, PARK J, et al. Percolation transitions in scale-free networks under the Achlioptas process[J]. Phys Rev Lett, 2009, 103(13): 135702.

[18] RADICCHI F, FORTUNATO S. Explosive percolation in scale-free networks[J]. Phys Rev Lett, 2009, 103(16): 168701.

[19] GOMEZ-GARDENES J, GOMEZ S, ARENAS A, et al. Explosive synchronization transitions in scale-free networks[J]. Phys Rev Lett, 2011, 106(12): 128701.

[20] CHUNG F, LU L. Connected components in random graphs with given expected degree sequences[J]. Annals of Combinatorics, 2002, 6(2): 125-145.

[21] ARAúJO N A M, HERRMANN H J. Explosive percolation via control of the largest cluster[J]. Phys Rev Lett, 2010, 105(3): 035701.

[22] BOHMAN T, FRIEZE A, WORMALD N C. Avoidance of a giant component in half the edge set of a random graph[J]. Random Structures and Algorithms, 2004, 25(4): 432-449.

[23] CHEN W , D’SOUZA R M. Explosive percolation with multiple giant components[J]. Phys Rev Lett, 2011, 106(11): 115701.

[24] CHEN W, ZHENG Z, D’SOUZA R M. Deriving an underlying mechanism for discontinuous percolation[J]. EPL, 2012, 100(6): 66006.

[25] CHEN W, NAGLER J, CHENG X, et al. Phase transitions in supercritical explosive percolation[J]. Phys Rev E, 2013, 87(5): 052130.

[26] CHEN W, CHENG X Q, ZHENG Z M, et al. Unstable supercritical discontinuous percolation transitions[J]. Phys Rev E, 2013, 88(4): 042152.

[27] CHEN W. Explosive percolation in random networks[M]. Berlin Heidelberg: Springer, 2014, 1-8.

[28] NAGLER J, LEVINA A, TIMME M. Impact of single links in competitive percolation[J]. Nature Physics, 2011, 7(3): 265-270.

[29] ASZTALOS A, TOROCZKAI Z. Network discovery by generalized random walks[J]. EPL, 2010, 92(5): 50008.

[30] SCHRENK K J, ARAúJO N A M, HERRMANN H J. Gaussian model of explosive percolation in three and higher dimensions[J]. Phys Rev E, 2011, 84(4): 041136.

[31] ZIFF R M. Scaling behavior of explosive percolation on the square lattice[J]. Phys Rev E, 2010, 82(5): 051105.

[32] CHAE H, YOOK S H, KIM Y. Explosive percolation on the Bethe lattice[J]. Phys Rev E, 2012, 85(5): 051118.

[33] CHOI W, YOOK S H, KIM Y. Bond-site duality and nature of the explosive-percolation phase transition on a two-dimensional lattice[J]. Phys Rev E, 2012, 86(5): 051126.

[34] BASTAS N, KOSMIDIS K, ARGYRAKIS P. Explosive site percolation and finite-size hysteresis[J]. Phys Rev E, 2011, 84(6): 066112.

[35] REIS S D S, MOREIRA A A, ANDRADE JR J S. Non-local product rules for percolation[J]. Phys Rev E, 2011, 85(4): 041112.

[36] LONGONE P, CENTRES P M, RAMIREZ-PASTOR A J. Percolation of aligned rigid rods on two-dimensional square lattices[J]. Phys Rev E, 2012, 85(1): 011108.

[37] LIU M X, FAN J F, LI L S, et al. Continuous percolation phase transitions of two-dimensional lattice networks under a generalized Achlioptas process[J]. Eur Phys J B, 2012, 85(4): 132.

[38] SCHRENK K J, FELDER A, DEFLORIN S, et al. Bohman-frieze-wormald model on the lattice, yielding a discontinuous percolation transition[J]. Phys Rev E, 2012, 85(3): 031103.

[39] ARAúJO N A M, ANDRADE JR J S, ZIFF R M, et al. Tricritical point in explosive percolation[J]. Phys Rev Lett, 2011, 106(9): 095703.

[40] CELLAI D, LAWLOR A, DAWSON K A, et al. Tricritical point in heterogeneous k-core percolation[J]. Phys Rev Lett, 2011, 107(17): 175703.

[41] JIA X, HONG J S, YANG H C, et al. Characteristics of phase transitions via intervention in random networks[J]. Chin Phys B, 2014, 23(7): 076401.

[42] HU J Q, YANG H C, YANG Y M. Two typical discontinuous transitions observed in generalized Achlioptas percolation process[J]. Chin Phys Lett, 2014, 31(7): 078901.

[43] SQUIRES S, SYTWU K, ALCALA D, et al. Weakly explosive percolation in directed networks[J]. Phys Rev E, 2013, 87(5): 052127.

[44] RADICCHI F, FORTUNATO S. Explosive percolation: A numerical analysis[J]. Phys Rev E, 2010,81(3): 036110.

[45] LI Y, TANG G, SONG L J. Numerical simulations of the phase transition property of the explosive percolation model on Erd?s-Rényi random network[J]. Acta Phys Sin, 2013, 62(4): 046401.

[46] FORTUNATO S, RADICCHI F. Explosive percolation in graphs[C]//Journal of Physics: Conference Series. [S.l.]: IOP, 2011, 297(1): 012009.

[47] CHOI W, YOOK S H, KIM Y. Explosive site percolation with a product rule[J]. Phys Rev E, 2011, 84(2): 02010.

[48] CHO Y S, KAHNG B. Suppression effect on explosive percolation[J]. Phys Rev Lett, 2011, 107(27): 275703.

[49] MANNA S S, CHATTERJEE A. A new route to explosive percolation[J]. Physica A: Statistical Mechanics and its Applications, 2011,390(2):177-182.

[50] FRIEDMAN E J, LANDSBERG A S. Construction and analysis of random networks with explosive percolation[J]. Phys Rev Lett, 2009, 103(25): 255701.

[51] MOREIRA A A, OLIVEIRA E A, REIS S D S, et al. Hamiltonian approach for explosive percolation[J]. Phys Rev E, 2010, 81(4): 040101.

[52] LEE S B, KIM J S. Absorbing phase transitions in diluted conserved threshold transfer process[J]. Phys Rev E, 2013, 87(3): 032117.

[53] LI J, OSTLING M. Corrected finite-size scaling in percolation[J]. Phys Rev E, 2012, 86(4): 040105.

[54] ZIFF M. Getting the jump on explosive percolation[J]. Science, 2013, 339(6124): 1159-1160.

[55] RIORDAN O, WARNKE L. Achlioptas processes can be nonconvergent[EB/OL]. (2012-7-26). http://arxiv-web3. library.cornell.edu/abs/1111.6177v1.

[56] HOOYBERGHS H, SCHAEYBROECK B V. Criterion for explosive percolation transitions on complex networks[J]. Phys Rev E, 2011, 83(3): 032101.

[57] CHUNG N N, CHEW L Y, LAI C H. Spectral analysis on explosive percolation[J]. EPL, 2013, 101(6): 66003.

[58] DA COSTA R A, DOROGOVTSEV S N, GOLTSEV A V, et al. Explosive percolation transition is actually continuous[J]. Phys Rev Lett, 2010, 105(25): 255701.

[59] GRASSBERGER P, CHRISTERNSEN C, BIZHANI B, et al. Explosive percolation is continuous, but with unusual finite size behavior[J]. Phys Rev Lett, 2011, 106(22): 225701.

[60] LEE H K, KIM B J, PARK H. Continuity of the explosive percolation transition[J]. Phys Rev E, 2011, 84(2): 020101.

[61] RIORDAN O, WARNKE L. Explosive percolation is continuous[J]. Science, 2011, 333(6040): 322-324.

[62] RIORDAN O, WARNKE L. Achlioptas process phase transitions are continuous[J]. The Annals of Applied Probability, 2012, 22(4): 1450-1464.

[63] NAGLER J, TIESSEN T, GUTCH H W. Continuous percolation with discontinuities[J]. Phys Rev X, 2012, 2(3): 031009 .

[64] CHO Y S, HWANG S, HERRMANN H J, et al. Avoiding a spanning cluster in percolation models[J]. Science, 2013, 339(6124): 1185-1187.

[65] CHOI W, CHAE H, YOOK S H, et al. Dimensional dependence of phase transitions in explosive percolation[J]. Phys Rev E, 2014, 90(2): 022123.

[66] DA COSTA R A, DOROGOVTSEV S N, GOLTSEV A V, et al. Critical exponents of the explosive percolation transition[J]. Phys Rev E, 2014, 89(4): 042148.

[67] DA COSTA R A, DOROGOVTSEV S N, GOLTSEV A V, et al. Solution of the explosive percolation quest: scaling functions and critical exponents[J]. Phys Rev E, 2014, 90(2): 022145.

[68] YANG Z,WEI W. Formation mechanism and size features of multiple giant clusters in generic percolation processes[J]. Phys Rev E 2012, 86(5): 051103 .

[69] QIAN J H, HAN D D, MA Y G. Criticality and continuity of explosive site percolation in random networks[J]. EPL, 2012, 100(4): 48006.

[70] TIAN L, SHI D N. The nature of explosive percolation phase transition[J]. Phys Lett A. 2012, 376(4): 286-289.

[71] FAN J, LIU M, LI L, et al. Continuous percolation phase transitions of random networks under a generalized Achlioptas process[J]. Phys Rev E, 2012, 85(6): 061110.

[72] RIORDAN O, WARNKE L. Convergence of Achlioptas processes via differential equations with unique solutions [EB/OL].(2013-6-27).http://arxiv.org/abs/1111.6179 .

[73] PANAGIOTOU K, SP?HEL R, STEGER A, et al. Explosive percolation in Erd?s-Rényi-like random graph processes[J]. Electronic Notes in Discrete Mathematics, 2011, 38(3): 699-704.

[74] ANDRADE JR J S , HERRMANN H J, MOREIRA A A, et al. Transport on exploding percolation clusters[J]. Phys Rev E, 2011, 83(3): 031133.

[75] ROZENFELD H D, GALLOS L K, MAKSE H A. Explosive percolation in the human protein homology network[J]. Eur Phys J B, 2010, 75(3): 305-310.

[76] BIZHANI G, PACZUSKI M, GRASSBERGER P. Discontinuous percolation transitions in epidemic processes, surface depinning in random media,and Hamiltonian random graphs [J]. Phys Rev E, 2012, 86(1): 011128.

[77] KIM Y, YUN Y, YOOK S H. Explosive percolation in a nanotube-based system[J]. Phys Rev E, 2010, 82(6): 061105.

[78] JOVANOVIC B, BULDYREV S V, HAVLIN S, et al. Punctuated equilibrium and “history-dependent” percolation[J]. Phys Rev E, 1994, 50(4): 2403-2406.

[79] BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature , 2010, 464(7291): 1025-1028.

[80] PARSHANI R, BULDYREV S V, HAVLIN S. Critical effect of dependency groups on the function of networks[J]. Proceedings of the National Academy of Sciences, 2011, 108(3): 1007-1010.

[81] SON S W, GRASSBERGER P, PACZUSKI M. Percolation transitions are not always sharpened by making networks interdependent[J]. Phys Rev Lett, 2011, 107(19): 195702.

[82] HU Y Q, KSHERIM B, COHEN R, et al. Percolation in interdependent and interconnected networks: abrupt change from second to first order transition[J]. Phys Rev E, 2011, 84(6): 066116.

[83] LI W, BASHAN A, BULDYREV S V, et al. Cascading failures in interdependent lattice networks: the critical role of the length of dependency links[J]. Phys Rev Lett, 2012, 108(22): 228702.

[84] BASHAN A, BEREZIN Y, BULDYREV S V, et al. The extreme vulnerability of interdependent spatially embedded networks[J]. Nature Physics, 2013, 9(10): 667-672.

[85] ZHOU D, BASHAN A, COHEN R, et al. Simultaneous first and second-order percolation transitions in interdependent networks[J]. Phys Rev E, 2014, 90(1): 012803.

[86] ARAúJO N A M, GRASSBERGER P, KAHNG B, et al. Recent advances and open challenges in percolation[J]. The European Physical Journal Special Topics, 2014, 223 (11), 2307-2321.

[87] BASTAS N, GIAZITZIDIS P, MARAGAKIS M, et al. Explosive percolation: unusual transitions of a simple model[J]. Physica A: Statistical Mechanics and its Applications, 2014, 407: 54-65.

編 輯 蔣 曉

Review of Explosive Percolation of the Complex Networks

CHEN Xiao-long1,2, YANG Chun1,2, LI Zhi-peng1, FU Chuan-ji1,3, YANG Hong-chun3, YANG Yu-ming2, SHI Xiao-hong1,2, and JIA xiao1,3

(1. Complex electronic information system of electromagnetic environment effect of State Key Laboratory Luoyang Henan 471003; 2. School of mathematical sciences, University of Electronic Science and Technology of China Chengdu 611731; 3. School of physical electronics, University of Electronic Science and Technology of China Chengdu 610054)

In this paper, we review the related works in explosive percolation, and give a detailed description of typical models and the main conclusions. Moreover, we show the applications of the explosive percolation in real-world networks. Lastly, we put forward a prospection of the research on the percolation.

explosive percolation; percolation transition; random networks; robustness

N94

A

10.3969/j.issn.1001-0548.2015.01.002

2014-03-14;

2014-12-03

國(guó)家實(shí)驗(yàn)室開(kāi)放課題基金(CEMEE2014K0209B)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金(ZYGX2011J046，ZYGX2012J046)；部級(jí)基金

陳小龍(1989-)，男，碩士生，主要從事復(fù)雜網(wǎng)絡(luò)爆炸滲流方面的研究.