爆發(fā)性逾滲模型的Shortest-path指數(shù)和Backbone指數(shù)

，

(合肥工業(yè)大學(xué)電子科學(xué)與應(yīng)用物理學(xué)院，安徽合肥230009)

幾何模型在統(tǒng)計物理和復(fù)雜系統(tǒng)的研究中扮演著重要的角色，為相變和臨界現(xiàn)象的理論研究提供了載體[1]，著名的例子包括Random Cluster模型、元胞自動機模型、逾滲模型等[2-8]。逾滲概念的提出距今已有約60年，最初用于模擬自然界中的森林火災(zāi)、流行病的傳播、多孔介質(zhì)中石油的流動等現(xiàn)象[6]。 隨后的研究顯示該模型存在非平凡的相變，因而引起統(tǒng)計物理學(xué)家的廣泛關(guān)注[7-8]。 普通逾滲中，人們以概率p往一個格子的連邊(edge)上放鍵(bond)，以1-p的概率不放。導(dǎo)致無窮大集團在無窮大格子上出現(xiàn)的最小p值記為pc，稱為逾滲閾值。爆發(fā)性逾滲采用了不同于普通逾滲的放鍵規(guī)則[9]。每打算往格子上放一根鍵，事先隨機選擇兩條edge作為候選放鍵位置，但最終只有一條edge的位置被放鍵，另一條edge的位置空置。 “二選一”時，常采用“乘積規(guī)則”，即分別計算兩條候選edge的端點所屬的兩個集團大小的乘積，其中使得乘積值較小的edge將被放鍵。 相比于普通逾滲，該規(guī)則使得巨大集團的形成推遲到來，而中等大小的集團的數(shù)目增多。 一旦接近相變點，集團大小可能會因極少數(shù)目鍵的加入而呈現(xiàn)爆發(fā)式增長，因而得名爆發(fā)性逾滲。爆發(fā)性逾滲最初被懷疑經(jīng)歷一級相變，隨后的研究表明其仍為連續(xù)相變，但擁有極其微小的序參量臨界指數(shù)β[10]。爆發(fā)性逾滲模型的一個典型應(yīng)用實例是Clusella等[11]曾利用它來探討計算機網(wǎng)絡(luò)的魯棒性。

爆發(fā)性逾滲與普通逾滲分屬不同的普適類，各自擁有一套獨立的臨界指數(shù)。借助于庫倫氣、共形場以及SLE等理論[12-13]，二維普通逾滲的臨界指數(shù)大多能夠解析地給出，但shortest-path指數(shù)dmin和backbone指數(shù)dB是例外，它們目前只有數(shù)值結(jié)果[14-15]。這兩個指數(shù)的定義可簡單地表達為：

lS～rdmin,lB～rdB,

(1)

式中r代表當(dāng)系統(tǒng)處在pc處時同屬一個無窮大集團的兩個點a、b之間的歐幾里得距離；lS代表a、b之間的最短路徑，在編程語言中，它指從a點出發(fā)通過鍵路徑到達b所需的最少的MC步數(shù)。在某些文獻中它也被稱作化學(xué)距離(chemical distance)[16]。為了解釋lB，我們設(shè)想鍵為導(dǎo)體棒，edge本身為絕緣體，現(xiàn)施電勢差于a、b之間，則所有的載流導(dǎo)體棒都稱為backbone鍵，由backbone鍵組成的路徑上所有格點的數(shù)目即為lB。由于觀測量lS和lB較為復(fù)雜，在實際的蒙特卡洛模擬中，人們往往借助一些其他更易于測量的物理量來間接獲得這兩個指數(shù)，且相應(yīng)的power-law關(guān)系中的自變量不再是r，而是線性系統(tǒng)尺寸L。例如，為獲得dB，文獻[14]的觀測量不是lB，而是backbone關(guān)聯(lián)函數(shù)。近年來，在普通逾滲問題的研究中，人們找到了兩個易于對dmin、dB實現(xiàn)精確測量的物理量[17-19]，分別是完全(complete)構(gòu)型上的圖形距離S和bridge-free構(gòu)型上的最大集團大小Cbf，它們在pc處滿足的標(biāo)度關(guān)系是

S～Ldmin,Cbf～LdB,

(2)

這兩個觀測量的定義將在第1節(jié)中作簡要介紹。

