安沈昊,于榮歡

(航天工程大學(xué) 復(fù)雜電子系統(tǒng)仿真實(shí)驗(yàn)室,北京 101400)

復(fù)雜網(wǎng)絡(luò)理論研究最早可追溯到18世紀(jì)由數(shù)學(xué)家歐拉提出的“七橋問(wèn)題”,將陸地抽象為點(diǎn),將連接陸地的橋梁抽象為邊,點(diǎn)與連接點(diǎn)的邊就組成了網(wǎng)絡(luò).隨著復(fù)雜系統(tǒng)的快速發(fā)展,復(fù)雜網(wǎng)絡(luò)的分析方法被廣泛應(yīng)用于社會(huì)、經(jīng)濟(jì)、軍事等領(lǐng)域,如在線社交網(wǎng)絡(luò)、國(guó)際貿(mào)易、現(xiàn)代化信息作戰(zhàn)系統(tǒng)等.

目前,復(fù)雜網(wǎng)絡(luò)各分支方向的研究已引起廣泛關(guān)注,國(guó)內(nèi)多名學(xué)者先后對(duì)復(fù)雜網(wǎng)絡(luò)的相關(guān)理論、研究和應(yīng)用方向進(jìn)行系統(tǒng)的整理和總結(jié)[1-6].朱涵等最早介紹了復(fù)雜網(wǎng)絡(luò)理論[7],何宇等從部件、權(quán)重、機(jī)制、動(dòng)態(tài)變化及側(cè)重條件5 個(gè)方面整理其演化模型并分類[8],周濤等詳述大數(shù)據(jù)時(shí)代下復(fù)雜網(wǎng)絡(luò)亟需解決的十大問(wèn)題[9].隨著復(fù)雜網(wǎng)絡(luò)理論研究的發(fā)展,有必要繼續(xù)對(duì)其理論進(jìn)行歸納和整理,以推動(dòng)進(jìn)一步研究.

1 復(fù)雜網(wǎng)絡(luò)基本概念

關(guān)于什么是復(fù)雜網(wǎng)絡(luò),目前還沒(méi)有一個(gè)統(tǒng)一的定義.錢學(xué)森先生認(rèn)為具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)可稱為復(fù)雜網(wǎng)絡(luò).在研究網(wǎng)絡(luò)時(shí),人們往往只關(guān)注節(jié)點(diǎn)之間是否存在連邊,忽視節(jié)點(diǎn)位置、邊的性質(zhì)等因素.復(fù)雜網(wǎng)絡(luò)就可看作復(fù)雜系統(tǒng)的高度抽象,將網(wǎng)絡(luò)中的節(jié)點(diǎn)抽象為復(fù)雜系統(tǒng)中的個(gè)體,網(wǎng)絡(luò)中的邊抽象為復(fù)雜系統(tǒng)中個(gè)體之間的關(guān)系,這樣由大量的節(jié)點(diǎn)及節(jié)點(diǎn)間相互連接的邊所構(gòu)成的網(wǎng)絡(luò)就可稱為復(fù)雜網(wǎng)絡(luò).

1.1 度分布

節(jié)點(diǎn)的度定義為與該節(jié)點(diǎn)相連的邊的個(gè)數(shù),反映該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度.網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值是該網(wǎng)絡(luò)的平均度.網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布表示為分布函數(shù)P(k),代表該節(jié)點(diǎn)的度等于k的概率,也可代表網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)數(shù)在總節(jié)點(diǎn)數(shù)中所占的比例.

1.2 平均路徑長(zhǎng)度

連接兩個(gè)節(jié)點(diǎn)的最短路徑所用邊的個(gè)數(shù)為兩節(jié)點(diǎn)之間的距離,網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間距離的平均值為網(wǎng)絡(luò)的平均路徑長(zhǎng)度.平均路徑長(zhǎng)度反映了節(jié)點(diǎn)之間聯(lián)系的緊密程度和網(wǎng)絡(luò)的大小.

1.3 集聚系數(shù)

節(jié)點(diǎn)的集聚系數(shù)表示為鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)與最大可能邊數(shù)之比,反映一個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)之間相互連接的情況.網(wǎng)絡(luò)的集聚系數(shù)表示為所有節(jié)點(diǎn)集聚系數(shù)的平均值,反映了網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)特性.

1.4 介數(shù)

