李慧嘉 黃照詞 王文璇 夏承遺

1) (北京郵電大學(xué)理學(xué)院, 北京 100876)

2) (天津理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院, 天津 300384)

高效率的網(wǎng)絡(luò)分析方法對(duì)于分析、預(yù)測(cè)和優(yōu)化現(xiàn)實(shí)群體行為具有重要的作用, 而加權(quán)機(jī)制作為網(wǎng)絡(luò)重構(gòu)化的重要方式, 在生物、工程和社會(huì)等各個(gè)領(lǐng)域都有極高的應(yīng)用價(jià)值.雖然已經(jīng)得到越來越多的關(guān)注, 但是現(xiàn)有加權(quán)方法數(shù)量還很少, 而且在不同拓?fù)漕愋秃徒Y(jié)構(gòu)特性現(xiàn)實(shí)網(wǎng)絡(luò)中的效果和性能有待繼續(xù)提高.本文提出了一種新型的雙模式加權(quán)機(jī)制, 該方法充分利用網(wǎng)絡(luò)的全局和局部的重要拓?fù)鋵傩?例如節(jié)點(diǎn)度、介數(shù)中心性和緊密中心性), 并構(gòu)建了兩種新型的運(yùn)行模式: 一種是在原始模式中通過增加橋邊的權(quán)重來提高同步能力; 另一種是在逆模式中通過弱化橋邊的權(quán)重來提高聚類檢測(cè).此外, 該加權(quán)機(jī)制僅受單一參數(shù) α 的影響, 非常便于調(diào)控.在人工基準(zhǔn)網(wǎng)絡(luò)和現(xiàn)實(shí)世界網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果均驗(yàn)證了該模型的有效性, 可以廣泛應(yīng)用于大規(guī)模的現(xiàn)實(shí)世界網(wǎng)絡(luò)中.

1 引 言

復(fù)雜網(wǎng)絡(luò)理論[1?3]是一種分析大規(guī)模復(fù)雜系統(tǒng)的有力工具, 在過去十年里已經(jīng)涌現(xiàn)出一系列相關(guān)研究成果, 例如聚類劃分技術(shù)、疾病傳播和免疫策略、交通驅(qū)動(dòng)模型、同步分析、級(jí)聯(lián)失效、異常值搜索算法等等.在這些成果中, 拓?fù)溆?jì)算和結(jié)構(gòu)分析是研究復(fù)雜網(wǎng)絡(luò)內(nèi)在特性的最有效途徑, 并使得理解網(wǎng)絡(luò)功能特征成為可能.其中, 最重要的拓?fù)涮卣髦皇蔷垲惤Y(jié)構(gòu)[3?8].它在探測(cè)聚類時(shí)將節(jié)點(diǎn)分成若干子集, 子集之間應(yīng)有清晰的邊界約束,同一組成員之間比不同組成員擁有更多的關(guān)聯(lián).聚類信息有助于理解和分析網(wǎng)絡(luò)的結(jié)構(gòu)特征和功能特性.

既有研究已提出了許多網(wǎng)絡(luò)聚類探測(cè)算法, 其中Newman等[9,10]提出的模塊度函數(shù)Q是最為常用的一種探測(cè)指標(biāo), 用以評(píng)價(jià)聚類劃分[2]的好壞.給定一個(gè)劃分Pk=(G1,G2,···,GK)=((V1,E1),(V2,E2),···,(VK,EK)), K是聚類的數(shù)目, 模塊度函數(shù)Q[9]定義如下:

其中, L是網(wǎng)絡(luò)中邊的總數(shù)目, l (Vs,Vs) 和分別代表聚類s內(nèi)部以及s與網(wǎng)絡(luò)中剩余部分之間的邊的數(shù)目.通常來說, Q值較大意味著該聚類結(jié)構(gòu)較好[11?16].此外, Boccaletti等[17]根據(jù)網(wǎng)絡(luò)中的同步局域化理論提出了一種新的動(dòng)態(tài)聚類檢測(cè)方法(opinion changing rate model, OCR).他們將改進(jìn)的Kuramoto同步模型應(yīng)用到網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)中, 利用社團(tuán)內(nèi)部連接緊密而同步速度快的特征, 利用權(quán)重技術(shù)使得網(wǎng)絡(luò)聚類之間的邊權(quán)逐漸降低, 直到網(wǎng)絡(luò)聚類劃分獲得最大的模塊度Q值.復(fù)雜網(wǎng)絡(luò)中另一個(gè)廣泛存在的現(xiàn)象是同步[18?24].在連通網(wǎng)絡(luò)中, 每個(gè)節(jié)點(diǎn)通過網(wǎng)絡(luò)連接, 在動(dòng)力系統(tǒng)的演化下, 與網(wǎng)絡(luò)其他節(jié)點(diǎn)進(jìn)行耦合.在足夠強(qiáng)的耦合作用下, 節(jié)點(diǎn)的狀態(tài)會(huì)隨著時(shí)間的延長達(dá)到同步(狀態(tài)一致).在許多加權(quán)網(wǎng)絡(luò)中, 可以調(diào)整網(wǎng)絡(luò)的結(jié)構(gòu)和權(quán)重, 以提升節(jié)點(diǎn)狀態(tài)獲得達(dá)到同步的能力.事實(shí)上, 已有研究結(jié)果表明, 在許多社會(huì)和生物網(wǎng)絡(luò)研究中, 同步行為會(huì)在調(diào)節(jié)系統(tǒng)和組織功能中發(fā)揮重要作用.

隨著數(shù)據(jù)收集技術(shù)的進(jìn)步, 諸如互聯(lián)網(wǎng)、國際貿(mào)易網(wǎng)絡(luò)等現(xiàn)實(shí)網(wǎng)絡(luò)的規(guī)模極速增長, 如何處理這些大規(guī)模網(wǎng)絡(luò)已經(jīng)成為巨大挑戰(zhàn).傳統(tǒng)的指數(shù)型算法, 甚至是多項(xiàng)式時(shí)間算法, 也已難以適用于大規(guī)模網(wǎng)絡(luò)的計(jì)算與分析.為此, 研究人員可以嘗試另辟蹊徑, 如通過改變拓?fù)湫再|(zhì)來提升網(wǎng)絡(luò)的計(jì)算效率.但是在許多實(shí)際應(yīng)用中, 網(wǎng)絡(luò)結(jié)構(gòu)通常是固定的, 一般不可能對(duì)邊進(jìn)行重連.為了克服這一困難,可以為網(wǎng)絡(luò)連邊分配合適的權(quán)重, 用來異化不同屬性的邊, 以達(dá)到提升計(jì)算性能的目的, 如弱化類間邊的權(quán)重可以提高聚類探測(cè)的效率; 而在信息傳播研究中提高重負(fù)荷邊的流通負(fù)載(通常用權(quán)重表示)可以降低網(wǎng)絡(luò)擁塞.

當(dāng)前, 加權(quán)方法已經(jīng)得到越來越多的關(guān)注[21?30],但是總體來說數(shù)量還很少, 而且對(duì)于不同拓?fù)漕愋秃徒Y(jié)構(gòu)特性的現(xiàn)實(shí)網(wǎng)絡(luò), 特定加權(quán)算法的效果和性能仍不清楚, 還有待繼續(xù)分析和驗(yàn)證.而且現(xiàn)有方法(在第2節(jié)詳細(xì)說明)通常僅利用一種節(jié)點(diǎn)中心度來定義網(wǎng)絡(luò)邊權(quán), 對(duì)于結(jié)構(gòu)相對(duì)均勻的網(wǎng)絡(luò), 效果不理想; 而且對(duì)于相對(duì)稀疏的現(xiàn)實(shí)網(wǎng)絡(luò), 調(diào)控參數(shù)的影響不明顯.另外, 目前加權(quán)之后的動(dòng)態(tài)網(wǎng)絡(luò)中的各種隱藏特征, 如聚類結(jié)構(gòu)和同步能力之間的相互關(guān)系, 仍未能得到很好的解釋和分析.

本文提出一種新型的雙模式加權(quán)機(jī)制, 用來解決上述問題.從一個(gè)簡單的無權(quán)無向網(wǎng)絡(luò)開始, 通過加權(quán)算法, 利用網(wǎng)絡(luò)的全局和多種局部信息(包括節(jié)點(diǎn)的介數(shù)、度、緊密中心度等), 將網(wǎng)絡(luò)轉(zhuǎn)化為能夠提高聚類和同步能力的加權(quán)有向網(wǎng)絡(luò).這里的加權(quán)機(jī)制包括兩種模式: 在原始模式下, 它通過增加橋邊的權(quán)重以提高網(wǎng)絡(luò)的同步能力; 而在逆模式中, 則通過弱化橋邊權(quán)重以提高聚類的檢測(cè)效率.該加權(quán)機(jī)制只受一個(gè)參數(shù) α 的控制, 可以很方便地進(jìn)行調(diào)控.對(duì)于聚類探測(cè), 通過在人工基準(zhǔn)網(wǎng)絡(luò)(包括GN基準(zhǔn)和LFR基準(zhǔn)), 以及若干現(xiàn)實(shí)網(wǎng)上進(jìn)行測(cè)試, 驗(yàn)證了本文提出的加權(quán)機(jī)制不僅有助于提高探測(cè)精度, 而且還能緩解模塊度優(yōu)化的分辨率限制問題.關(guān)于同步性, 通過在具有不同結(jié)構(gòu)特性的無標(biāo)度網(wǎng)絡(luò)和Watts-Strogatz網(wǎng)絡(luò)上進(jìn)行測(cè)試,驗(yàn)證了加權(quán)機(jī)制在提升網(wǎng)絡(luò)同步性能上的高效表現(xiàn).通過比較, 本文提出的加權(quán)機(jī)制在提高網(wǎng)絡(luò)計(jì)算能力方面要優(yōu)于其他以往發(fā)表的加權(quán)方法.

