滲流模型在現實網絡中的應用探討

怡涵++王猛

摘 要：該文研究了現實網絡中的滲流現象，該現象的研究可以用于分析現實中的網絡系統，諸如互聯網系統遭受攻擊以及疾病在人類接觸網絡中的傳播等一系列問題。該文的主要思路是將Karrer等人提出的信息傳播算法應用于兩個具體的網絡，即E-R隨機圖和美國供電網絡，采用迭代法求解方程得出上述網絡經歷結點打擊之后，極大點聚占整網比例的估計值。此后，將該文計算的預測值與現實網絡進行對比，并且分析了該算法出現偏差的主要原因。

關鍵詞：滲流 復雜網絡 信息傳播算法 迭代法

中圖分類號：P64 文獻標識碼：A 文章編號：1674-098X（2017）06（b）-0166-03

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

1 主要模型

該文主要分析點滲流模型。我們通常使用一個0-1矩陣來描述任何現實網絡的拓撲結構，假設一個圖總共有N個節點和E條邊，（即，如果點i和j相連，則矩陣元素Ai，j =1，否則Ai，j =0）。如果是無向圖，則該矩陣是沿主對角線對稱的，也就有Ai，j=Aj，i，這樣我們可以只用一半的矩陣元素來描述該網絡拓撲結構，此外，我們將Ai，i設置為零，這樣鄰接矩陣的對角線元素都是0，該文所研究的網絡全部為無向圖。

滲流模型關注的另外一個關鍵概念即為點聚，假設有兩個結點，如果它們之間至少存在一條路徑，從其中一個結點出發，沿著該路徑可以到達另外一個結點，則這樣兩個結點同屬于一個點距，而整個網絡中擁有最大結點數量的點聚，則是滲流模型關注的重點。

在通常的點滲透模型中，每個點都以概率P被激活，也可以理解為P概率表示該點被保留，以1-P的概率被刪除，這代表了一種比較普遍的網絡打擊現象，例如，對互聯網中所有的網站都以相同的概率就行攻擊，社交網絡中以相同的概率刪除結點，等等。對于具體的保留概率P而言，P=0，沒有節點處于激活狀態，因此整個網絡中沒有任何的點距。對于P=1，所有結點都是激活的，網絡中相當于沒有結點被刪除。

而Karrer等人[5]提出了信息傳播算法則著重考慮了上述激活概率，該方法需要對現實網絡中的每一條邊列出方程，參見圖1。現在我們假設對任何一條邊，i->j，來表示該邊導向的點聚不屬于極大點聚的概率，則依據圖1；我們有

（1）

特殊的如果j是葉子結點，則我們有。這樣，全圖E條邊總共有2E個方程。這2E個方程可以通過迭代解出來，如果j不是葉子結點，則的迭代初始值設定為0。

在此基礎上我們使用來表述結點j不屬于極大點聚的概率，此時我們有

（2）

而對于我們關注任意抽取一點，它經歷結點打擊之后，屬于極大點距的概率即為

（3）

2 模型應用

這里選擇兩個具體的網絡來應用Karrer等人提出的算法，第一網絡是一個ER隨機圖，該包括10000個結點，并且任意結點之間出現一條連接的概率是0.0005，這意味著該網絡的每一個結點度平均值大致上是5。第二網絡是美國供電網絡，該網絡擁有4941個結點，該網絡的數據直接來源于文獻[8]。

從圖2和圖3的對比分析我們發現在ER隨機網絡中，信息傳播算法關于極大點聚占整網全部結點比例的預期值和實際值高度吻合，而在美國供電網絡中，信息傳播算法的預期值要高于實際值。因而，可以得信息傳播算法的預期計算只有在某些網絡中非常準確，而在其他網絡中則不那么準確。而該算法到底在哪些網絡中預期準確，究竟哪些因素造成了該算法的誤差，則成為本文下面研究的重點問題。

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

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

3 模型誤差來源討論

關于信息傳播算法，其算法創造者Karrer等人[5]曾經指出，樹型結構的網絡或者本地近似樹型結構的網絡中應用該算法的誤差最小，或者更為直白地說，當網絡中的環數量非常少的時候，該算法應用的效果更好，至于為什么環會導致算法預測的不精確并沒有詳盡地說明。

該文在研究信息傳播算法極其迭代算法時，首先觀察了，當P=1的情況，此時，網絡未經任何結點刪除，可以認為是原始網絡、如果該算法對原始網絡極大點聚的估計值存在偏差，這種偏差一定會帶到結點刪除之后，導致結點刪除之后的預期值也不準確。此時，公式（1）變成

（4）

按照該算法的代入規則，即如果j是葉子結點，則我們設定 否則設定其初始值為0，我們發現對于所有不存在環的點聚，我們將迭代得出所有以及所有的，這樣該點聚所有點不屬于極大點聚概率為1，這也意味著該點聚內所有結點都不屬于極大點聚。而對于有環的點聚，我們通過迭代得出來導向葉子結點的其他的而整個子組的這意味著該點聚所有結點都屬于極大點聚。

這樣的一種設置，使得該模型對于兩種類型的網絡預測效果不佳，第一張情況是整個網絡的極大點聚不存在任何的環，這樣真實的極大點聚將被當做非極大點聚來處理，計算的誤差此時會非常大。第二種情況就非極大點聚的點聚中許多都含有環，此時，這些非極大點聚都會被當成極大點聚來處理，從而導致預期值計算誤差增大。

而講過對兩個具體網絡拓撲結構的觀察我們發現，在隨機ER圖中，非極大點聚中的環非常少，而極大點聚中確實存在著一定數量的環，因而可以解釋ER隨機網絡中，信息傳播算法預期值和真實值的接近程度非常高。而在美國供電網絡中環的數量比較多，經過結點打擊之后，許多環都散步到非極大點聚當中，這就使得概算在p的某些取值之下顯得不夠準確。

5 結語

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

參考文獻

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