介數(shù)分為點(diǎn)介數(shù)和邊介數(shù).點(diǎn)介數(shù)表示為經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑數(shù)目占所有最短路徑數(shù)目的比例,邊介數(shù)表示為所有經(jīng)過(guò)該邊的最短路徑數(shù)目占所有最短路徑數(shù)目的比例.介數(shù)反映了相應(yīng)節(jié)點(diǎn)或邊在整個(gè)網(wǎng)絡(luò)中的作用和地位.

2 典型復(fù)雜網(wǎng)絡(luò)模型

網(wǎng)絡(luò)的結(jié)構(gòu)與功能聯(lián)系緊密,拓?fù)浣Y(jié)構(gòu)決定功能,功能影響拓?fù)浣Y(jié)構(gòu)演化.為研究復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性,Erdos 與Renyi 最早根據(jù)隨機(jī)圖理論構(gòu)建了隨機(jī)網(wǎng)絡(luò)模型(ER 模型)[10],但ER 模型的連接規(guī)則與節(jié)點(diǎn)分布的隨機(jī)性使其不適合研究真實(shí)復(fù)雜網(wǎng)絡(luò).因此,基于已有網(wǎng)絡(luò)模型的缺陷與真實(shí)網(wǎng)絡(luò)研究的需求,學(xué)者們提出了大量不同的復(fù)雜網(wǎng)絡(luò)模型.

2.1 小世界網(wǎng)絡(luò)模型

通常認(rèn)為如果網(wǎng)絡(luò)的平均路徑長(zhǎng)度L與節(jié)點(diǎn)數(shù)N的對(duì)數(shù)成正比,則稱該網(wǎng)絡(luò)具有小世界效應(yīng).絕大部分真實(shí)復(fù)雜網(wǎng)絡(luò)都具有小世界效應(yīng),即具有較小的平均路徑長(zhǎng)度和較大的集聚系數(shù).

基于此,Watts 和Strogatz 提出了小世界網(wǎng)絡(luò)模型(WS 模型)[11].在一個(gè)包含N個(gè)節(jié)點(diǎn)的環(huán)狀規(guī)則網(wǎng)絡(luò)中,以順時(shí)針?lè)较蛟L問(wèn)每個(gè)節(jié)點(diǎn)并選取與當(dāng)前節(jié)點(diǎn)連接的邊,以概率p對(duì)每條邊進(jìn)行刪除和重連,將邊的另一端隨機(jī)連接到其他節(jié)點(diǎn)上,在這個(gè)過(guò)程中可能會(huì)出現(xiàn)長(zhǎng)程邊從而減小網(wǎng)絡(luò)的平均路徑長(zhǎng)度,以概率1-p保留原有邊,整個(gè)過(guò)程中不允許出現(xiàn)重復(fù)連接和自環(huán).可以改變p值來(lái)調(diào)節(jié)網(wǎng)絡(luò)的隨機(jī)性,并保持網(wǎng)絡(luò)中邊數(shù)的平衡,p=0 時(shí)對(duì)應(yīng)規(guī)則網(wǎng)絡(luò),p=1 時(shí)對(duì)應(yīng)隨機(jī)網(wǎng)絡(luò).通過(guò)這種方法構(gòu)造出來(lái)的小世界網(wǎng)絡(luò)具有較小的平均路徑長(zhǎng)度和較大的集聚系數(shù).

考慮到WS 模型的構(gòu)造方法可能會(huì)破壞網(wǎng)絡(luò)的連通性,Newman 和Watts 對(duì)其進(jìn)行了改進(jìn),提出了NW模型[12].NW 模型的改進(jìn)之處在于用隨機(jī)化加邊取代了隨機(jī)化重連,即以概率p在隨機(jī)選取的節(jié)點(diǎn)對(duì)之間添加連接邊,不改動(dòng)原有連接邊,且不允許出現(xiàn)重復(fù)連接和自環(huán).當(dāng)網(wǎng)絡(luò)規(guī)模N足夠大而p足夠小時(shí),WS 模型與NW 模型在本質(zhì)上是一樣的.

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

在隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)中,節(jié)點(diǎn)的度分布近似為泊松分布.但研究者發(fā)現(xiàn)大多數(shù)真實(shí)復(fù)雜網(wǎng)絡(luò)的度分布服從冪律分布,即隨著節(jié)點(diǎn)度k增大,分布函數(shù)P(k)衰減速度變小.