本文第1節(jié)和第2節(jié)分別梳理復(fù)雜網(wǎng)絡(luò)的基本理論及國內(nèi)外相關(guān)的工作; 第3節(jié)引入本文使用的加權(quán)機(jī)制并提出對(duì)應(yīng)的雙模式加權(quán)算法; 第4節(jié)對(duì)加權(quán)機(jī)制如何增強(qiáng)網(wǎng)絡(luò)同步性能及其對(duì)聚類結(jié)構(gòu)探測(cè)的影響進(jìn)行詳細(xì)分析; 第5節(jié)對(duì)加權(quán)機(jī)制分別運(yùn)用于人工網(wǎng)絡(luò)和大量現(xiàn)實(shí)世界網(wǎng)絡(luò)進(jìn)行試驗(yàn);第6節(jié)對(duì)全文進(jìn)行總結(jié), 并提出一些未來研究中值得深入考慮的問題.

2 相關(guān)工作

基于現(xiàn)實(shí)數(shù)據(jù)重構(gòu)復(fù)雜網(wǎng)絡(luò)是了解和控制復(fù)雜系統(tǒng)的基本方式, 而作為網(wǎng)絡(luò)重構(gòu)的重要組成部分, 網(wǎng)絡(luò)加權(quán)已經(jīng)開始得到越來越多的關(guān)注.Chavez等[21]提出了一種通過拉普拉斯矩陣的非對(duì)角線元素 lij來增強(qiáng)同步能力的加權(quán)方案, 其加權(quán)后的元素定義如下:

其中, α 為調(diào)控參數(shù), Bij是節(jié)點(diǎn)i和j之間的邊介數(shù)中心度, α ≈1 相當(dāng)于最優(yōu)的同步能力.與之相似, Wang等[22]提出網(wǎng)絡(luò)可以被視為是加權(quán)無向網(wǎng)絡(luò)和加權(quán)有向網(wǎng)絡(luò)的疊加.基于現(xiàn)實(shí)網(wǎng)絡(luò)的特征, 他們假設(shè)了一個(gè)合適的梯度場(chǎng), 并定義權(quán)重

如下:

Charvez等和Wang等提出方法具有一定程度的相似性, 但后者利用的不是介數(shù)中心度, 而是基于節(jié)點(diǎn)的度.隨著 α 值的增大, 網(wǎng)絡(luò)同步化總是會(huì)隨之提升.然而, 同時(shí)應(yīng)當(dāng)注意避免 α 值過高, 否則會(huì)導(dǎo)致網(wǎng)絡(luò)斷開和分裂.為了解決這個(gè)問題, Jalili等[23]在節(jié)點(diǎn)介數(shù)中心度方法的基礎(chǔ)上提出了一種新的加權(quán)方法, 其中權(quán)重定義如下:

其中, BjB 和 BijB 分別代表節(jié)點(diǎn)j與邊 eij之間的介數(shù)中心度.該加權(quán)機(jī)制被用來提高網(wǎng)絡(luò)的同步性能.但是上述加權(quán)算法僅僅利用一種節(jié)點(diǎn)中心度來定義網(wǎng)絡(luò)邊權(quán), 對(duì)于結(jié)構(gòu)相對(duì)均勻的網(wǎng)絡(luò), 效果不理想.而且對(duì)于相對(duì)稀疏的現(xiàn)實(shí)網(wǎng)絡(luò), 調(diào)控參數(shù)的影響不明顯.

最近, Khadivi等[31]討論了一種新型加權(quán)機(jī)制, 用以緩解網(wǎng)絡(luò)聚類中的模塊度缺陷, 即分辨率極限[32]和極端限制[33]等問題.該加權(quán)機(jī)制利用了網(wǎng)絡(luò)的局部和全局信息, 其中每條邊的權(quán)重定義如下:

其中, cij定義為共同鄰居比例, Bij是邊介數(shù)中心度.利用Clauset-Newman-Moore方法[10]進(jìn)行試驗(yàn), 驗(yàn)證了該加權(quán)機(jī)制能夠顯著地優(yōu)化社團(tuán)探測(cè)的速度與精度.但是仿真分析也表明, 當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí), 其加權(quán)效果不明顯.而且雖然該方法可以用來加強(qiáng)社團(tuán)內(nèi)部的團(tuán)內(nèi)邊, 但是卻無法明顯降低團(tuán)間邊的權(quán)重, 從而阻礙了該加權(quán)算法的進(jìn)一步應(yīng)用.另外現(xiàn)有的網(wǎng)絡(luò)加權(quán)方法還包括模擬退火算法[25]、文獻(xiàn)計(jì)量方法[26]、隨機(jī)游走算法[27]、級(jí)聯(lián)動(dòng)力學(xué)方法[28]、變分貝葉斯方法[29]和概率推斷方法[30]等.但總體來說, 當(dāng)前加權(quán)算法的數(shù)量還很少, 而且對(duì)于不同拓?fù)漕愋秃徒Y(jié)構(gòu)特性的現(xiàn)實(shí)網(wǎng)絡(luò), 特定加權(quán)算法的效果和性能仍不清楚, 還有待繼續(xù)分析和驗(yàn)證.

3 復(fù)雜網(wǎng)絡(luò)基本理論

3.1 基本定義

假設(shè) G (V,E) 是一個(gè)無向連通圖, V為節(jié)點(diǎn)集,E為邊界集.這里考慮三個(gè)最常用的衡量拓?fù)浣Y(jié)構(gòu)和信息流通的中心度指標(biāo).

節(jié)點(diǎn)度節(jié)點(diǎn)度 ki[34]表示節(jié)點(diǎn)i相連的邊的數(shù)量, 根據(jù)鄰接矩陣 A =(aij) 將其定義為

其中, aij是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鄰接矩陣值.還可以將節(jié)點(diǎn)度擴(kuò)展到加權(quán)網(wǎng)絡(luò)得到節(jié)點(diǎn)強(qiáng)度的概念.

節(jié)點(diǎn)強(qiáng)度節(jié)點(diǎn)強(qiáng)度 si[35]是節(jié)點(diǎn)i相關(guān)聯(lián)的邊的權(quán)重總和, 定義如下:

其中, wij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的邊的權(quán)重值.

介數(shù)中心度一個(gè)節(jié)點(diǎn)在信息傳播中的重要性可以通過其介數(shù)中心度[36]來計(jì)算, 定義為

其中, σij(u) 為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的通過節(jié)點(diǎn)u的最短路徑的數(shù)量, σij是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑的總數(shù)量.介數(shù)中心度的概念還可以拓展到邊.邊 eij的介數(shù)中心度 Bij表示通過該邊的最短路徑的數(shù)量, 在信息傳播研究中常用來表示流通負(fù)載.

緊密中心度(closeness)節(jié)點(diǎn)i的緊密中心度[36]定義為一個(gè)網(wǎng)絡(luò)中其他節(jié)點(diǎn)到節(jié)點(diǎn)i的平均距離的倒數(shù)

其中, Dij是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間最短路徑的長度;Ci用來測(cè)量一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的(平均)緊密程度.為了定義該中心性與最短路徑的直接(正比例)關(guān)系, 還可以將其定義為 Ci的倒數(shù):

k-鄰域圖k-鄰域圖[37,38]定義為將節(jié)點(diǎn)i和節(jié)點(diǎn)j連接起來的最短路徑上的點(diǎn)的集合, 其中i和j之間的最短距離值小于等于k.由于鄰域關(guān)系是不對(duì)稱的( i →j ), 因此根據(jù)k-鄰域圖的定義得到的可能是一個(gè)有向子圖.在特定網(wǎng)絡(luò)中, 節(jié)點(diǎn)i的k-鄰域圖被構(gòu)造為特定的相似性度量(這里指最短路徑距離)下顯示與i最相似的子圖.然而在大多數(shù)應(yīng)用中, k的值難以直接給定, 以致其應(yīng)用領(lǐng)域受到限制.

3.2 雙模式加權(quán)算法

1)通信鄰域圖

