劉婉璐，葉永升

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

社團(tuán)結(jié)構(gòu)對網(wǎng)絡(luò)穩(wěn)定性的影響分析

劉婉璐，葉永升

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

利用CSEN模型建立具有社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)，并用CNM算法對所建立的網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)分析，基于CML的相繼故障模型對所建立的網(wǎng)絡(luò)進(jìn)行隨機(jī)及蓄意攻擊，探討社團(tuán)結(jié)構(gòu)對網(wǎng)絡(luò)穩(wěn)定性的影響.結(jié)果表明網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)強(qiáng)度越大，網(wǎng)絡(luò)的穩(wěn)定性越強(qiáng)；網(wǎng)絡(luò)穩(wěn)定性存在一個界值，一旦網(wǎng)絡(luò)受到攻擊大于某閾值，故障會迅速擴(kuò)大到整個網(wǎng)絡(luò)，從而造成整個網(wǎng)絡(luò)崩潰.同時，給出不同社團(tuán)結(jié)構(gòu)對應(yīng)的網(wǎng)絡(luò)所能承受的隨機(jī)及蓄意攻擊的閾值，為監(jiān)控網(wǎng)絡(luò)安全調(diào)整網(wǎng)絡(luò)穩(wěn)定提供參考.

CSEN模型；社團(tuán)結(jié)構(gòu)；CNM算法；網(wǎng)絡(luò)穩(wěn)定性

0 引言

現(xiàn)實生活中很多系統(tǒng)都可看作一個網(wǎng)絡(luò)，隨著信息全球化的飛速發(fā)展，網(wǎng)絡(luò)的規(guī)模不斷擴(kuò)大，節(jié)點間的聯(lián)系也更加復(fù)雜，大規(guī)模的復(fù)雜網(wǎng)絡(luò)成為學(xué)術(shù)界的研究熱點［1］.隨著對復(fù)雜網(wǎng)絡(luò)的深入研究，人們發(fā)現(xiàn)很多網(wǎng)絡(luò)都有一個共同性質(zhì)——社團(tuán)結(jié)構(gòu)［2］，所謂社團(tuán)即是將網(wǎng)絡(luò)中的節(jié)點劃分成不同組，組內(nèi)節(jié)點聯(lián)系比較稠密，組間節(jié)點聯(lián)系比較稀疏.

近年來，很多學(xué)者更加關(guān)注對大規(guī)模復(fù)雜網(wǎng)絡(luò)的安全穩(wěn)定性研究.文獻(xiàn)［3］采用變量梯度分析法研究網(wǎng)絡(luò)的穩(wěn)定性，文獻(xiàn)［4］對非線性動力系統(tǒng)構(gòu)成的復(fù)雜網(wǎng)絡(luò)進(jìn)行研究，分析該網(wǎng)絡(luò)的同步性及隨機(jī)穩(wěn)定性.考慮到社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要結(jié)構(gòu)屬性［5］，本文將結(jié)合網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)性對網(wǎng)絡(luò)穩(wěn)定性進(jìn)行分析，探討社團(tuán)模塊度Q與網(wǎng)絡(luò)穩(wěn)定性的關(guān)系，揭示破壞網(wǎng)絡(luò)穩(wěn)定性和引起網(wǎng)絡(luò)崩潰的內(nèi)在機(jī)制.

1 建立網(wǎng)絡(luò)

為了探討社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)穩(wěn)定性之間的關(guān)系，首先需要建立具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)模型.此處，運(yùn)用具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)演化模型——CSEN模型［6］生成網(wǎng)絡(luò)，CSEN模型即Community Structured Evolving Network Model.

具體算法過程如下：

第1步：初始化.設(shè)初始網(wǎng)絡(luò)中有c0(c0＞1)個社團(tuán)，各個社團(tuán)的內(nèi)部由n0個兩兩相連的節(jié)點構(gòu)成，且這c0個社團(tuán)由c0(c0-1)/2條邊連接.

第2步：社團(tuán)增長.以概率p向網(wǎng)絡(luò)中添加一個新社團(tuán).該社團(tuán)仍是由n0個兩兩相連的節(jié)點所構(gòu)成.從新社團(tuán)中任選一個節(jié)點，經(jīng)過m條邊與其他社團(tuán)內(nèi)的節(jié)點相連接.