對于爆發(fā)性逾滲，截至目前，shortest-path指數(shù)和backbone指數(shù)既無解析解，也無數(shù)值解。在本工作中，我們假定公式(2)對爆發(fā)性逾滲依然有效，并利用蒙特卡洛模擬研究了周期性邊界條件下正方晶格上滿足乘積規(guī)則的爆發(fā)性逾滲，通過測量S和Cbf并進行數(shù)據(jù)分析，獲得了關(guān)于這兩個臨界指數(shù)的首個估計。

1 蒙特卡洛模擬

本文在正方格子上模擬了遵守乘積規(guī)則的爆發(fā)性逾滲模型，其逾滲閾值為pc=0.526 565(5)[20]，實際的模擬點為p=0.526 563 6，其位于文獻值的一個誤差棒之內(nèi)。這樣選擇的原因在于，我們的另一個尚未發(fā)表的工作顯示，該模型的臨界點可更精確地表達為pc=0.526 563 6(10)。在模擬中，正方晶格的線性尺寸涵蓋從L=4到L=8 192的多個尺寸，例如，L=4, 6, 8, 12, …, 6 144, 8 192。每個尺寸的樣本數(shù)不盡相同，總的來說大系統(tǒng)尺寸的樣本數(shù)少，而小系統(tǒng)尺寸的樣本數(shù)較多，例如，L≤512的各系統(tǒng)，樣本數(shù)均達到2千萬左右，而L≥6 144的大系統(tǒng)，樣本數(shù)僅10萬左右。

本工作中的兩個觀測量分別是在完全構(gòu)型和bridge-free構(gòu)型上取樣而得，下面介紹這兩種構(gòu)型產(chǎn)生的過程和相應(yīng)觀測量的取樣方法。

1.1 產(chǎn)生完全構(gòu)型

為了產(chǎn)生爆發(fā)性鍵逾滲的完全構(gòu)型，本文采用如下算法：

Step1: 從一個空的格子開始，每個格點i自成一個集團，集團編號與格點自身的編號相同；

Step2:從所有未被鍵占據(jù)的edge中隨機選擇兩條候選edge(分別記為e1和e2)，計算e1的兩個端點所屬的兩個集團大小的乘積；對e2作類似的操作；

Step3:使得乘積較小的edge位置將被放鍵，另一根edge處將被空置；若乘積相等，則從這兩根edge中隨機地選擇一根edge進行占據(jù)；

Step4:將新加入鍵的兩個端點所屬的兩個集團進行合并，并將合并后的集團編號進行更新；

Step5:重復(fù)Step2～4，直到格子上鍵總數(shù)達到預(yù)設(shè)值(等于pc×edge總數(shù)并取整)。

值得一提的是，在Step4中，我們事實上僅更新參與合并的兩個集團中較小的那個集團的編號，使其與較大的那個集團編號一樣。

鍵構(gòu)型產(chǎn)生后，采用Swendsen-Wang算法統(tǒng)計各個集團的大小[21]。在具體實施時，采用breadth-first搜索方案。在搜索時，從某個集團的具有最小編號的格點(稱為第0代seed site)出發(fā)，搜索它的所有最近鄰鄰居，其中位于集團上的那些鄰居構(gòu)成新一代seed sites(記為第1代)；接下來搜索第1代seed sites的所有最近鄰鄰居，那些位于集團上且此前未被搜索過的鄰居點構(gòu)成第2代seed sites；依此方案可以繼續(xù)搜索第3代，第4代，…，第m代。 其中m是該集團中最后一個被搜索的點所屬的seed sites代數(shù)。很顯然，構(gòu)型上的每一個集團都存在一個確定的m，值最大的記為m0。S=〈m0〉是m0的系綜平均值，方便起見，我們稱其為圖形距離。

1.2 產(chǎn)生bridge-free構(gòu)型

將完全構(gòu)型上的所有占據(jù)鍵根據(jù)其連通性特征分為兩類：橋鍵和非橋鍵。所謂橋鍵是指若被刪除，其兩個端點將分屬不同的集團；若被刪除后仍屬于同一集團，則該鍵為非橋鍵。若采用一定的算法刪除掉構(gòu)型上所有的橋鍵，就得到bridge-free構(gòu)型。為了獲得backbone指數(shù)的估計，我們測量bridge-free構(gòu)型上最大集團的大小，并取其系綜平均值Cbf。

b為樹枝鍵；j為樞紐鍵；未作標(biāo)記為非橋鍵。 圖1 3種構(gòu)型及3類鍵的例子Fig.1 An example for illustrating three types configurations