針對(duì)這種情況,Barabas 和Albert 提出了無(wú)標(biāo)度網(wǎng)絡(luò)模型(BA 模型)[13]從兩方面來(lái)描述其產(chǎn)生機(jī)制,即網(wǎng)絡(luò)增長(zhǎng)和優(yōu)先連接.網(wǎng)絡(luò)增長(zhǎng)意味著網(wǎng)絡(luò)中不斷有新節(jié)點(diǎn)加入并連接到已存在的節(jié)點(diǎn)上,初始網(wǎng)絡(luò)包含m0個(gè)節(jié)點(diǎn)和m1條邊,每個(gè)時(shí)間步增加一個(gè)新節(jié)點(diǎn)和m(m≤m0)條邊,連接到m個(gè)已有的節(jié)點(diǎn)上;優(yōu)先連接意味著新增加的節(jié)點(diǎn)會(huì)優(yōu)先連接度值較大的節(jié)點(diǎn),將節(jié)點(diǎn)i的度ki和所有節(jié)點(diǎn)度的總和k的比值作為新增加的節(jié)點(diǎn)連接到節(jié)點(diǎn)i的概率,新增加的節(jié)點(diǎn)根據(jù)此概率選擇所要連接的m個(gè)節(jié)點(diǎn).經(jīng)過(guò)t個(gè)時(shí)間步后初始網(wǎng)絡(luò)就會(huì)演化成具有m0+t個(gè)節(jié)點(diǎn)和m1+mt條邊的網(wǎng)絡(luò),其中大多數(shù)節(jié)點(diǎn)度值較小,少數(shù)節(jié)點(diǎn)度值很大.結(jié)果顯示,BA 網(wǎng)絡(luò)不僅兼具小世界效應(yīng)和較大的集群系數(shù),其度分布也滿足冪律分布.

2.3 局域世界網(wǎng)絡(luò)模型

BA 模型中的優(yōu)先連接機(jī)制存在于全局網(wǎng)絡(luò),然而Li 等通過(guò)對(duì)真實(shí)復(fù)雜網(wǎng)絡(luò)的研究,發(fā)現(xiàn)優(yōu)先連接機(jī)制僅存在于局部網(wǎng)絡(luò),因此在BA 模型的基礎(chǔ)上提出一種簡(jiǎn)單局域世界網(wǎng)絡(luò)模型(LC 模型)[14].該模型首先隨機(jī)選取m個(gè)節(jié)點(diǎn)作為新增節(jié)點(diǎn)的局域世界,新增節(jié)點(diǎn)會(huì)優(yōu)先連接所對(duì)應(yīng)的局域世界中度值較大的節(jié)點(diǎn),而不是選擇全局網(wǎng)絡(luò)中度值較大的節(jié)點(diǎn)進(jìn)行連接.

在BA 模型中,新增節(jié)點(diǎn)擁有全局信息;在LC 模型中,新增節(jié)點(diǎn)僅擁有局部信息.在真實(shí)復(fù)雜網(wǎng)絡(luò)中,總是存在少數(shù)節(jié)點(diǎn)擁有全局信息,大部分節(jié)點(diǎn)僅擁有局部信息.基于此,Qin 等對(duì)LC 模型進(jìn)行了改進(jìn),建立了一種新的局域世界網(wǎng)絡(luò)模型[15].該模型引入了全局節(jié)點(diǎn)數(shù)與總結(jié)點(diǎn)數(shù)的比值作為新增節(jié)點(diǎn)屬于全局節(jié)點(diǎn)的概率p.當(dāng)p=0 時(shí),該模型對(duì)應(yīng)于LC 模型;當(dāng)p=1時(shí),對(duì)應(yīng)于BA 模型.

2.4 權(quán)重網(wǎng)絡(luò)模型

上述網(wǎng)絡(luò)模型均將網(wǎng)絡(luò)視為無(wú)權(quán)網(wǎng)絡(luò),忽略了節(jié)點(diǎn)之間的相互作用程度或節(jié)點(diǎn)和邊的物理量等信息.而真實(shí)網(wǎng)絡(luò)往往為節(jié)點(diǎn)或邊具有權(quán)重的有權(quán)網(wǎng)絡(luò),相比于無(wú)權(quán)網(wǎng)絡(luò),有權(quán)網(wǎng)絡(luò)更能反映真實(shí)情況.