受到k-鄰域圖定義的啟發(fā), 為了增強(qiáng)網(wǎng)絡(luò)信息流, 本文提出了一個(gè)新的拓?fù)涠x——通信鄰域圖(communication neighbor graph, CNG), 并進(jìn)一步提出一種新的加權(quán)算法.通信鄰域圖的具體定義如下.

通訊鄰域圖假設(shè) G (V,E) 是一個(gè)無自循環(huán)的無向網(wǎng)絡(luò), 其中節(jié)點(diǎn)的數(shù)量 | |V||=N.對(duì)于G中的節(jié)點(diǎn)來說, ζij是節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的最短路徑(路徑為節(jié)點(diǎn)序列集合).節(jié)點(diǎn)i通過節(jié)點(diǎn)j的通信鄰域圖用 Πi→j表示, 其定義為: 給定節(jié)點(diǎn)u, 如果滿足通過節(jié)點(diǎn)i與u之間的最短路徑長度大于節(jié)點(diǎn)j與u之間的最短路徑長度, 即 l (ζiu)> l (ζju) ,那么節(jié)點(diǎn)u屬于 Πi→j.如果節(jié)點(diǎn)i和節(jié)點(diǎn)u之間存在一條以上的最短路徑, 那么就認(rèn)為 ζiu是其中任意一條.根據(jù)通信鄰域圖CNG的定義, 對(duì)于特定節(jié)點(diǎn)u, 假定節(jié)點(diǎn)i與節(jié)點(diǎn)u之間有邊相連, 如果 ζiu經(jīng)過節(jié)點(diǎn)j, 那么節(jié)點(diǎn)u就屬于 Πi→j.

注意到通信鄰域圖CNG是非對(duì)稱的, 即一般情況下 Πi→j與 Πj→i是不同的.對(duì)于任意一對(duì)相鄰的節(jié)點(diǎn)i和j來說, 節(jié)點(diǎn)j一定屬于 Πi→j.另外, 任一節(jié)點(diǎn)屬于且僅屬于節(jié)點(diǎn)i的一個(gè)通訊鄰域圖.圖1(a)給出了兩個(gè)相鄰節(jié)點(diǎn)的通信鄰域圖的例子.當(dāng)網(wǎng)絡(luò)是稠密且規(guī)模不大時(shí), 該定義是非常直觀的.

圖1 (a)節(jié)點(diǎn)4和節(jié)點(diǎn)5之間邊對(duì)應(yīng)的通訊鄰域圖; (b)網(wǎng)絡(luò)中的橋邊Fig.1.(a) Communication neighborhood graph corresponding to the edge between node 4 and node 5; (b) bridge side in the network.

2) 加權(quán)算法

如果邊權(quán)與流量成正比, 那么為了增強(qiáng)連邊上的信息流, 需要研究最有可能出現(xiàn)瓶頸的橋點(diǎn)和橋邊.因?yàn)闃螯c(diǎn)和橋邊數(shù)目較少且處于兩個(gè)類之間,它們往往無法承載端點(diǎn)需要發(fā)送的全部信息, 如圖1(b)所示.如果節(jié)點(diǎn)具有大的度、介數(shù)中心性和緊密中心性, 那么它更有可能具有高信息吞吐量,因此這些節(jié)點(diǎn)及其所連的邊更可能成為瓶頸.在本文模型中, 這種可能性被假設(shè)為與單一實(shí)數(shù)成正比, 即定義圖中每個(gè)節(jié)點(diǎn)的 γ 值.

在給定通信鄰域圖CNG的定義后, 接下來介紹一種新型的加權(quán)機(jī)制.令 γ (u)∈R 表示屬于Πi→j中節(jié)點(diǎn)u的一個(gè)特定指標(biāo),Γ(Πi→j)={γ(u1),γ(u2),···,γ(uk)} 且 是 Πi→j中 所 有 節(jié) 點(diǎn) 的 γ 值集合, 其中 u ∈Πi→j.那么, 本文的加權(quán)機(jī)制定義如下:

其中, ψ 為任意實(shí)數(shù)集中的單一實(shí)數(shù)相關(guān)的函數(shù).這是一種具有代表性的加權(quán)方法, 可以用來加強(qiáng)與網(wǎng)絡(luò)通信相關(guān)的多種計(jì)算與應(yīng)用.

本文加權(quán)算法旨在重點(diǎn)增強(qiáng)瓶頸節(jié)點(diǎn)的各種中心性值, 使其與加權(quán)權(quán)重成正比, 以便增強(qiáng)網(wǎng)絡(luò)的整體通信能力.定義 ψ 為一個(gè)集合所有元素的加和, 即如果 X ={x1,x2,···,xN} , 那么ψ(X)=定義節(jié)點(diǎn)u的加權(quán)參數(shù)為

其中, α ∈R , 且 ku, Bu和分別為網(wǎng)絡(luò)G中節(jié)點(diǎn)的度、介數(shù)中心性和緊密中心度 Cu的倒數(shù).ε 設(shè)定為0.01, 以避免 γ 值為0.設(shè)計(jì)加權(quán)參數(shù) γ 是為了反映瓶頸節(jié)點(diǎn)u的各項(xiàng)參數(shù), 包括度 ku, 介數(shù)中心性 Bu和緊密中心度 Cu, 如果各項(xiàng)參數(shù)比較大, 則γ也比較大, 節(jié)點(diǎn)u成為瓶頸節(jié)點(diǎn)的概率也會(huì)很大.那么, 節(jié)點(diǎn)j到節(jié)點(diǎn)i的權(quán)重為

其中 Πi→j表示節(jié)點(diǎn)i通過節(jié)點(diǎn)j的通信鄰域圖.(12) 式表示的加權(quán)機(jī)制的原理為當(dāng)傳輸線路i→j 比較重要時(shí), 其通信鄰域圖 Πi→j的規(guī)模也會(huì) 相 應(yīng) 比 較 大.則 當(dāng) α >0 時(shí), (12)式 的 分 子 項(xiàng)和相應(yīng)的權(quán)重 Wij也會(huì)相應(yīng)比較大,從而實(shí)現(xiàn)了加權(quán)機(jī)制增強(qiáng)重要通信邊的權(quán)重的目的.這里, 分母項(xiàng)的設(shè)置是為了實(shí)現(xiàn)標(biāo)準(zhǔn)化, 權(quán)重矩陣的對(duì)角線元素被設(shè)置具有零行和屬性, 即

在加權(quán)策略((12)式)中, 分母的標(biāo)準(zhǔn)化項(xiàng)使得入度更加均勻.另外, γ 函數(shù)((11)式)增強(qiáng)了以高 γ 值節(jié)點(diǎn)為起點(diǎn)的路徑, 并且進(jìn)一步使得網(wǎng)絡(luò)流量更加趨向于流向這類節(jié)點(diǎn).這個(gè)過程使節(jié)點(diǎn)的負(fù)載分配更加傾向于平均.總而言之, 本文提出的加權(quán)策略使負(fù)載分布更加均勻化, 同時(shí)降低了平均路徑長度.本文加權(quán)算法具體流程如算法1所示.本算法由于需要計(jì)算節(jié)點(diǎn)的介數(shù)、度、緊密度三種中心性度量, 時(shí)間復(fù)雜度分別為O(n3), O(n2)和O(n3), 因此總的時(shí)間復(fù)雜度為O(n3).

算法1網(wǎng)絡(luò)加權(quán)算法流程

輸入: 網(wǎng)絡(luò)G, 其節(jié)點(diǎn)數(shù)為n, 邊數(shù)為m; 加權(quán)參數(shù)α.

輸出: 網(wǎng)絡(luò)加權(quán)矩陣W.

1） 根據(jù)“通訊鄰域圖”的定義計(jì)算網(wǎng)絡(luò)中每條邊的通訊鄰域圖;

2） 計(jì)算 ku, Bu和 C ～u, 分別為網(wǎng)絡(luò)G中節(jié)點(diǎn)的度、介數(shù)中心性和緊密中心度 Cu的倒數(shù);

3） 根據(jù)(6)式和(11)式計(jì)算節(jié)點(diǎn)u的加權(quán)值γ(u);

4）根據(jù)(12)式更新網(wǎng)絡(luò)中邊的加權(quán)值wij.

需要說明的是, 本文提出的加權(quán)機(jī)制是使用虛擬方式改變拓?fù)浣Y(jié)構(gòu), 但是僅通過加權(quán)來達(dá)到網(wǎng)絡(luò)重連的效果是不大可能的.例如, 在環(huán)形規(guī)則網(wǎng)絡(luò)中, 所有節(jié)點(diǎn)的 γ 值是相等的, 加權(quán)機(jī)制并不能增強(qiáng)網(wǎng)絡(luò)的傳輸容量.因此, 本文的加權(quán)機(jī)制旨在通過降低瓶頸節(jié)點(diǎn)的限制, 使網(wǎng)絡(luò)層次結(jié)構(gòu)趨于平坦以提高傳輸容量.這種加權(quán)機(jī)制對(duì)具有非均勻?qū)哟谓Y(jié)構(gòu)和瓶頸節(jié)點(diǎn)的網(wǎng)絡(luò)(如無標(biāo)度網(wǎng)絡(luò))來說很有效率.反之, 均勻網(wǎng)絡(luò)或無瓶頸節(jié)點(diǎn)的網(wǎng)絡(luò)則不具備這種加權(quán)機(jī)制的優(yōu)勢(shì).此外, 本文的加權(quán)策略還有一個(gè)重要優(yōu)點(diǎn): 只受一個(gè)參數(shù)調(diào)控, 即參數(shù) α , 可以用來控制加權(quán)權(quán)重的異質(zhì)程度(即非均勻性).這里有三種典型的情況:

當(dāng) α >0(α<0) , 在通信鄰域圖中, 具有高ξ值的節(jié)點(diǎn)對(duì)信息傳輸會(huì)有更多(更少)的貢獻(xiàn).特別地, 在同質(zhì)(均勻)網(wǎng)絡(luò)中, 節(jié)點(diǎn)呈現(xiàn)出均勻的負(fù)載和度分布, 那么節(jié)點(diǎn)的 ξ 值和隨之得到的加權(quán)值也會(huì)變得均勻.在這種情況下, 改變 α 不會(huì)導(dǎo)致權(quán)重和網(wǎng)絡(luò)傳輸效率發(fā)生顯著變化.類似地, 當(dāng)網(wǎng)絡(luò)負(fù)載分布和度分布是異質(zhì)(非均勻)時(shí), 不同的 α 會(huì)導(dǎo)致權(quán)重和網(wǎng)絡(luò)傳輸效率發(fā)生顯著變化.因此, 在異質(zhì)(同質(zhì))網(wǎng)絡(luò)中, α 會(huì)有更多(更少)的影響.

當(dāng) α =0 時(shí), γ 值將退化為對(duì)所有節(jié)點(diǎn)u都有γ(u)=1.值得注意的是, 這種情況與無權(quán)網(wǎng)絡(luò)或者標(biāo)準(zhǔn)化僅僅應(yīng)用于節(jié)點(diǎn)度的情況不同.在這種情況下, 僅考慮每個(gè)通信鄰域圖的節(jié)點(diǎn)數(shù)量, 它在γ值分布的方差較小的網(wǎng)絡(luò)中將會(huì)相當(dāng)有效, 即 γ 值的同質(zhì)性.

由于受標(biāo)準(zhǔn)化因子和通信鄰域圖節(jié)點(diǎn)數(shù)目的影響, α <0 并不會(huì)產(chǎn)生負(fù)值, 但是會(huì)使得信息傳輸能力下降(即具有高 ξ 值的節(jié)點(diǎn)對(duì)信息傳輸會(huì)有更少的貢獻(xiàn)).根據(jù)本文框架, 我們提出了利用轉(zhuǎn)置權(quán)重矩陣以降低傳輸能力的逆加權(quán)方案.為了能夠更方便地轉(zhuǎn)換, 權(quán)重矩陣被定義為

其中, 參數(shù) 0 ≤ρ≤1 , 表示傳輸程度.例如, 當(dāng)ρ=1 意味著高傳輸流量, 而 ρ =0 意味著低傳輸流量.

逆模式加權(quán)機(jī)制在(12)式的加權(quán)機(jī)制中,設(shè)定參數(shù) α <0 , 定義為逆模式加權(quán)機(jī)制.根據(jù)(12)式, 在逆模式加權(quán)機(jī)制中, 即具有高 ξ 值的節(jié)點(diǎn)對(duì)信息傳輸會(huì)有更少的貢獻(xiàn), 從而會(huì)使得網(wǎng)絡(luò)流量更加趨向于避開這類節(jié)點(diǎn), 使得信息傳輸能力下降.為了能夠更方便地轉(zhuǎn)換, 權(quán)重矩陣被定義為(13)式.逆模式加權(quán)算法如算法2所示.

算法2逆模式加權(quán)算法流程

輸入: 網(wǎng)絡(luò)G, 其節(jié)點(diǎn)數(shù)為n, 邊數(shù)為m; 加權(quán)參數(shù) α <0 ; 傳輸程度參數(shù)0≤ρ≤1.

輸出: 網(wǎng)絡(luò)加權(quán)矩陣W.

1) 根據(jù)“通訊鄰域圖”的定義計(jì)算網(wǎng)絡(luò)中每條邊的通訊鄰域圖;

2) 根據(jù)(11)式計(jì)算節(jié)點(diǎn)u的加權(quán)值 γ (u) ;

為了測(cè)試參數(shù) α 的影響, 將其應(yīng)用到著名的BA網(wǎng)絡(luò)中, 分別考慮 α =2 和 α =6 兩種情況, 結(jié)果如圖2所示.可以看出, 受加權(quán)機(jī)制的影響, 節(jié)點(diǎn)強(qiáng)度和節(jié)點(diǎn)度會(huì)出現(xiàn)明顯異化.此外, 當(dāng)α=6時(shí), 節(jié)點(diǎn)強(qiáng)度和節(jié)點(diǎn)度的關(guān)系的分布相較于α=2時(shí)更加分散.這是因?yàn)?α 的值越大, 更多的邊會(huì)得到較大的權(quán)重值.該結(jié)果與前面加權(quán)機(jī)制的分析相符合.因此, 通過本文的加權(quán)策略, 權(quán)重分布、節(jié)點(diǎn)強(qiáng)度以及度的關(guān)系均依賴于參數(shù) α 的值, 該加權(quán)網(wǎng)絡(luò)比相應(yīng)的二進(jìn)制無權(quán)網(wǎng)絡(luò)提供了更多的信息.

圖2 參數(shù)α取不同值時(shí)BA模型中節(jié)點(diǎn)強(qiáng)度s和節(jié)點(diǎn)度k之間的關(guān)系(N = 5000) (a) α =2 ; (b)α=6Fig.2.Relationship between node strength s and node degree k in BA model (N = 5000) with different values of parameter α: (a) α =2 ; (b) α =6.

4 復(fù)雜網(wǎng)絡(luò)的屬性分析

許多研究[20,39,40]發(fā)現(xiàn), 網(wǎng)絡(luò)中信息傳輸?shù)碾y易程度可以解釋為同步能力, 并且它們都被網(wǎng)絡(luò)拓?fù)渚仃嚨奶卣髦邓拗?由此直接引出本文提出的加權(quán)方案, 它可以試圖通過改善信息流以增強(qiáng)同步能力.然而, 并不是所有的應(yīng)用都需要提高同步能力,有些反而需要降低, 比如降低網(wǎng)絡(luò)的同步性有助于辨別網(wǎng)絡(luò)中的聚類結(jié)構(gòu)[17].本節(jié)將分析加權(quán)機(jī)制對(duì)網(wǎng)絡(luò)同步能力的作用, 并進(jìn)一步分析其對(duì)聚類探測(cè)及其效率的影響, 從而有效驗(yàn)證加權(quán)機(jī)制的高效性.除了同步和聚類分析, 本文加權(quán)機(jī)制還可以有效應(yīng)用于網(wǎng)絡(luò)流行病傳播關(guān)鍵路徑識(shí)別、免疫策略分析、演化博弈分析、路由策略設(shè)計(jì)、交通擁塞預(yù)防等多個(gè)方面.

4.1 同步性分析

首先說明加權(quán)機(jī)制增強(qiáng)網(wǎng)絡(luò)同步性能的原因.設(shè) λ1≤λ2≤,···,≤λN為加權(quán)矩陣W的N個(gè)特征值.根據(jù)文獻(xiàn)[41], 矩陣W的特征值比 λN/λ2越小, 則意味著該網(wǎng)絡(luò)具有更大的同步能力.如上所述, 網(wǎng)絡(luò)通信的能力可以被解釋為在網(wǎng)絡(luò)中信息流動(dòng)的難易程度.更確切地說, 可以將動(dòng)態(tài)方程寫作:

通過網(wǎng)絡(luò)加權(quán), 總是可以將W的對(duì)角線元素標(biāo)準(zhǔn)化為1, 從而防止任意大或者任意小的耦合值.權(quán)重矩陣W是不對(duì)稱的, 并且一般而言非對(duì)稱矩陣的特征值非常復(fù)雜.下面的推論證明了非對(duì)稱矩陣W具有有界的實(shí)數(shù)特征值.

推論1加權(quán)機(jī)制((12)式)得到的權(quán)重矩陣的所有特征值是實(shí)數(shù), 且值介于0—2之間.

證明權(quán)重矩陣W對(duì)應(yīng)的拉普拉斯矩陣 Lw,寫作 Lw=MQ , 其中

Q是一個(gè)零行和矩陣, 具有負(fù)非對(duì)角項(xiàng), 即Qij=?ψ(Γ(Πi→j)).容易看出, W的特征值λi(i=1,···,N) 與 M1/2QM1/2的特征值相等, 即是實(shí)數(shù)且非負(fù)的, 且最小特征值 λ1=0.另一方面,Gerschgorin循環(huán)定理[42]證明了 Lw的每個(gè)特征值都在一個(gè)半徑為1的圓的內(nèi)部, 因此0=λ1≤λ2≤,···,≤λN≤2.證明完畢.