在實際的模擬中，為了更方便地刪除橋鍵，采用了類似文獻[18-19]的做法，將所有橋鍵進一步分類為樹枝鍵和樞紐鍵。樹枝鍵是指若其被刪除，其兩個端點中至少有一個屬于單點集團；一根樹枝鍵的刪除有可能導(dǎo)致新的樹枝鍵產(chǎn)生，因而在蒙特卡洛模擬中刪除樹枝鍵的過程是迭代式進行的。排除掉所有樹枝鍵后的構(gòu)型，稱為leaf-free構(gòu)型。接下來在leaf-free構(gòu)型上采用“回溯”(backtracking)法識別非橋鍵并進行標(biāo)記。回溯法識別非橋鍵的基本策略是，從集團上的一個點出發(fā)采用breadth-first方案搜索最近鄰鄰居，并將每一代seed sites與下一代鄰居點link起來。比如，用于link的數(shù)組father(j)=i表示j號格點是作為上一代seed sitei的下一代鄰居被搜索到并加入link列表的。 一旦某一代seed sitej′搜索到位于同一集團且已被訪問過的點i′，則意味著一個由鍵組成的封閉的環(huán)路被找到，環(huán)路徑上的每一根鍵必為非橋鍵。為了標(biāo)記這個環(huán)上的所有鍵為非橋，需要從i′,j′出發(fā)沿link列表反向查找各自的father，這個過程迭代地進行，直到找到共同的father為止。其他的環(huán)狀路徑也是采用這種方式進行查找和標(biāo)記。當(dāng)整個識別過程結(jié)束時，leaf-free構(gòu)型上所有被標(biāo)記為非橋的鍵組成的子構(gòu)型即為bridge-free構(gòu)型。 為方便直觀理解，本文提供了3種構(gòu)型及3類鍵的一個例子(圖1)。

2 數(shù)據(jù)分析

理論上，式(2)只在熱力學(xué)極限(系統(tǒng)為無窮大)條件下嚴格成立。考慮到蒙特卡洛方法只能模擬有限大小的系統(tǒng)，因此必須考慮有限尺度效應(yīng)。式(3)對S和Cbf進行擬合：

F(L)=LdO(a+bLy1)，

(3)

式中F代表觀測量S或Cbf，dO代表臨界指數(shù)dmin或dB，y1代表有限尺度修正的leading項修正指數(shù)。擬合的流程按照least-square標(biāo)準(zhǔn)進行。一個可以被接受的擬合應(yīng)保證χ2/dDF在O(1)數(shù)量級，其中χ2代表數(shù)據(jù)與擬合公式之間的殘差，dDF是自由度，定義為數(shù)據(jù)點的數(shù)目與擬合參數(shù)個數(shù)之差。實際操作中，一般將χ2/dDF≈1的擬合視為合理的。擬合結(jié)果呈現(xiàn)在表 1中，Lmin表示被用于擬合的數(shù)據(jù)來自最小尺寸為Lmin的那些系統(tǒng)。

2.1 Shortest-path指數(shù)dmin

在對S的擬合中，當(dāng)y1作為自由參數(shù)時，發(fā)現(xiàn)y1≈-0.35。為了減少一個擬合參數(shù)，將y1固定在y1=-0.35進行擬合，擬合結(jié)果見表1。為了判斷y1的輕微變化對臨界指數(shù)dmin的估計值的影響，將y1固定在其他值進行了擬合(未顯示于表格中)。 此外，還嘗試過在式(3)中添加subleading修正項cL-2進行擬合，但當(dāng)添上該項時，修正幅值b和c以及l(fā)eading修正指數(shù)y1均不能被MC數(shù)據(jù)所分辨(不確定度與中心值相當(dāng)，甚至大于中心值)。綜合各種各樣的擬合，我們給出關(guān)于shortest-path指數(shù)的最終估計結(jié)果為dmin=1.189(3)，為顯示關(guān)于誤差估計的可靠性，取dmin等于中心值、中心值加上3個誤差棒、中心值減去3個誤差棒分別畫了S/Ldmin關(guān)于L-0.35的數(shù)據(jù)點線圖(圖2)。理論上，dmin等于中心值時數(shù)據(jù)點應(yīng)呈現(xiàn)出一條近似的直線，而dmin等于另外兩個值時，在L很大的區(qū)域應(yīng)呈現(xiàn)出向上或向下的彎曲。圖2清楚地展示出了這種預(yù)期中的趨勢，表明關(guān)于dmin的估計是可靠的。