Yook 提出了一種基于BA 模型的簡(jiǎn)單加權(quán)網(wǎng)絡(luò)模型[16],通過(guò)賦予邊權(quán)重來(lái)描述節(jié)點(diǎn)之間的相互作用強(qiáng)度與連接邊之間的異質(zhì)性.

Barrat 等提出了具有較強(qiáng)代表性的BBV 模型[17].該模型綜合考慮了拓?fù)浣Y(jié)構(gòu)和權(quán)重在網(wǎng)絡(luò)動(dòng)態(tài)演化過(guò)程中的影響,隨著網(wǎng)絡(luò)規(guī)模的增大,其度分布、邊權(quán)分布和節(jié)點(diǎn)權(quán)分布都具有無(wú)標(biāo)度特性.

周健等把局域世界特征引入到BBV 模型中,提出了一種基于局域世界演化的BBV 模型[18].該模型的構(gòu)建考慮了局域世界內(nèi)新節(jié)點(diǎn)和新連接的產(chǎn)生、局域世界內(nèi)舊連接的消亡、局域世界外新連接的產(chǎn)生、權(quán)值優(yōu)先連接這4 個(gè)方面.

周鵬堯等在BBV 模型的基礎(chǔ)上,提出一種廣義的加權(quán)網(wǎng)絡(luò)演化(FBBV)模型[19].該模型與BBV 模型的不同之處在于,當(dāng)網(wǎng)絡(luò)中加入新節(jié)點(diǎn)時(shí),網(wǎng)絡(luò)中所有邊權(quán)都會(huì)發(fā)生變化,變化程度取決于各邊所處的實(shí)際位置.

3 復(fù)雜網(wǎng)絡(luò)研究現(xiàn)狀

3.1 社團(tuán)結(jié)構(gòu)研究

在現(xiàn)實(shí)生活中人們可能因各種因素處于不同的團(tuán)體中,成員之間聯(lián)系頻繁,而團(tuán)體之間僅偶爾有往來(lái).在復(fù)雜網(wǎng)絡(luò)中同樣有著類似的社團(tuán)現(xiàn)象,社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征.

關(guān)于社團(tuán)結(jié)構(gòu)的定義,根據(jù)連接密度可理解為社團(tuán)是對(duì)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的分組,組內(nèi)節(jié)點(diǎn)之間聯(lián)系緊密,組間節(jié)點(diǎn)聯(lián)系稀疏;根據(jù)連通性可將社團(tuán)看作一個(gè)派系,即由兩個(gè)以上的節(jié)點(diǎn)組成的全連通子圖,其中任意兩個(gè)節(jié)點(diǎn)之間都存在連接邊.

復(fù)雜網(wǎng)絡(luò)中的社團(tuán)根據(jù)不同的標(biāo)準(zhǔn)可分為不同的類型.根據(jù)社團(tuán)內(nèi)部節(jié)點(diǎn)聯(lián)系的緊密程度,可分為強(qiáng)社團(tuán)和弱社團(tuán);根據(jù)社團(tuán)之間是否有重疊節(jié)點(diǎn),可分為重疊社團(tuán)與非重疊社團(tuán).

如何對(duì)隱藏在復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)進(jìn)行檢測(cè)與劃分,是復(fù)雜網(wǎng)絡(luò)研究中的一個(gè)重要內(nèi)容.關(guān)于社團(tuán)結(jié)構(gòu)的檢測(cè)算法,汪小帆等首先介紹了計(jì)算機(jī)科學(xué)中的譜平分法和Kernighan-Lin 算法、社會(huì)學(xué)中具有代表性的分裂算法和凝聚算法[20].

復(fù)雜網(wǎng)絡(luò)中多數(shù)節(jié)點(diǎn)的“多屬性”特征使重疊社團(tuán)的檢測(cè)算法具有更高的實(shí)用性.為準(zhǔn)確檢測(cè)出權(quán)重網(wǎng)絡(luò)中的重疊社團(tuán),賈鄭磊等提出了一種基于Jaccard系數(shù)的BGLL 模塊密度優(yōu)化算法,相比于傳統(tǒng)BGLL算法,該算法能充分利用局部、全局信息,將有權(quán)節(jié)點(diǎn)與社團(tuán)相似度相結(jié)合,具有更高準(zhǔn)確率[21].李歡等從不同角度將重疊社團(tuán)檢測(cè)算法分為基于派系過(guò)濾的算法、基于局部拓展的算法、基于邊劃分的算法、基于動(dòng)力學(xué)的算法和基于模糊檢測(cè)的算法[22].