接下來引入超中心節(jié)點(diǎn)的定義.

超中心節(jié)點(diǎn)網(wǎng)絡(luò)中具有最大 γ 值的節(jié)點(diǎn)被稱為網(wǎng)絡(luò)的超中心節(jié)點(diǎn).

定理1令 G (V,E) 為一個(gè)無向網(wǎng)絡(luò), 對(duì)于每一對(duì)節(jié)點(diǎn)u和v, 選擇它們之間的最短路徑 S Puv, 并根據(jù)通信鄰域圖的定義確定通信鄰域圖運(yùn)用加權(quán)機(jī)制((12)式).如果該鄰域圖具有唯一的超中心節(jié)點(diǎn), 那么當(dāng) α →+∞ 時(shí), 通過移除超中心節(jié)點(diǎn)的輸入邊, 剩余網(wǎng)絡(luò)將會(huì)退化到一個(gè)以超中心節(jié)點(diǎn)為根節(jié)點(diǎn)的有向生成樹, 因此總有一條有向路徑可以從超中心節(jié)點(diǎn)通向其他所有節(jié)點(diǎn).

證明根據(jù)(12)式, 當(dāng) α →+∞ 時(shí), 可以得到ψ(Γ(Πi→j))≈max{Γ(Πi→j)} , 從而有現(xiàn)在, 假設(shè)節(jié)點(diǎn) u?是唯一的超中心節(jié)點(diǎn), 即網(wǎng)絡(luò)中具有最大的 γ 值的節(jié)點(diǎn).當(dāng) α →+∞ 時(shí), 如果 u?∈Πi→j并收斂于0, 權(quán)重 Wij將收斂于1.換言之, 每個(gè)節(jié)點(diǎn)?只保持一條邊連接網(wǎng)絡(luò)中具有最大 γ 值的那個(gè)節(jié)點(diǎn).由于 u?的輸入邊被刪除了, 也就是所有到u?的輸入邊的權(quán)重都等于0, 僅保留N – 1條有向邊.因此, 從節(jié)點(diǎn) u?到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)都有一條有向路徑, 且僅保留有N – 1條邊, 由此得到的網(wǎng)絡(luò)結(jié)構(gòu)是一個(gè)有向生成樹, 其中具有最大 γ 值的節(jié)點(diǎn)是根節(jié)點(diǎn).證明完畢.

推論2根據(jù)參考文獻(xiàn)[41], 定理1中得到的有向生成樹的特征值比 λN/λ2=1 , 意味著該網(wǎng)絡(luò)具有最大的同步能力.簡單來說, 由于生成樹的根擁有最大的 γ 值, 因此在所得的生成樹中, 大多數(shù)節(jié)點(diǎn)都在樹的較低層次上, 也就是說大多數(shù)節(jié)點(diǎn)與根節(jié)點(diǎn)的平均距離較短.值得一提的是, 當(dāng)α→+∞時(shí), 如果不移除根節(jié)點(diǎn)的輸入邊, 那么特征 值 比 λN/λ2=2 , 也就是說,0=λ1<λ2=λ3,···,=λN?1<λN=2.如果超中心節(jié)點(diǎn)并不唯一, 當(dāng) α →+∞ 時(shí), 網(wǎng)絡(luò)將退化為有向圖, 其中所有超中心節(jié)點(diǎn)都屬于邊權(quán)重相等的團(tuán).此外, 該團(tuán)中的任意節(jié)點(diǎn)都能與圖中的所有其他節(jié)點(diǎn)相連, 即對(duì)于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)來說, 都有一條有向路徑通向每個(gè)超中心節(jié)點(diǎn).基于上述可以發(fā)現(xiàn), 只有參與這些路徑的邊被留下來, 而其他的邊都將會(huì)消失.

4.2 聚類結(jié)構(gòu)分析

前文已經(jīng)提到, 在一些應(yīng)用中, 有時(shí)候還需要降低同步能力, 如辨別網(wǎng)絡(luò)中的聚類結(jié)構(gòu)[17].本文提出的加權(quán)策略對(duì)聚類結(jié)構(gòu)探測(cè)也有很強(qiáng)的影響,并且可以進(jìn)一步發(fā)現(xiàn)聚類結(jié)構(gòu)與同步性之間的隱藏關(guān)系.首先給出聚類結(jié)構(gòu)的弱定義:

聚類結(jié)構(gòu)的弱定義Radicchi等[43]分別從弱定義和強(qiáng)定義這兩方面給出了衡量聚類結(jié)構(gòu)的量化標(biāo)準(zhǔn), 其中弱定義被認(rèn)為是一個(gè)子圖集合能夠成為聚類結(jié)構(gòu)的最弱標(biāo)準(zhǔn), 即聚類是網(wǎng)絡(luò)的子圖集合, 子圖內(nèi)部的邊的密度高于子圖之間的邊的密度.給定一個(gè)網(wǎng)絡(luò) G =(V,E) , 其中V是節(jié)點(diǎn)集,E是邊界集, A =(aij) 為 其鄰接矩陣, 令Vs?V為一個(gè)特定子圖, Vs=VVs為網(wǎng)絡(luò)其余的節(jié)點(diǎn)集,那么在弱靈敏度條件下 Vs能夠成為一個(gè)聚類的條件是:

推論3如果 eij是一個(gè)類間邊, 那么鄰域圖Πi→j和 Πj→i很可能是兩個(gè)相鄰的聚類.此外, 在極端情況下, 如果網(wǎng)絡(luò)是二劃分且 eij是唯一的類間邊, 根據(jù)聚類結(jié)構(gòu)的弱定義, Πi→j和 Πj→i將是嚴(yán)格的網(wǎng)絡(luò)聚類.

證明:根據(jù)弱定義, 如果一個(gè)網(wǎng)絡(luò)擁有聚類結(jié)構(gòu), 由于存在高密度的類內(nèi)邊, 一個(gè)隨機(jī)游走者將會(huì)在一個(gè)聚類中停留很多的時(shí)間.這意味著一個(gè)節(jié)點(diǎn)到同一聚類內(nèi)的節(jié)點(diǎn)的路徑長度通常比到不同聚類的節(jié)點(diǎn)的路徑長度短.如圖2中 α =2 時(shí),Πi→j中的節(jié)點(diǎn)到節(jié)點(diǎn)j的路徑長度比到節(jié)點(diǎn)i的路徑長度都要長.相反, Πj→i中的節(jié)點(diǎn)到節(jié)點(diǎn)i的路徑長度比到節(jié)點(diǎn)j的路徑長度長.因此可以得出結(jié)論: Πi→j和 Πj→i很可能是兩個(gè)不同的聚類.此外, 如果 eij是唯一的類間界, 根據(jù)聚類結(jié)構(gòu)的弱定義, 這個(gè)結(jié)論是嚴(yán)格的.證明完畢.

為了闡明加權(quán)機(jī)制對(duì)聚類結(jié)構(gòu)的影響, 逐步增大 α 的值并在示例網(wǎng)絡(luò)中刪除 Wij<0.5 的 邊.如圖3所示, 當(dāng) α 值從2增加到4, 聚類結(jié)構(gòu)會(huì)顯著增強(qiáng).

圖3 應(yīng)用加權(quán)機(jī)制后網(wǎng)絡(luò)的動(dòng)態(tài)演化示例圖Fig.3.Example of dynamic evolution of network after applying weighting mechanism.

根據(jù)弱定義, 比率 R =lout/lin在解決模塊度優(yōu)化問題上發(fā)揮著十分重要的作用.為了滿足弱定義的標(biāo)準(zhǔn), 這個(gè)比率的區(qū)間應(yīng)該為[0, 2].

定理2令 lout為類間邊的數(shù)量, lin為類內(nèi)邊的數(shù)量, 那么比率 R =lout/lin可以用來有效量化網(wǎng)絡(luò)中的聚類結(jié)構(gòu).

證明對(duì)于特定的網(wǎng)絡(luò)G, 其相對(duì)的超圖G?定義為一個(gè)有向加權(quán)的C團(tuán)結(jié)構(gòu), 其中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于G的一個(gè)聚類.在 G?中, 節(jié)點(diǎn)r和節(jié)點(diǎn)s之間的邊用來加權(quán), 其中代表G中聚類r和聚類s之間的團(tuán)間邊數(shù)量,代表聚類r內(nèi)部邊的數(shù)量.G?對(duì)應(yīng)的 C ×C 拉普拉斯矩陣F={Frs} 是不對(duì)稱的, 但是可以變換為 F =?Θ , 其中?={?rs}是一個(gè)對(duì)稱的零行和矩陣, 其非對(duì)角元素為對(duì)角元素為且那么可以將F寫成:

因?yàn)镕是零行和的, 所以F的譜元素都是非負(fù)實(shí)數(shù), 其中F的最小特征值, 次小特征值

