怡涵++王猛

摘 要：該文研究了現(xiàn)實(shí)網(wǎng)絡(luò)中的滲流現(xiàn)象，該現(xiàn)象的研究可以用于分析現(xiàn)實(shí)中的網(wǎng)絡(luò)系統(tǒng)，諸如互聯(lián)網(wǎng)系統(tǒng)遭受攻擊以及疾病在人類接觸網(wǎng)絡(luò)中的傳播等一系列問(wèn)題。該文的主要思路是將Karrer等人提出的信息傳播算法應(yīng)用于兩個(gè)具體的網(wǎng)絡(luò)，即E-R隨機(jī)圖和美國(guó)供電網(wǎng)絡(luò)，采用迭代法求解方程得出上述網(wǎng)絡(luò)經(jīng)歷結(jié)點(diǎn)打擊之后，極大點(diǎn)聚占整網(wǎng)比例的估計(jì)值。此后，將該文計(jì)算的預(yù)測(cè)值與現(xiàn)實(shí)網(wǎng)絡(luò)進(jìn)行對(duì)比，并且分析了該算法出現(xiàn)偏差的主要原因。

關(guān)鍵詞：滲流 復(fù)雜網(wǎng)絡(luò) 信息傳播算法 迭代法

中圖分類號(hào)：P64 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）06（b）-0166-03

滲流，即以相同的概率p對(duì)格子或者復(fù)雜網(wǎng)絡(luò)中的邊或者點(diǎn)進(jìn)行隨機(jī)占據(jù)，研究格子或者整網(wǎng)的連通性問(wèn)題，是統(tǒng)計(jì)物理學(xué)中最好研究的過(guò)程之一。它被用作多孔介質(zhì)[1]，顆粒和復(fù)合材料[2]，電阻網(wǎng)絡(luò)[3]，森林火災(zāi)[4]以及許多其他科學(xué)系統(tǒng)的模型。Karrer等人提出了一種新穎的方法，作為輸入給定網(wǎng)絡(luò)的詳細(xì)拓?fù)浣Y(jié)構(gòu)，以預(yù)測(cè)滲流強(qiáng)度的值（和其他宏觀觀測(cè)值，如邊占據(jù)概率和點(diǎn)占據(jù)概率的函數(shù)[5]，特別是他們闡明了特定網(wǎng)絡(luò)的邊滲流臨界值是非回溯矩陣的最大特征值。Hamilton和Pryadko基于相同的理論方法研究了孤立網(wǎng)絡(luò)中的點(diǎn)滲流現(xiàn)象[6]，Radicchi[5]分析相了依網(wǎng)絡(luò)中邊和點(diǎn)的滲流模型[7]。該文將Karrer等人提出的信息傳播算法應(yīng)用于兩個(gè)具體的網(wǎng)絡(luò)，即E-R隨機(jī)圖和美國(guó)供電網(wǎng)絡(luò)，采用迭代法求解方程得出上述網(wǎng)絡(luò)經(jīng)歷結(jié)點(diǎn)打擊之后，極大點(diǎn)聚占整網(wǎng)比例的估計(jì)值。此后，將該文計(jì)算的預(yù)測(cè)值與現(xiàn)實(shí)網(wǎng)絡(luò)進(jìn)行對(duì)比，并且分析了該算法出現(xiàn)偏差的主要原因。

1 主要模型

該文主要分析點(diǎn)滲流模型。我們通常使用一個(gè)0-1矩陣來(lái)描述任何現(xiàn)實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，假設(shè)一個(gè)圖總共有N個(gè)節(jié)點(diǎn)和E條邊，（即，如果點(diǎn)i和j相連，則矩陣元素Ai，j =1，否則Ai，j =0）。如果是無(wú)向圖，則該矩陣是沿主對(duì)角線對(duì)稱的，也就有Ai，j=Aj，i，這樣我們可以只用一半的矩陣元素來(lái)描述該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，此外，我們將Ai，i設(shè)置為零，這樣鄰接矩陣的對(duì)角線元素都是0，該文所研究的網(wǎng)絡(luò)全部為無(wú)向圖。