針對(duì)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)中非重疊社團(tuán)的檢測(cè),張鵬改進(jìn)了密度峰值聚類算法,通過(guò)自定義加權(quán)集合密度算法尋找聚類中心,然后計(jì)算節(jié)點(diǎn)之間的相似性,最終完成社團(tuán)劃分[23].

3.2 抗毀性研究

網(wǎng)絡(luò)的抗毀性可理解為當(dāng)網(wǎng)絡(luò)受到攻擊或出現(xiàn)故障時(shí)所表現(xiàn)出的恢復(fù)性或適應(yīng)性,或在部分節(jié)點(diǎn)或邊失效的情況下仍能繼續(xù)提供服務(wù)的能力.如果一個(gè)網(wǎng)絡(luò)在受到攻擊而被移除少量節(jié)點(diǎn)后,剩余節(jié)點(diǎn)之間仍然是連通的,那么該網(wǎng)絡(luò)對(duì)這種攻擊具有較強(qiáng)抗毀性.

Albert 等最早開(kāi)始研究復(fù)雜網(wǎng)絡(luò)在節(jié)點(diǎn)失效情況下的抗毀性[24].他們用隨機(jī)攻擊與選擇性攻擊兩種不同策略分別對(duì)隨機(jī)網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行攻擊.隨機(jī)攻擊指的是隨機(jī)移除網(wǎng)絡(luò)中的節(jié)點(diǎn),選擇性攻擊即按照節(jié)點(diǎn)度從大到小的順序移除節(jié)點(diǎn).結(jié)果表明:無(wú)標(biāo)度網(wǎng)絡(luò)在隨機(jī)攻擊下表現(xiàn)出較強(qiáng)的抗毀性,在選擇性攻擊下卻非常脆弱,若移除有大量連接的關(guān)鍵節(jié)點(diǎn),網(wǎng)絡(luò)將立刻崩潰.

與最初基于圖論的研究方法不同,目前復(fù)雜網(wǎng)絡(luò)抗毀性的研究方法已發(fā)展為基于統(tǒng)計(jì)物理的方法,其方向包括抗毀性指標(biāo)測(cè)度和抗毀性策略優(yōu)化.

在抗毀性指標(biāo)測(cè)度方面,孫成雨等對(duì)二進(jìn)制粒子群算法的概率映射函數(shù)和位置更新式進(jìn)行改進(jìn),并結(jié)合適應(yīng)度函數(shù)求解算法,設(shè)計(jì)出點(diǎn)韌性度算法,該算法能夠快速獲取網(wǎng)絡(luò)點(diǎn)韌性度以衡量其抗毀性性能,還可用于求解邊韌性度[25].

有關(guān)研究顯示,根據(jù)網(wǎng)絡(luò)實(shí)際情況選擇合適的、包含多種信息的抗毀性指標(biāo),對(duì)抗毀性策略的優(yōu)化有重要的意義[26,27].此外,張煜等從拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)容量和路由策略等3 個(gè)方面介紹了抗毀性優(yōu)化策略的研究進(jìn)展[28],并指出除了拓?fù)浣Y(jié)構(gòu),網(wǎng)絡(luò)的防御與故障修復(fù)策略都將成為重要研究方向.

3.3 節(jié)點(diǎn)影響力研究

小世界效應(yīng)與無(wú)標(biāo)度特性使得復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)分布呈現(xiàn)不均勻的現(xiàn)象,少數(shù)節(jié)點(diǎn)具有大量連接,處于重要地位,例如在國(guó)際貿(mào)易中對(duì)整個(gè)貿(mào)易體系有重要影響的一些國(guó)家,相比于大多數(shù)普通節(jié)點(diǎn),這些少數(shù)節(jié)點(diǎn)對(duì)于整體網(wǎng)絡(luò)有著更大的影響.因此準(zhǔn)確識(shí)別復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn),對(duì)于優(yōu)化復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)與功能具有重要意義.