第3步：節(jié)點增長.以概率1-p向該網(wǎng)絡(luò)中添加一個新節(jié)點.該節(jié)點按照社團(tuán)規(guī)模優(yōu)先機(jī)制［7］選擇一個社團(tuán)并加入，對該節(jié)點引入m條邊，這m條邊以概率q與該節(jié)點所在社團(tuán)內(nèi)的其他節(jié)點相連，而以概率1-q與其他社團(tuán)內(nèi)的節(jié)點相連.

第4步：返回第2步，直到網(wǎng)絡(luò)達(dá)到所需規(guī)模為止.

通過多次隨機(jī)獨立實驗的統(tǒng)計平均，得到該模型所生成網(wǎng)絡(luò)的集聚譜分布（如圖1所示）.

圖1 集聚譜分布

圖2各個網(wǎng)絡(luò)對應(yīng)的社團(tuán)模塊度Q

圖1 中k表示節(jié)點，C(k)表示節(jié)點的集聚譜，此為100組數(shù)據(jù)得到的平均結(jié)果.結(jié)果表明，生成的網(wǎng)絡(luò)聚類系數(shù)較大，平均最短路徑長度較短，且通過簡單的參數(shù)調(diào)整即可控制網(wǎng)絡(luò).

2 分析生成網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)

以下采用Newman貪婪（CNM）算法［8］，對Q函數(shù)及輔助向量進(jìn)行改進(jìn)，并采取Clauset、Newman和Moore設(shè)計的數(shù)據(jù)結(jié)構(gòu)來存儲和更新Q函數(shù)，及對網(wǎng)絡(luò)進(jìn)行社團(tuán)化處理.

具體過程如下：

第1步：初始化.將網(wǎng)絡(luò)中的每個節(jié)點都看作一個社團(tuán)，初始的模塊度值Q=0.若節(jié)點i、j有邊相連，則邊權(quán)eij=1；若節(jié)點i、j無邊相連，則邊權(quán)，以a作為輔助向量，其元素.對ΔQ矩陣初始化，該矩陣元素滿足ΔQ=2(e-aa)，顯然ΔQ矩陣是稀疏矩陣.ijijij

第2步：從初始化的ΔQ矩陣中選取每行的最大元素，構(gòu)成最大堆H.

第3步：從最大堆H中找到最大的ΔQij，將對應(yīng)的社團(tuán)i、j進(jìn)行合并（不妨設(shè)i＜j），將合并之后的社團(tuán)標(biāo)記為j，并對矩陣ΔQ、最大堆H及輔助向量a進(jìn)行更新.

第4步：重復(fù)第2步，直到將所有的ΔQij由正值變?yōu)樨?fù)值.

最終，得到100組節(jié)點不同的網(wǎng)絡(luò)的模塊度值Q（如圖2所示）.

3 社團(tuán)結(jié)構(gòu)對受攻擊下的網(wǎng)絡(luò)穩(wěn)定性影響

為研究網(wǎng)絡(luò)在受攻擊下的穩(wěn)定性，在此采用隨機(jī)攻擊和蓄意攻擊［9］2種攻擊方式.隨機(jī)攻擊即隨機(jī)地移除某些節(jié)點及與其相連的所有邊；蓄意攻擊即有意地移除某些介數(shù)較大的節(jié)點及與其相連的邊.若抗攻擊性較強(qiáng)則稱網(wǎng)絡(luò)有較強(qiáng)的魯棒性，即認(rèn)為網(wǎng)絡(luò)的穩(wěn)定性較強(qiáng)，否則認(rèn)為網(wǎng)絡(luò)的穩(wěn)定性較弱.圖3給出了網(wǎng)絡(luò)穩(wěn)定性閾值Rc隨社團(tuán)模塊度Q的變化關(guān)系.

圖3 網(wǎng)絡(luò)穩(wěn)定性閾值Rc隨社團(tuán)模塊度Q的變化關(guān)系

基于耦合映像格子（CML）的相繼故障模型［10］通過網(wǎng)絡(luò)受到擾動R所能達(dá)到的閾值Rc（當(dāng)R≥Rc時網(wǎng)絡(luò)中所有的節(jié)點都在下一時刻發(fā)生故障）的大小來衡量關(guān)聯(lián)網(wǎng)絡(luò)的穩(wěn)定性.在模擬過程中，對應(yīng)相同的社團(tuán)結(jié)構(gòu)選擇相同的節(jié)點進(jìn)行隨機(jī)攻擊（蓄意攻擊采取同樣的方法）.數(shù)值實驗采取的參數(shù)m=5，ε=0.6，N在[1 325,1 425]之間，其中m指攻擊某個節(jié)點的時刻，ε指耦合強(qiáng)度，N指網(wǎng)絡(luò)規(guī)模，100次實驗之后得到網(wǎng)絡(luò)穩(wěn)定性隨社團(tuán)模塊度Q的變化關(guān)系（如圖3所示）.