滲流模型關(guān)注的另外一個(gè)關(guān)鍵概念即為點(diǎn)聚，假設(shè)有兩個(gè)結(jié)點(diǎn)，如果它們之間至少存在一條路徑，從其中一個(gè)結(jié)點(diǎn)出發(fā)，沿著該路徑可以到達(dá)另外一個(gè)結(jié)點(diǎn)，則這樣兩個(gè)結(jié)點(diǎn)同屬于一個(gè)點(diǎn)距，而整個(gè)網(wǎng)絡(luò)中擁有最大結(jié)點(diǎn)數(shù)量的點(diǎn)聚，則是滲流模型關(guān)注的重點(diǎn)。

在通常的點(diǎn)滲透模型中，每個(gè)點(diǎn)都以概率P被激活，也可以理解為P概率表示該點(diǎn)被保留，以1-P的概率被刪除，這代表了一種比較普遍的網(wǎng)絡(luò)打擊現(xiàn)象，例如，對(duì)互聯(lián)網(wǎng)中所有的網(wǎng)站都以相同的概率就行攻擊，社交網(wǎng)絡(luò)中以相同的概率刪除結(jié)點(diǎn)，等等。對(duì)于具體的保留概率P而言，P=0，沒(méi)有節(jié)點(diǎn)處于激活狀態(tài)，因此整個(gè)網(wǎng)絡(luò)中沒(méi)有任何的點(diǎn)距。對(duì)于P=1，所有結(jié)點(diǎn)都是激活的，網(wǎng)絡(luò)中相當(dāng)于沒(méi)有結(jié)點(diǎn)被刪除。

而Karrer等人[5]提出了信息傳播算法則著重考慮了上述激活概率，該方法需要對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)中的每一條邊列出方程，參見(jiàn)圖1?，F(xiàn)在我們假設(shè)對(duì)任何一條邊，i->j，來(lái)表示該邊導(dǎo)向的點(diǎn)聚不屬于極大點(diǎn)聚的概率，則依據(jù)圖1；我們有

（1）

特殊的如果j是葉子結(jié)點(diǎn)，則我們有。這樣，全圖E條邊總共有2E個(gè)方程。這2E個(gè)方程可以通過(guò)迭代解出來(lái)，如果j不是葉子結(jié)點(diǎn)，則的迭代初始值設(shè)定為0。

在此基礎(chǔ)上我們使用來(lái)表述結(jié)點(diǎn)j不屬于極大點(diǎn)聚的概率，此時(shí)我們有

（2）

而對(duì)于我們關(guān)注任意抽取一點(diǎn)，它經(jīng)歷結(jié)點(diǎn)打擊之后，屬于極大點(diǎn)距的概率即為

（3）

2 模型應(yīng)用

這里選擇兩個(gè)具體的網(wǎng)絡(luò)來(lái)應(yīng)用Karrer等人提出的算法，第一網(wǎng)絡(luò)是一個(gè)ER隨機(jī)圖，該包括10000個(gè)結(jié)點(diǎn)，并且任意結(jié)點(diǎn)之間出現(xiàn)一條連接的概率是0.0005，這意味著該網(wǎng)絡(luò)的每一個(gè)結(jié)點(diǎn)度平均值大致上是5。第二網(wǎng)絡(luò)是美國(guó)供電網(wǎng)絡(luò)，該網(wǎng)絡(luò)擁有4941個(gè)結(jié)點(diǎn)，該網(wǎng)絡(luò)的數(shù)據(jù)直接來(lái)源于文獻(xiàn)[8]。

從圖2和圖3的對(duì)比分析我們發(fā)現(xiàn)在ER隨機(jī)網(wǎng)絡(luò)中，信息傳播算法關(guān)于極大點(diǎn)聚占整網(wǎng)全部結(jié)點(diǎn)比例的預(yù)期值和實(shí)際值高度吻合，而在美國(guó)供電網(wǎng)絡(luò)中，信息傳播算法的預(yù)期值要高于實(shí)際值。因而，可以得信息傳播算法的預(yù)期計(jì)算只有在某些網(wǎng)絡(luò)中非常準(zhǔn)確，而在其他網(wǎng)絡(luò)中則不那么準(zhǔn)確。而該算法到底在哪些網(wǎng)絡(luò)中預(yù)期準(zhǔn)確，究竟哪些因素造成了該算法的誤差，則成為本文下面研究的重點(diǎn)問(wèn)題。