節(jié)點(diǎn)影響力研究包括節(jié)點(diǎn)重要性排序和影響力最大化,李夢(mèng)甜對(duì)二者進(jìn)行了深入研究,提出了一種中心性方法對(duì)節(jié)點(diǎn)傳播力進(jìn)行評(píng)估與排序,該方法將本節(jié)點(diǎn)聚類系數(shù)與相鄰節(jié)點(diǎn)度值結(jié)合,具有良好的分辨率與排序準(zhǔn)確性,運(yùn)用該方法找出的節(jié)點(diǎn)集合能夠影響更多的節(jié)點(diǎn)[29].

考慮到節(jié)點(diǎn)影響力指標(biāo)受節(jié)點(diǎn)屬性、網(wǎng)絡(luò)結(jié)構(gòu)等因素影響,張應(yīng)青等將節(jié)點(diǎn)影響力測(cè)度方法分為基于節(jié)點(diǎn)多屬性的多指標(biāo)測(cè)度方法、基于節(jié)點(diǎn)局部信息和基于網(wǎng)絡(luò)全局信息的單屬性指標(biāo)測(cè)度,并介紹了貪心算法、啟發(fā)式算法和滲流方法3 種尋找影響力節(jié)點(diǎn)集合的方法[30].

上述重要節(jié)點(diǎn)的識(shí)別方法僅局限于尋找在靜態(tài)網(wǎng)絡(luò)中具有深刻拓?fù)涮卣鞯墓?jié)點(diǎn),而真實(shí)復(fù)雜網(wǎng)絡(luò)的規(guī)模與結(jié)構(gòu)時(shí)刻都在變化.基于此,任卓明討論了節(jié)點(diǎn)影響力算法在增長(zhǎng)網(wǎng)絡(luò)、實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)與結(jié)構(gòu)突變或微擾的動(dòng)態(tài)網(wǎng)絡(luò)中遇到的問(wèn)題,對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)影響力研究有重要的意義[31].

3.4 信息傳播研究

如今網(wǎng)絡(luò)已成為信息的主要傳播渠道,這使得人們的社交網(wǎng)絡(luò)從線下接觸式拓展至線上非接觸式.對(duì)信息在社交網(wǎng)絡(luò)上傳播的動(dòng)力學(xué)機(jī)理進(jìn)行研究,是有效實(shí)施風(fēng)險(xiǎn)管控的基礎(chǔ).建立合適的信息傳播模型能準(zhǔn)確反映網(wǎng)絡(luò)個(gè)體之間信息傳播情況隨時(shí)間產(chǎn)生的變化.

典型的信息傳播模型主要參照流行病傳播模型,包括SI 模型、SIS 模型、SIR 模型、SEIR 模型、SIRS模型等.李丹丹等從經(jīng)典謠言傳播模型到社會(huì)網(wǎng)絡(luò)上的謠言傳播模型、從微觀機(jī)制和宏觀機(jī)制,分別評(píng)述了謠言傳播模型的發(fā)展歷程[32].錢亞飛分析了元胞自動(dòng)機(jī)模型、多數(shù)決定模型、Ising 模型、有界信任模型、Sznajd 模型這5 種輿情演化模型,將其分為離散與連續(xù)兩類觀點(diǎn)模型,指出網(wǎng)絡(luò)輿情研究應(yīng)當(dāng)注重真實(shí)數(shù)據(jù)集的獲取與多學(xué)科的有機(jī)結(jié)合[33].

謠言在實(shí)際社交網(wǎng)絡(luò)中的傳播率是非一致性的,每個(gè)用戶對(duì)謠言的抵抗力不同,用戶之間的親密程度也會(huì)影響謠言的傳播.翟倩倩等建立了一種S2IR 網(wǎng)絡(luò)謠言傳播模型,該模型充分考慮謠言傳播的差異性與謠言免疫策略,更加符合實(shí)際網(wǎng)絡(luò)中的謠言傳播,不足之處是未能進(jìn)一步對(duì)謠言未知節(jié)點(diǎn)進(jìn)行細(xì)分[34].

3.5 同步控制研究