根據(jù)譜方法和信息論[42,44?46],能夠量化超圖的連通性, 從而衡量不同聚類的性質(zhì)和互相關(guān)聯(lián)的程度.應(yīng)該注意到,已經(jīng)過標(biāo)準(zhǔn)化, 所以它應(yīng)該是一維的.這里, 可以得出.特殊情況下, 如果C個(gè)聚類都具有相等規(guī)模 Nc=N/C ,那么類內(nèi)邊數(shù)量和類間邊數(shù)量對(duì)所有聚類來說都是一樣的.此時(shí), 由和可以得到由?=CI/lin, 可以得到證明完畢.

接下來將展示本文的加權(quán)策略如何化解聚類探測(cè)中的分辨率限制問題, 以使優(yōu)化方法更加有效.Fortunato和Barthelemy[32]發(fā)現(xiàn)了聚類探測(cè)的分辨率限制問題, 表明對(duì)于優(yōu)化模塊度Q((1)式)的算法, 如果的取值區(qū)間不在[0, L]內(nèi), 那么模塊度優(yōu)化算法將無法檢測(cè)到這些聚類.直觀地看, 如果引入一種加權(quán)策略, 能夠有效擴(kuò)大這個(gè)限制區(qū)間, 那么許多優(yōu)化算法就能夠在一個(gè)較大的限制范圍內(nèi)探測(cè)到準(zhǔn)確聚類.為了分析簡便, 假設(shè)權(quán)重之和邊的個(gè)數(shù)L保持相等.這里, 加權(quán)網(wǎng)絡(luò)中所有的量都以上尖號(hào)為區(qū)分, 即.首先, 回顧一個(gè)關(guān)于聚類規(guī)模邊界的定理[32].

定理3聚類規(guī)模對(duì)模塊度函數(shù)Q的影響有如下限制:

其中, R =lout/lin.如果合并聚類i和聚類j不能提高模塊度函數(shù)Q的值, 那么對(duì)于聚類i和聚類j的規(guī)模有如下約束條件[31]:

對(duì)所有j, 有

對(duì)所有i, 有

總結(jié)來說, 如果將本文的加權(quán)策略應(yīng)用于網(wǎng)絡(luò)中, 那么能夠通過優(yōu)化算法探測(cè)出更大或更小的聚類, 從而可以有效地降低分辨率限制的問題.

5 實(shí) 驗(yàn)

本節(jié)將上述加權(quán)機(jī)制運(yùn)用在人工網(wǎng)絡(luò)和大量現(xiàn)實(shí)世界網(wǎng)絡(luò)中.結(jié)果表明, 這種加權(quán)機(jī)制可以分別利用原模式和逆模式來提高網(wǎng)絡(luò)同步能力以及增強(qiáng)聚類結(jié)構(gòu)檢測(cè)能力.

5.1 同步性

在本文提出的加權(quán)策略中, 唯一的調(diào)整參數(shù)是α.通過改變 α 參數(shù), 可以控制權(quán)重值的異質(zhì)性和特征值比 λN/λ2.

1)人工基準(zhǔn)網(wǎng)絡(luò)

這里利用無標(biāo)度網(wǎng)絡(luò)[2]和Watts-Strogatz小世界網(wǎng)絡(luò)[1]作為基準(zhǔn)模型網(wǎng)絡(luò), 并將本文加權(quán)機(jī)制應(yīng)用其中.無標(biāo)度網(wǎng)絡(luò)的節(jié)點(diǎn)度分布服從冪律特性, 即該模型有兩個(gè)參數(shù), 其中節(jié)點(diǎn)初始邊數(shù) k0控制平均度, 即 〈 k〉≈2k0.另外, 參數(shù) β 調(diào)整控制網(wǎng)絡(luò)度分布的異質(zhì)性, 當(dāng) β 增加時(shí), 網(wǎng)絡(luò)的異質(zhì)性會(huì)減少到特定程度.

圖4給出了在無標(biāo)度網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果, 其中數(shù)據(jù)點(diǎn)為50次實(shí)驗(yàn)結(jié)果的平均值.圖4(a)為特征值比 λN/λ2和參數(shù)( α , 〈 k〉 )的對(duì)應(yīng)關(guān)系, 這里網(wǎng)絡(luò)的平均度用 〈 k〉 表示.設(shè) α =1 , 對(duì)于所有的平均度〈k〉 , 可以得到 λN/λ2<2 , 這比文獻(xiàn)[23]的最優(yōu)情況還要好, 而又優(yōu)于文獻(xiàn)[21, 22, 39]的研究結(jié)果.對(duì)于較大的平均度 〈 k〉 , 權(quán)重分布和度分布的同質(zhì)性增加, 這表示 γ 值將更加均勻, 而 α 的影響也會(huì)較弱.所以, 無論 α 的大小, 加權(quán)過程都將顯著提高網(wǎng)絡(luò)同步能力.對(duì)于平均度 〈 k〉 較低的網(wǎng)絡(luò), 由于網(wǎng)絡(luò)中異質(zhì)性較高, 因此較大的 α 將會(huì)得到更好的結(jié)果.接下來研究網(wǎng)絡(luò)的異質(zhì)性(非均勻性), 該性質(zhì)可以用參數(shù) β 來衡量.已有研究表明, 網(wǎng)絡(luò)度分布的異質(zhì)性是影響同步性能最重要的因素之一.無標(biāo)度網(wǎng)絡(luò)中特征值比 λN/λ2和參數(shù) α , β 的關(guān)系如圖4(b)所示.對(duì)于不同的 β , 因?yàn)闊o標(biāo)度特征導(dǎo)致節(jié)點(diǎn)度的非均勻性, 參數(shù) α 的影響作用會(huì)更加顯著.此外可以看出, 隨著 β 值增加, 網(wǎng)絡(luò)非均勻性降低,得到的加權(quán)網(wǎng)絡(luò)的同步性會(huì)逐漸變差.

圖4 (a) 無標(biāo)度網(wǎng)絡(luò)中 λ N/λ2 與( α , 〈 k〉 )的對(duì)應(yīng)關(guān)系(N = 500, β =0 ); (b)無標(biāo)度網(wǎng)絡(luò)中 λ N/λ2 與( α , β )的對(duì)應(yīng)關(guān)系(N = 500, 〈 k〉=4 )Fig.4.(a) Corresponding relationship (N = 500, β =0 ) in scale-free networks between λ N/λ2 and ( α , 〈 k〉 ); (b) Corresponding relationship (N = 500, 〈 k〉=4 ) in scale-free networks between λ N/λ2 and ( α , β ).

接下來將加權(quán)機(jī)制應(yīng)用到Watts-Strogatz網(wǎng)絡(luò)中, 相對(duì)于無標(biāo)度網(wǎng)絡(luò)來說, Watts-Strogatz網(wǎng)絡(luò)的節(jié)點(diǎn)度分布是均勻的.該網(wǎng)絡(luò)受兩個(gè)參數(shù)控制, 即平均度 〈 k〉=2k0, 和重連概率P.圖5給出了在Watts-Strogatz網(wǎng)絡(luò)中應(yīng)用本文加權(quán)算法的結(jié)果, 圖中數(shù)據(jù)點(diǎn)為50次實(shí)驗(yàn)結(jié)果的平均值.其中, 圖5(a)為特征值比 λN/λ2隨參數(shù) α 和網(wǎng)絡(luò)平均度 〈 k〉 的變化情況.和無標(biāo)度網(wǎng)絡(luò)相似, 當(dāng)平均度〈k〉 增加時(shí), 網(wǎng)絡(luò)的異構(gòu)程度隨之降低 α , 從而降低α的貢獻(xiàn)程度.可以看出, 當(dāng)平均度 〈 k〉 非常高時(shí),α對(duì)特征值比 λN/λ2幾乎沒有影響.圖5(b)為特征值比 λN/λ2隨參數(shù) α 和重連概率P的變化情況.當(dāng)P較小時(shí), 網(wǎng)絡(luò)度分布幾乎是均勻的, 但是節(jié)點(diǎn)的負(fù)載分布卻是極度非均勻的.這是由于極少數(shù)的重連邊可以被視作捷徑, 它們承擔(dān)著很高的負(fù)載,導(dǎo)致負(fù)載的分布具有高度的不均勻性.隨著重連概率P的增加, 網(wǎng)絡(luò)重連邊的數(shù)量會(huì)逐漸增加, 負(fù)載分布會(huì)因此變得越來越均勻.在這種情況下, 雖然度分布的方差會(huì)逐漸增加, 但仍不足以提升 γ 值的異質(zhì)程度.因此, 增加P會(huì)使 γ 值分布更加均勻,從而降低加權(quán)機(jī)制的貢獻(xiàn)程度.特別地, 當(dāng)P = 1時(shí), Watts-Strogatz網(wǎng)絡(luò)等同于完全隨機(jī)圖.