圖2為隨機(jī)ER圖中信息傳播算法預(yù)期結(jié)果與真實(shí)結(jié)果的對(duì)比。其中，S代表在網(wǎng)絡(luò)中隨機(jī)抽取一點(diǎn)，該點(diǎn)在經(jīng)歷結(jié)點(diǎn)打擊之后屬于極大點(diǎn)聚的概率。P代表結(jié)點(diǎn)激活或者保留概率。圖中的實(shí)線代表預(yù)期值，而圓圈實(shí)線代表真實(shí)結(jié)果。關(guān)于真實(shí)結(jié)果的計(jì)算，我們按照1-P在圖中隨機(jī)刪除結(jié)點(diǎn)，點(diǎn)數(shù)剩余圖中的極大子組所含的結(jié)點(diǎn)數(shù)量占原圖所有結(jié)點(diǎn)的比例。這種刪除和計(jì)算被重復(fù)進(jìn)行了100次，得出的均值作為真實(shí)值。

圖3為美國(guó)供電網(wǎng)絡(luò)中信息傳播算法預(yù)期結(jié)果與真實(shí)結(jié)果的對(duì)比。其中，S代表在網(wǎng)絡(luò)中隨機(jī)抽取一點(diǎn)，該點(diǎn)在經(jīng)歷結(jié)點(diǎn)打擊之后屬于極大點(diǎn)聚的概率。P代表結(jié)點(diǎn)激活或者保留概率。圖中的實(shí)線代表預(yù)期值，而圓圈實(shí)線代表真實(shí)結(jié)果。關(guān)于真實(shí)結(jié)果的計(jì)算，我們按照1-P在圖中隨機(jī)刪除結(jié)點(diǎn)，點(diǎn)數(shù)剩余圖中的極大子組所含的結(jié)點(diǎn)數(shù)量占原圖所有結(jié)點(diǎn)的比例。這種刪除和計(jì)算被重復(fù)進(jìn)行了100次，得出的均值作為真實(shí)值。

3 模型誤差來(lái)源討論

關(guān)于信息傳播算法，其算法創(chuàng)造者Karrer等人[5]曾經(jīng)指出，樹(shù)型結(jié)構(gòu)的網(wǎng)絡(luò)或者本地近似樹(shù)型結(jié)構(gòu)的網(wǎng)絡(luò)中應(yīng)用該算法的誤差最小，或者更為直白地說(shuō)，當(dāng)網(wǎng)絡(luò)中的環(huán)數(shù)量非常少的時(shí)候，該算法應(yīng)用的效果更好，至于為什么環(huán)會(huì)導(dǎo)致算法預(yù)測(cè)的不精確并沒(méi)有詳盡地說(shuō)明。

該文在研究信息傳播算法極其迭代算法時(shí)，首先觀察了，當(dāng)P=1的情況，此時(shí)，網(wǎng)絡(luò)未經(jīng)任何結(jié)點(diǎn)刪除，可以認(rèn)為是原始網(wǎng)絡(luò)、如果該算法對(duì)原始網(wǎng)絡(luò)極大點(diǎn)聚的估計(jì)值存在偏差，這種偏差一定會(huì)帶到結(jié)點(diǎn)刪除之后，導(dǎo)致結(jié)點(diǎn)刪除之后的預(yù)期值也不準(zhǔn)確。此時(shí)，公式（1）變成

（4）

按照該算法的代入規(guī)則，即如果j是葉子結(jié)點(diǎn)，則我們?cè)O(shè)定 否則設(shè)定其初始值為0，我們發(fā)現(xiàn)對(duì)于所有不存在環(huán)的點(diǎn)聚，我們將迭代得出所有以及所有的，這樣該點(diǎn)聚所有點(diǎn)不屬于極大點(diǎn)聚概率為1，這也意味著該點(diǎn)聚內(nèi)所有結(jié)點(diǎn)都不屬于極大點(diǎn)聚。而對(duì)于有環(huán)的點(diǎn)聚，我們通過(guò)迭代得出來(lái)導(dǎo)向葉子結(jié)點(diǎn)的其他的而整個(gè)子組的這意味著該點(diǎn)聚所有結(jié)點(diǎn)都屬于極大點(diǎn)聚。