表1 觀測量S的擬合結(jié)果

圖2 S/Ldmin關(guān)于L-0.35的點線Fig.2 Points and curve of S/Ldmin versus L-0.35

Lminχ2/dDFdBaby12563847.4/74.5/61.545 0(5)1.544 0(8)1.002(4)1.009(6)-3.0(3)-3.9(6)-1-13845123.9/63.4/51.546 1(5)1.545 7(8)0.992(4)0.995(6)-696.0(100)-885.0(283)-2-27683.5/51.546 6(5)0.987(4)--

2.2 Backbone指數(shù)dB

對Cbf首先實施讓y1作為自由參數(shù)的擬合，但y1和b均不能被MC數(shù)據(jù)所分辨。為此，將y1固定在常見的修正指數(shù)y1=-1和-2處進行擬合，以評估修正指數(shù)y1的變化對臨界指數(shù)dB的影響。我們還嘗試了拋棄所有修正項，直接使用O(L)=aLdO進行擬合，擬合結(jié)果見表2。綜合這些擬合以及其他未顯示于表格中的擬合，得到關(guān)于dB的最終估計為dB=1.546(5)。為了展示結(jié)果的可靠性，取3個不同的dB值(中心值以及加、減3個誤差棒)去畫Cbf/LdB關(guān)于L-1的數(shù)據(jù)曲線。顯然，當(dāng)系統(tǒng)無窮大(L-1→0)且dB為中心值時，Cbf/LdB應(yīng)等于常數(shù)a(≈1)，數(shù)據(jù)點在圖中應(yīng)展示出一條近似的水平直線，而另外2個dB值則導(dǎo)致曲線在L-1→0的區(qū)域呈現(xiàn)出向上或向下的彎曲。這種預(yù)期中的現(xiàn)象在圖3中被清楚地觀察到，表明關(guān)于dB的估計也是可靠的。

圖3 Cbf/LdB隨L-1變化的點線Fig.3 Points and curve of Cbf/LdB versus L-1

3 討論和結(jié)論

通過蒙特卡洛模擬和細致的數(shù)據(jù)分析，獲得了周期性邊界條件下正方晶格上滿足乘積規(guī)則的爆發(fā)性逾滲模型的Shortest-path指數(shù)和Backbone指數(shù)分別為dmin=1.189(3)和dB=1.546(5)。這兩個指數(shù)(dmin,dB)在爆發(fā)性逾滲類系統(tǒng)中從未被解析地確定或數(shù)值地估計過， 因此本文的工作提供了關(guān)于它們的第一個估計。本工作預(yù)期達到的目的包含兩個方面：一是為本領(lǐng)域同行提供可靠的科學(xué)數(shù)據(jù)，拋磚引玉，期待能為人們將來解析地研究爆發(fā)性逾滲提供檢驗基礎(chǔ)；二是對測量dmin、dB的新方法的一次重要應(yīng)用，在今后的工作中，該方法還將應(yīng)用到更多的模型，如Ising模型和Potts模型。

對比后不難發(fā)現(xiàn)，爆發(fā)性逾滲的Shortest-path指數(shù)和Backbone指數(shù)均不同于普通逾滲，后者相應(yīng)的結(jié)果分別為dmin,普=1.130 77(2)[15]和dB，普=1.643 4(2)[14]。這表明兩個模型擁有不同的集團結(jié)構(gòu)特征，尤其是在集團的緊致性(compactness)方面。盡管爆發(fā)性逾滲擁有更大的pc值(或占據(jù)鍵濃度)，但其最大集團內(nèi)部格點彼此之間的連通度(或集團的緊致性)略低于普通逾滲的最大集團。此外，本文的結(jié)果也從臨界指數(shù)dmin、dB的角度再次印證爆發(fā)性逾滲模型與普通逾滲模型的確分屬于不同的普適類。由本工作出發(fā)還引申出一系列有待回答的問題。如前所述，本文研究的爆發(fā)性逾滲模型采用了乘積規(guī)則和周期性邊界條件。 一個自然的問題是：由該模型獲得的結(jié)果是否具有普遍性？例如，當(dāng)乘積規(guī)則改為求和規(guī)則，或者周期性邊界條件改為開放邊界條件時，dmin、dB的值是否會改變？探究這些問題，將有助于加深人們對具有非平凡規(guī)則的統(tǒng)計模型相變普適類性質(zhì)的理解。