圖5 (a) Watts-Strogatz網(wǎng) 絡(luò) 中 λ N/λ2 與( α , 〈 k〉 )的 對(duì) 應(yīng) 關(guān) 系(N = 500, P = 0.1); (b) Watts-Strogatz網(wǎng) 絡(luò) 中λN/λ2與( α , P)的對(duì)應(yīng)關(guān)系(N = 500, 〈 k〉=4 )Fig.5.(a) Corresponding relationship (N = 500, P = 0.1) in Watts-Strogatz networks between λ N/λ2 and ( α , 〈 k〉 ); (b) corresponding relationship (N = 500, 〈 k〉=4 ) in Watts-Strogatz networks between λ N/λ2 and ( α , P).

2) 現(xiàn)實(shí)世界網(wǎng)絡(luò)

雖然現(xiàn)實(shí)世界極其復(fù)雜以致無法獲取全部信息, 但是為了充分地進(jìn)行驗(yàn)證, 我們將9個(gè)不同的加權(quán)機(jī)制應(yīng)用到大量現(xiàn)實(shí)世界網(wǎng)絡(luò)中并進(jìn)行對(duì)比,包括Chavez方法[21]、Wang方法[22]、Jalili方法[23]、Khadivi方法[31]、模擬退火(SA)算法[25]、隨機(jī)游走(RW)算法[27]、變分貝葉斯(VB)算法[29]、概率推斷(PL)方法[30]和本文方法, 結(jié)果列在表1中,其中設(shè)定 α =4.可以看出, 本文使用的加權(quán)機(jī)制的性能超過了其他所有的加權(quán)方法.值得一提的是, 對(duì)于所有的現(xiàn)實(shí)世界網(wǎng)絡(luò), 隨著 α 的增加, 特征值 λN/λ2比都將收斂于2.

表1 在現(xiàn)實(shí)世界網(wǎng)絡(luò)中使用8種不同加權(quán)策略的實(shí)驗(yàn)結(jié)果對(duì)比, 其中RW代表隨機(jī)游走方法, SA代表模擬退火方法,VB代表變分貝葉斯方法, PL代表概率推斷方法Table 1.Comparison of experimental results using eight different weighting strategies in real world networks, in which RW represents random walk method, SA stands for simulated annealing method, VB stands for variational Bayesian method, PL stands for probability inference method.

5.2 聚類探測(cè)

1)人工基準(zhǔn)網(wǎng)絡(luò)

本文采用兩個(gè)著名的人工基準(zhǔn)網(wǎng)絡(luò), 即Girvan-Newman (GN)基準(zhǔn)網(wǎng)絡(luò)和Lancichinetti-Fortunato-Radicchi (LFR)基準(zhǔn)網(wǎng)絡(luò), 用以評(píng)估加權(quán)機(jī)制對(duì)社區(qū)探測(cè)效率的影響.其中, GN基準(zhǔn)測(cè)試[9,11]已經(jīng)廣泛應(yīng)用于對(duì)不同聚類算法的效率評(píng)估.GN網(wǎng)絡(luò)共包括128個(gè)節(jié)點(diǎn), 這些節(jié)點(diǎn)被分配到4個(gè)聚類中, 每個(gè)聚類包含32個(gè)節(jié)點(diǎn), 每個(gè)聚類內(nèi)部點(diǎn)之間連邊和與類外節(jié)點(diǎn)連邊的概率分別為 pin和 pout.因此, 對(duì)于每個(gè)節(jié)點(diǎn), 它們?cè)诰垲悆?nèi)部的邊的個(gè)數(shù)和與其他類節(jié)點(diǎn)關(guān)聯(lián)的邊的期望分別為 zin=31pin和 zout=96pout, 可以看出 zin+zout=16.

更進(jìn)一步地, Lancichinetti等[47]提出了LFR基準(zhǔn)網(wǎng)絡(luò), 它可以通過調(diào)整相關(guān)參數(shù)來符合現(xiàn)實(shí)網(wǎng)絡(luò)中的無標(biāo)度特征.在該基準(zhǔn)網(wǎng)絡(luò)中, 節(jié)點(diǎn)的度分布和聚類規(guī)模遵循冪律分布.此外, 還需要設(shè)定一些其他參數(shù), 包括節(jié)點(diǎn)最大度、節(jié)點(diǎn)平均度、節(jié)點(diǎn)總數(shù)、聚類最大規(guī)模和最小規(guī)模以及最重要的混合參數(shù) μ.混合參數(shù) μ 的取值區(qū)間為[0, 1], 決定了LFR基準(zhǔn)圖的聚類模糊性程度: μ 越大, 聚類就越難被正確劃分.可以看出, GN基準(zhǔn)網(wǎng)絡(luò)是LFR基準(zhǔn)網(wǎng)絡(luò)的一個(gè)特例.由于GN基準(zhǔn)網(wǎng)絡(luò)和LFR基準(zhǔn)網(wǎng)絡(luò)的社團(tuán)都是預(yù)先給定的, 而不同劃分算法得到的結(jié)果是不同的, 因此這里利用正確率R(正確劃分的節(jié)點(diǎn)和全部節(jié)點(diǎn)的比值)衡量劃分的正確性.

首先, 將加權(quán)策略將應(yīng)用于GN基準(zhǔn)網(wǎng)絡(luò).在圖6(a)的原加權(quán)網(wǎng)絡(luò)中, α 取2和4, 在逆加權(quán)網(wǎng)絡(luò)中, α 取–2和–4, 數(shù)據(jù)點(diǎn)為50次實(shí)驗(yàn)結(jié)果的平均值.圖6(a)給出了在GN基準(zhǔn)網(wǎng)絡(luò)上應(yīng)用加權(quán)策略前后的平均正確率R的對(duì)比.可以看出, 當(dāng)α=4 和 α =2 時(shí), 加權(quán)策略的原模式都提高了平均正確率R, 而相應(yīng)的兩個(gè)逆模式 ( α =?4 和α=?2 )都會(huì)降低平均正確率R.與 α =4 的情況相比, 在 α =2 的情況下, 平均正確率R會(huì)下降約2—3倍.而且在逆模式中, 當(dāng) zout≤6.5 時(shí),α=?4的情況與 α =?2 相比, 平均正確率R會(huì)降低2倍以上.

其次, 在LFR基準(zhǔn)網(wǎng)絡(luò)上進(jìn)行分析, 其中參數(shù)設(shè)置如下: 節(jié)點(diǎn)數(shù)量為1000、平均度為20、最大節(jié)點(diǎn)度為50、冪律分布指數(shù)為2、混合參數(shù) μ 在區(qū)間[0, 0.5]內(nèi)變化.從圖6(b)可以看出, 加權(quán)策略的原模式會(huì)顯著提高平均正確率R, 而相應(yīng)的逆模式會(huì)降低平均正確率R.與 α =4 的情況相比, 在α=2的情況下, 平均正確率R會(huì)下降約4—5倍.另外, 在逆加權(quán)模式也會(huì)得到相似的結(jié)果.比較兩種基準(zhǔn)網(wǎng)絡(luò), 對(duì)于提高平均正確率R, 加權(quán)策略在LFR基準(zhǔn)網(wǎng)絡(luò)中會(huì)取得更好的效果.

圖6 (a) GN基準(zhǔn)網(wǎng)絡(luò)中使用加權(quán)機(jī)制(逆加權(quán)機(jī)制)前后平均比率R的對(duì)比; (b) LFR基準(zhǔn)網(wǎng)絡(luò)中使用加權(quán)機(jī)制(逆加權(quán)機(jī)制)前后平均比率R的對(duì)比Fig.6.(a) Comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism)in GN benchmark network; (b) comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism) in LFR benchmark network.

再次, 為了展示加權(quán)機(jī)制對(duì)聚類探測(cè)的影響,首先利用具有不同 α 值的加權(quán)機(jī)制對(duì)網(wǎng)絡(luò)賦權(quán), 然后利用一些著名的聚類算法運(yùn)行并測(cè)試其準(zhǔn)確性.這里使用在信息論中被廣泛研究的標(biāo)準(zhǔn)化互信息(normalized mutual information, NMI)來衡量聚類結(jié)果的準(zhǔn)確性[40].NMI位于區(qū)間[0, 1]內(nèi), 其值的大小表明真實(shí)聚類和模型結(jié)果之間重疊的比例.特別地, 當(dāng)NMI的值為1時(shí), 算法結(jié)果與真實(shí)聚類完全相同, 具有最高的劃分效率.真實(shí)劃分X和模型結(jié)果Y之間的標(biāo)準(zhǔn)化互信息NMI的數(shù)學(xué)定義為

其中, cX和 cY分別表示真實(shí)劃分X和模型結(jié)果Y中的聚類數(shù)量.在(21)式, Nij代表真實(shí)劃分中聚類i和實(shí)驗(yàn)結(jié)果中聚類j之間重疊的節(jié)點(diǎn)數(shù)量,Ni和 Nj分別表示矩陣N中第i行和第j列值的總和.