無(wú)論是在日常生活中還是在專業(yè)領(lǐng)域內(nèi),同步都是一種常見(jiàn)的現(xiàn)象,例如魚群中每條魚的同時(shí)擺動(dòng)、超導(dǎo)體中電子的一致前進(jìn)等.由于同步既會(huì)產(chǎn)生有益結(jié)果也會(huì)產(chǎn)生有害結(jié)果,因此有必要對(duì)復(fù)雜網(wǎng)絡(luò)中的同步進(jìn)行控制.復(fù)雜網(wǎng)絡(luò)中的同步控制就是指通過(guò)對(duì)網(wǎng)絡(luò)施加外力對(duì)其進(jìn)行控制,使內(nèi)部多個(gè)節(jié)點(diǎn)動(dòng)力系統(tǒng)達(dá)到相同狀態(tài)并保持穩(wěn)定.如何實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的同步控制,從而維持有益同步規(guī)避有害同步,已成為當(dāng)前研究的熱點(diǎn)問(wèn)題.

信息在網(wǎng)絡(luò)中的傳播速度會(huì)受到各種因素的影響與限制,這就導(dǎo)致在控制器接受與發(fā)送節(jié)點(diǎn)狀態(tài)信息的過(guò)程中出現(xiàn)滯后現(xiàn)象[35].針對(duì)復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)本身可能存在的滯后現(xiàn)象,王亞楠分別從馬爾可夫切換轉(zhuǎn)移率部分已知和完全已知兩種情況出發(fā)研究復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng)的同步控制問(wèn)題[36].

由于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量眾多,對(duì)所有節(jié)點(diǎn)進(jìn)行控制顯然是不切實(shí)際的,因此牽制控制策略的研究受到廣泛關(guān)注,即僅對(duì)一部分節(jié)點(diǎn)進(jìn)行控制進(jìn)而使全局網(wǎng)絡(luò)保持同步.王瑞峰等引入事件激發(fā)函數(shù)實(shí)現(xiàn)牽制節(jié)點(diǎn)集的實(shí)時(shí)更新,依據(jù)合適的節(jié)點(diǎn)集選取規(guī)則,有效提高了同步效率與資源使用率[37].曹進(jìn)德等從控制條件、節(jié)點(diǎn)選取策略、影響因素、算法、應(yīng)用等方面概述了復(fù)雜網(wǎng)絡(luò)牽制同步的研究進(jìn)展[38],在目前大多數(shù)牽制控制策略依賴全局信息的背景下,如何利用局部信息實(shí)現(xiàn)分布式的牽制控制值得深入研究.

3.6 隨機(jī)行走研究

隨機(jī)行走是復(fù)雜網(wǎng)絡(luò)領(lǐng)域研究的諸多動(dòng)力學(xué)行為之一,并且與信息傳播、同步等其它動(dòng)力學(xué)行為存在緊密聯(lián)系.復(fù)雜網(wǎng)絡(luò)上的隨機(jī)行走是指隨機(jī)行走粒子以復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)為載體,從初始節(jié)點(diǎn)出發(fā),在每個(gè)時(shí)間步以一定概率選擇當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行傳輸最終到達(dá)目的節(jié)點(diǎn)的過(guò)程.

景興利等運(yùn)用圖譜理論,給出一般網(wǎng)絡(luò)上隨機(jī)行走平均到達(dá)時(shí)間的精確解,對(duì)加權(quán)網(wǎng)絡(luò)的平均首到達(dá)時(shí)間和平均陷阱時(shí)間進(jìn)行分析,發(fā)現(xiàn)二者與網(wǎng)絡(luò)規(guī)模、陷阱點(diǎn)度值、權(quán)重系數(shù)、平均度有密切關(guān)系[39].

4 結(jié)論與展望

本文從復(fù)雜網(wǎng)絡(luò)的基本概念、網(wǎng)絡(luò)模型、研究現(xiàn)狀3 個(gè)層面簡(jiǎn)要介紹了近幾年復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究成果和進(jìn)展.從中可以看到:大多數(shù)復(fù)雜網(wǎng)絡(luò)模型是在BA 模型的基礎(chǔ)上,通過(guò)新的機(jī)制演化而來(lái),BA 模型將繼續(xù)為復(fù)雜網(wǎng)絡(luò)模型研究提供重要的參考價(jià)值;當(dāng)前復(fù)雜網(wǎng)絡(luò)的研究更側(cè)重于結(jié)構(gòu)特性和網(wǎng)絡(luò)動(dòng)力學(xué)兩個(gè)領(lǐng)域,并且兩個(gè)領(lǐng)域間的研究相互影響,如何描述并分析網(wǎng)絡(luò)結(jié)構(gòu)特性與動(dòng)力學(xué)行為之間的關(guān)系,將是眾多學(xué)者面臨的難題.