這樣的一種設(shè)置，使得該模型對(duì)于兩種類型的網(wǎng)絡(luò)預(yù)測(cè)效果不佳，第一張情況是整個(gè)網(wǎng)絡(luò)的極大點(diǎn)聚不存在任何的環(huán)，這樣真實(shí)的極大點(diǎn)聚將被當(dāng)做非極大點(diǎn)聚來(lái)處理，計(jì)算的誤差此時(shí)會(huì)非常大。第二種情況就非極大點(diǎn)聚的點(diǎn)聚中許多都含有環(huán)，此時(shí)，這些非極大點(diǎn)聚都會(huì)被當(dāng)成極大點(diǎn)聚來(lái)處理，從而導(dǎo)致預(yù)期值計(jì)算誤差增大。

而講過(guò)對(duì)兩個(gè)具體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的觀察我們發(fā)現(xiàn)，在隨機(jī)ER圖中，非極大點(diǎn)聚中的環(huán)非常少，而極大點(diǎn)聚中確實(shí)存在著一定數(shù)量的環(huán)，因而可以解釋ER隨機(jī)網(wǎng)絡(luò)中，信息傳播算法預(yù)期值和真實(shí)值的接近程度非常高。而在美國(guó)供電網(wǎng)絡(luò)中環(huán)的數(shù)量比較多，經(jīng)過(guò)結(jié)點(diǎn)打擊之后，許多環(huán)都散步到非極大點(diǎn)聚當(dāng)中，這就使得概算在p的某些取值之下顯得不夠準(zhǔn)確。

5 結(jié)語(yǔ)

最后我們來(lái)討論一下信息傳播算法的應(yīng)用以及該文的一點(diǎn)小小的貢獻(xiàn)。信息傳播算法的優(yōu)勢(shì)在于對(duì)于任何現(xiàn)實(shí)存在的具體網(wǎng)絡(luò)，通過(guò)將其拓?fù)浣Y(jié)構(gòu)作為輸入，我們可以預(yù)測(cè)一下在特定結(jié)點(diǎn)保存比例之下，經(jīng)歷結(jié)點(diǎn)打擊會(huì)的網(wǎng)絡(luò)極大點(diǎn)聚規(guī)模。因?yàn)楝F(xiàn)實(shí)中這種預(yù)測(cè)可以發(fā)生在實(shí)際結(jié)點(diǎn)打擊之前，使我們對(duì)未來(lái)打擊發(fā)生之后網(wǎng)絡(luò)連通性有一定的預(yù)估。與此同時(shí)，極大點(diǎn)聚本身代表了某個(gè)網(wǎng)絡(luò)中信息傳遞的最大范圍，對(duì)其進(jìn)行估計(jì)顯然也有一定意義。由于其他一些研究已經(jīng)證明了對(duì)于結(jié)點(diǎn)數(shù)量龐大的網(wǎng)絡(luò)，環(huán)出現(xiàn)在非極大子組的概率非常小，這一定程度上保證了這種算法預(yù)測(cè)效果。而本文的一點(diǎn)貢獻(xiàn)在于明確分析得出該算法使用環(huán)境，并且對(duì)預(yù)測(cè)誤差的產(chǎn)生有了較為清晰的剖析，從而提示后續(xù)研究在使用這一算法時(shí)，應(yīng)該首先觀察網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否出現(xiàn)該文提出的兩種不適宜采用這種方法的情況，從而更加合理地使用這一方法。

參考文獻(xiàn)

[1] J. Machta， Phase transition in fractal porous media[J].Phys. Rev. Lett.1991，66，169-172.

[2] T.Odagaki and S.Toyofuku，Properties of percolationclusters in a model granular system in two dimensions.J.Phys.Cond. Mat.1998，10：6447-6452.

[3] L.de Arcangelis， S. Redner， and A. Coniglio，Anomalousvoltage distribution of random resistor networks and anew model for the backbone at the percolation threshold[J].Phys. Rev. B，1985，31：4725-4728.

[4] C.L.Henley，Statics of a self-organized percolationmodel[J].Phys.Rev.Lett.1993，71：2741-2744.

[5] B.Karrer，M.E.J.Newman， and L. Zdeborov_a， Phys.Rev.Lett.2014，113.

[6] K. E. Hamilton and L.P.Pryadko，Phys.Rev.Lett.2014，113：208701.

[7] F.Radicchi，Nature Phys.2015（11）：597.

[8] D.J.Watts and S.H.Strogatz，Collective dynamics ofsmall-worldnetworks[J].Nature.1998（393）：440-442.