圖7 (a)和圖7(b)給出了利用兩種著名算法,即模擬退火法(SA)[48]和Duch-Arenas法(DA)[49],在運(yùn)用加權(quán)機(jī)制的網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果, 圖中數(shù)據(jù)點(diǎn)為50次實(shí)驗(yàn)結(jié)果的平均值.其中, SA算法被證明是效果最好的聚類算法之一, 然而其計(jì)算復(fù)雜性也較高.與SA相比, DA不僅在模塊化優(yōu)化方面具備一定可靠性, 而且計(jì)算過程也相對(duì)簡單.從圖7(a)和圖7(b)可以看到, 當(dāng) α 值從–2降低到–4,逆加權(quán)模式對(duì)應(yīng)的NMI值越來越高, 要優(yōu)于無權(quán)網(wǎng)絡(luò).相反, 在原加權(quán)模式中, 當(dāng) α 值從2增加到4,加權(quán)網(wǎng)絡(luò)的NMI相對(duì)于無權(quán)網(wǎng)絡(luò)的NMI卻越來越少.這些結(jié)果均驗(yàn)證了本文的加權(quán)策略的有效性.此外, 通過比較兩種方法發(fā)現(xiàn), 圖7(a)中α=4( α =?4 )和 α =2 ( α =?2 )兩 種 情 況 的NMI差異區(qū)間小于圖7(b).這可能是因?yàn)? 即使是在無權(quán)網(wǎng)絡(luò)中, SA都擁有更高的精確度, 難以通過加權(quán)策略提高它的表現(xiàn).但是對(duì)于DA來說, 通過提高α, 加權(quán)機(jī)制能夠大幅提高它的計(jì)算精度.

圖7 在LFR網(wǎng)絡(luò)中運(yùn)用加權(quán)機(jī)制(逆加權(quán)機(jī)制), 當(dāng)取不同的 α 值時(shí), 利用(a) SA算法和(b) DA算法后NMI的計(jì)算值Fig.7.Weighted mechanism (inverse weighted mechanism)is used in LFR network.When the α value is different, the NMI value is calculated by using (a) SA algorithm and (b) DA algorithm.

此外, 本文還考慮了聚類規(guī)模的影響, 驗(yàn)證結(jié)果如圖8所示, 圖中數(shù)據(jù)點(diǎn)為50次實(shí)驗(yàn)結(jié)果的平均值.考慮兩種不同聚類規(guī)模條件下的LFR基準(zhǔn)網(wǎng)絡(luò), 其中, 每個(gè)聚類的節(jié)點(diǎn)數(shù)量在10—50之間為小聚類網(wǎng)絡(luò), 在20—100之間為大聚類網(wǎng)絡(luò).為了增強(qiáng)這兩種LFR基準(zhǔn)網(wǎng)絡(luò)的可比性, 規(guī)定它們的區(qū)別僅限于聚類的規(guī)模大小, 其他方面的性質(zhì)則完全相同.圖8驗(yàn)證了在逆加權(quán)網(wǎng)絡(luò)中, SA和DA算法的準(zhǔn)確性都得到提升.此外, 通過比較不同規(guī)模LFR網(wǎng)絡(luò)的聚類結(jié)果可以看出, 大聚類網(wǎng)絡(luò)中兩種算法的精確度更低, 這可能是因?yàn)樾【垲惥W(wǎng)絡(luò)中具有更多的類間邊, 而類間邊更可能是被加權(quán)的.并且通過比較兩種方法, 圖8(a)顯示的小聚類和大聚類LFR網(wǎng)絡(luò)(無論是逆加權(quán)網(wǎng)絡(luò)還是加權(quán)網(wǎng)絡(luò))之間的NMI區(qū)間差距小于圖8(b), 原因與圖7相同, 完美證明了本文加權(quán)機(jī)制的有效性.

圖8 在LFR網(wǎng)絡(luò)中運(yùn)用加權(quán)機(jī)制(逆加權(quán)機(jī)制), 當(dāng)α=4( α =?4 )并考慮聚類規(guī)模時(shí), 利用(a) SA算法和(b) DA算法后NMI的計(jì)算值Fig.8.The weighted mechanism (inverse weighted mechanism) is used in LFR network.When α = 4 (α = –4) and considering the cluster size, the NMI calculated by (a) SA algorithm and (b) DA algorithm.

2) 現(xiàn)實(shí)世界網(wǎng)絡(luò)

進(jìn)一步將加權(quán)策略應(yīng)用到現(xiàn)實(shí)世界網(wǎng)絡(luò)中, 結(jié)果在表2中列出.這里使用了7種廣泛使用的網(wǎng)絡(luò), 并標(biāo)識(shí)了相應(yīng)的文獻(xiàn)出處.為了便于比較,提供了關(guān)于7種網(wǎng)絡(luò)已發(fā)表方法中的最優(yōu)模塊度Q值[56].本文計(jì)算了當(dāng) α =4 時(shí)三種代表性算法,即SA[48], DA[49]和CNM[10]的加權(quán)前后模塊度Q值, 其中“/”左右表示加權(quán)后和加權(quán)前的模塊度Q值, 結(jié)果如表2所列.這三種算法的精確度雖然并不處于最頂級(jí)的行列, 然而正如表2所列, 在應(yīng)用加權(quán)策略后, 結(jié)果非常接近已發(fā)表的最優(yōu)值, 并且計(jì)算過程更加簡便.

表2 在不同現(xiàn)實(shí)網(wǎng)絡(luò)使用加權(quán)策略得到的實(shí)驗(yàn)結(jié)果, 其中“/”左右表示加權(quán)后和加權(quán)前的模塊度Q值Table 2.Experimental results are obtained by using weighting strategy in different real networks, where /’s left or right represents the modularity Q value after or before weighting.

進(jìn)一步將9種加權(quán)策略應(yīng)用到現(xiàn)實(shí)世界網(wǎng)絡(luò)中, 包括Chavez方法[21]、Wang方法[22]、Jalili方法[23]、Khadivi方法[31]、模擬退火(SA)算法[25]、隨機(jī)游走(RW)算法[27]、變分貝葉斯(VB)算法[29]、概率推斷方法[30]和本文方法, 用以對(duì)比不同加權(quán)方法的聚類效果.聚類算法統(tǒng)一使用CNM方法[10],并計(jì)算當(dāng) α =4 時(shí)的模塊度Q值.結(jié)果列在表3中, 可以看出, 本文所使用的加權(quán)機(jī)制的性能超過了其他所有的加權(quán)方法, 從而驗(yàn)證了本文加權(quán)算法的高效性.

表3 在現(xiàn)實(shí)世界網(wǎng)絡(luò)中使用不同加權(quán)策略的實(shí)驗(yàn)結(jié)果對(duì)比, 這里網(wǎng)絡(luò)聚類算法利用CNM算法, 其中RW代表隨機(jī)游走方法, SA代表模擬退火方法, VB代表變分貝葉斯方法, PL代表概率推斷方法Table 3.Comparison of experimental results using different weighting strategies in the real world network.CNM algorithm is used as the network clustering algorithm, in which RW represents the random walk method, SA represents the simulated annealing method, VB represents the variable dB method, and PL represents the probability inference method.

6 結(jié) 論

隨著“大數(shù)據(jù)”技術(shù)的不斷涌現(xiàn)和發(fā)展, 如何處理大規(guī)模網(wǎng)絡(luò)已經(jīng)成為了巨大的現(xiàn)實(shí)挑戰(zhàn)[57,58].同時(shí), 作為一個(gè)開放性問題, 提高網(wǎng)絡(luò)同步性能或聚類探測(cè)的算法效率往往非常困難.為此, 本文提出一個(gè)新型雙模式加權(quán)機(jī)制, 通過加權(quán)改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來提高同步性能或聚類探測(cè)的算法效率.該加權(quán)機(jī)制包括兩種模式: 一是通過提高橋點(diǎn)的權(quán)重以增強(qiáng)同步能力的原始模式: 二是通過減少橋點(diǎn)的權(quán)重以提高聚類探測(cè)效率的逆模式.這種加權(quán)機(jī)制僅受一個(gè)參數(shù) α 的影響, 因此非常便于實(shí)施.通過在人工基準(zhǔn)網(wǎng)絡(luò)和現(xiàn)實(shí)世界網(wǎng)絡(luò)上的實(shí)驗(yàn)分析, 檢驗(yàn)了模型的有效性和高效性.特別地, 通過比較發(fā)現(xiàn),本文提出的加權(quán)策略在效率上優(yōu)于以往發(fā)表的提升網(wǎng)絡(luò)計(jì)算效率的加權(quán)方法.

在今后的研究工作中, 仍有一些問題值得深入探討.比如工程、信息領(lǐng)域應(yīng)用中的群體演化博弈和平均一致性問題, 可能在無向網(wǎng)絡(luò)中更容易分析和理解, 加權(quán)有向網(wǎng)絡(luò)并不一定是最佳選擇.另外,如何在擁有數(shù)百萬甚至更多節(jié)點(diǎn)的超大規(guī)模網(wǎng)絡(luò)中進(jìn)行研究分析, 也需要進(jìn)一步深入探索.

感謝吉林大學(xué)劉大有教授、中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院章祥蓀研究員、中央財(cái)經(jīng)大學(xué)劉志東教授對(duì)本文提出的建設(shè)性建議.