從圖3可以看出，無論是隨機(jī)攻擊還是蓄意攻擊，閾值Rc都隨著社團(tuán)模塊度Q的增加而增加.這說明網(wǎng)絡(luò)社團(tuán)模塊度Q越大其魯棒性越強(qiáng)，Q越小網(wǎng)絡(luò)越脆弱.當(dāng)Q值靠近0時，無論是隨機(jī)攻擊還是蓄意攻擊，較小的擾動都可能造成網(wǎng)絡(luò)的崩潰.

4 總結(jié)與展望

本文分析了復(fù)雜網(wǎng)絡(luò)穩(wěn)定性與社團(tuán)結(jié)構(gòu)之間的相互關(guān)系，經(jīng)100組實驗得到的平均數(shù)據(jù)可知，社團(tuán)模塊度Q越大網(wǎng)絡(luò)魯棒性越強(qiáng)，即網(wǎng)絡(luò)越穩(wěn)定，Q越小網(wǎng)絡(luò)越脆弱.給出了各個Q值對應(yīng)的攻擊閾值Rc，即隨機(jī)或蓄意攻擊網(wǎng)絡(luò)某些節(jié)點，當(dāng)R≥Rc時，網(wǎng)絡(luò)中的所有節(jié)點都在下一時刻發(fā)生故障.這對現(xiàn)實網(wǎng)絡(luò)的監(jiān)控和調(diào)整有一定的指導(dǎo)意義，如在股票市場中可根據(jù)社團(tuán)模塊度Q及市場受攻擊的大小R對網(wǎng)絡(luò)進(jìn)行有效地調(diào)整和監(jiān)控.另外，在攻擊R臨近閾值Rc時，重點調(diào)整哪些節(jié)點才能避免下一時刻所有節(jié)點都發(fā)生故障，是進(jìn)一步需要探討的問題.

［1］BARABASI A L.Linked：The new science of networks［M］.Massaehusetts：Persus Publishing，2002.

［2］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［3］毛凱.復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性與魯棒性研究［J］.計算機(jī)科學(xué)，2015，42（4）：85-88.

［4］嚴(yán)洲.復(fù)雜網(wǎng)絡(luò)隨機(jī)穩(wěn)定性和同步性研究［D］.杭州：浙江大學(xué)，2012.

［5］FORTUNATO S，CASTELLANO C.Community structure in graphs［J］.Encyclopedia of Complexity&Systems Science，2007（12）：490-512.

［7］LI Chunguang，CHEN Guanrong.Modeling of weighted evolving networks with community structures［J］.Physica A，2006，370（2）：869-876.

［8］CLAUSET A，NEWMAN M E J，MOORE C.Finding community structure in very large networks［J］.Physical Review E，2004，70（6）：066111.

［9］CRUCITTI P，LATORA V.Error and attack tolerance of complex networks［J］.Physica A，2004，340（1/2/3）：388-394.

［10］WANG Xiaofan，XU Jian.Cascading failures in coupled map lattices［J］.Physical Review E，2004，70（5）：056113.

Effects Analysis of Community Structure on Stability of Complex Networks

LIU Wanlu,YE Yongsheng
（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）

Complex networks with community structure are constructed by using the CSEN model，and commu?nity structures are detected by the CNM algorithm in the constructed networks.Random and deliberate attack?ing on the networks based on the CML cascading failures model is used to find the relationship between com?munity structures and stability of networks.The results show that the greater modularity means the stronger stability and robustness of networks，and there is a critical value.Once the networks are attacked greater than the value，failures will expand to the entire networks fast，and the entire networks will collapse.The critical values that adjust different community structures under random or deliberate attacking are given.All results provide a reference for monitoring network security and regulating the network stability.

CSEN model；community structure；CNM algorithm；stability of complex networks

O 29

A

2095-0691（2016）04-0030-03

2016-07-06

國家自然科學(xué)基金項目（61300048）；安徽省自然科學(xué)研究項目（1408085MA08）；安徽省高校自然科學(xué)研究項目（KJ2016A633）

劉婉璐（1988- ），女，安徽淮北人，碩士，助教，研究方向：復(fù)雜網(wǎng)絡(luò).