隨著科技發(fā)展與眾多復(fù)雜巨系統(tǒng)的出現(xiàn),復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和動(dòng)力學(xué)行為趨向復(fù)雜化.人們僅依靠數(shù)字、表格等傳統(tǒng)形式已無(wú)法有效對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行全局性的規(guī)劃與管理,需要運(yùn)用可視化技術(shù)全面、直觀、清晰、實(shí)時(shí)地描述復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)行為,以便對(duì)其進(jìn)行分析、管理與評(píng)估.對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行可視化處理,既可以幫助人們從視覺(jué)層面上理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu),也便于學(xué)者研究復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化對(duì)其動(dòng)力學(xué)行為的影響.因此,復(fù)雜網(wǎng)絡(luò)可視化將是未來(lái)復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)之一,具體有以下幾個(gè)方向:

(1)可視化算法

可視化算法按照適用規(guī)模,可分為布點(diǎn)算法和可視化壓縮算法[40];按照布局方式,可分為基于節(jié)點(diǎn)-鏈接的可視化方法、基于鄰接矩陣的可視化方法和基于圖嵌入的可視化方法[41].隨著大數(shù)據(jù)的興起與節(jié)點(diǎn)關(guān)系的復(fù)雜化,可視化算法在性能與可觀性等方面遇到了巨大的挑戰(zhàn).對(duì)此,一是可以對(duì)現(xiàn)有算法進(jìn)行改進(jìn),提高計(jì)算效率,以減少計(jì)算資源的占用;二是可以引入“可視化分層”的概念,將運(yùn)算壓力與可視化結(jié)果隨著用戶的交互操作分配到不同的層面上.

(2)網(wǎng)絡(luò)拓?fù)淇梢暬?/p>

網(wǎng)絡(luò)拓?fù)淇梢暬且环N將點(diǎn)和線構(gòu)成圖形、圖像來(lái)對(duì)網(wǎng)絡(luò)中的拓?fù)湫畔⑦M(jìn)行描述與分析的技術(shù)[42].在大數(shù)據(jù)處理與云計(jì)算等技術(shù)的推動(dòng)下,能夠合理運(yùn)用有限資源,高效地管理大量關(guān)系復(fù)雜的節(jié)點(diǎn),并簡(jiǎn)潔、直觀地展示其運(yùn)行狀態(tài)等信息,具有重要的意義.因此,如何實(shí)現(xiàn)拓?fù)涮匦?、布局算法和可視化方式三者的結(jié)合,是當(dāng)前面臨的難點(diǎn).

(3)動(dòng)態(tài)網(wǎng)絡(luò)可視化

復(fù)雜網(wǎng)絡(luò)所具有“無(wú)標(biāo)度”特性使其處在一個(gè)數(shù)據(jù)不斷更新的狀態(tài),且新數(shù)據(jù)會(huì)對(duì)原始可視化效果帶來(lái)不可控、不可估計(jì)的影響,為其可視化帶來(lái)了巨大的挑戰(zhàn)[43].目前的可視化算法與工具大多用于靜態(tài)網(wǎng)絡(luò)的可視化,無(wú)法準(zhǔn)確描述持續(xù)演變的真實(shí)動(dòng)態(tài)網(wǎng)絡(luò),怎樣有效實(shí)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)可視化也是一個(gè)值得關(guān)注的問(wèn)題.

時(shí)至今日,復(fù)雜網(wǎng)絡(luò)的應(yīng)用已遠(yuǎn)遠(yuǎn)超出物理學(xué)和數(shù)學(xué)的范疇,其分析與應(yīng)用也為諸多學(xué)科提出了新的具有挑戰(zhàn)性的難題.把復(fù)雜網(wǎng)絡(luò)理論與實(shí)際問(wèn)題聯(lián)系起來(lái),增強(qiáng)其實(shí)用性,進(jìn)而應(yīng)用到實(shí)際復(fù)雜系統(tǒng)中,將是復(fù)雜網(wǎng)絡(luò)理論研究未來(lái)的發(fā)展趨勢(shì).