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

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

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

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

1 引 言

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

既有研究已提出了許多網(wǎng)絡(luò)聚類探測算法, 其中Newman等[9,10]提出的模塊度函數(shù)Q是最為常用的一種探測指標(biāo), 用以評價聚類劃分[2]的好壞.給定一個劃分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ò)中的同步局域化理論提出了一種新的動態(tài)聚類檢測方法(opinion changing rate model, OCR).他們將改進的Kuramoto同步模型應(yīng)用到網(wǎng)絡(luò)的每個節(jié)點中, 利用社團內(nèi)部連接緊密而同步速度快的特征, 利用權(quán)重技術(shù)使得網(wǎng)絡(luò)聚類之間的邊權(quán)逐漸降低, 直到網(wǎng)絡(luò)聚類劃分獲得最大的模塊度Q值.復(fù)雜網(wǎng)絡(luò)中另一個廣泛存在的現(xiàn)象是同步[18?24].在連通網(wǎng)絡(luò)中, 每個節(jié)點通過網(wǎng)絡(luò)連接, 在動力系統(tǒng)的演化下, 與網(wǎng)絡(luò)其他節(jié)點進行耦合.在足夠強的耦合作用下, 節(jié)點的狀態(tài)會隨著時間的延長達到同步(狀態(tài)一致).在許多加權(quán)網(wǎng)絡(luò)中, 可以調(diào)整網(wǎng)絡(luò)的結(jié)構(gòu)和權(quán)重, 以提升節(jié)點狀態(tài)獲得達到同步的能力.事實上, 已有研究結(jié)果表明, 在許多社會和生物網(wǎng)絡(luò)研究中, 同步行為會在調(diào)節(jié)系統(tǒng)和組織功能中發(fā)揮重要作用.

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

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

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

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

2 相關(guān)工作

基于現(xiàn)實數(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]提出了一種通過拉普拉斯矩陣的非對角線元素 lij來增強同步能力的加權(quán)方案, 其加權(quán)后的元素定義如下:

其中, α 為調(diào)控參數(shù), Bij是節(jié)點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)實網(wǎng)絡(luò)的特征, 他們假設(shè)了一個合適的梯度場, 并定義權(quán)重

如下:

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

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

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

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

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

3.1 基本定義

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

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

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

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

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

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

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

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

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

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

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

1)通信鄰域圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 參數(shù)α取不同值時BA模型中節(jié)點強度s和節(jié)點度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)方案, 它可以試圖通過改善信息流以增強同步能力.然而, 并不是所有的應(yīng)用都需要提高同步能力,有些反而需要降低, 比如降低網(wǎng)絡(luò)的同步性有助于辨別網(wǎng)絡(luò)中的聚類結(jié)構(gòu)[17].本節(jié)將分析加權(quán)機制對網(wǎng)絡(luò)同步能力的作用, 并進一步分析其對聚類探測及其效率的影響, 從而有效驗證加權(quán)機制的高效性.除了同步和聚類分析, 本文加權(quán)機制還可以有效應(yīng)用于網(wǎng)絡(luò)流行病傳播關(guān)鍵路徑識別、免疫策略分析、演化博弈分析、路由策略設(shè)計、交通擁塞預(yù)防等多個方面.

4.1 同步性分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 應(yīng)用加權(quán)機制后網(wǎng)絡(luò)的動態(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), 這個比率的區(qū)間應(yīng)該為[0, 2].

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

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

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

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

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

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

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

對所有j, 有

對所有i, 有

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

5 實 驗

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

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)機制應(yīng)用其中.無標(biāo)度網(wǎng)絡(luò)的節(jié)點度分布服從冪律特性, 即該模型有兩個參數(shù), 其中節(jié)點初始邊數(shù) k0控制平均度, 即 〈 k〉≈2k0.另外, 參數(shù) β 調(diào)整控制網(wǎng)絡(luò)度分布的異質(zhì)性, 當(dāng) β 增加時, 網(wǎng)絡(luò)的異質(zhì)性會減少到特定程度.

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

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

圖5 (a) Watts-Strogatz網(wǎng) 絡(luò) 中 λ N/λ2 與( α , 〈 k〉 )的 對 應(yīng) 關(guān) 系(N = 500, P = 0.1); (b) Watts-Strogatz網(wǎng) 絡(luò) 中λN/λ2與( α , P)的對應(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)實世界網(wǎng)絡(luò)

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

表1 在現(xiàn)實世界網(wǎng)絡(luò)中使用8種不同加權(quán)策略的實驗結(jié)果對比, 其中RW代表隨機游走方法, 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 聚類探測

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

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

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

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

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

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

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

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

圖7 在LFR網(wǎng)絡(luò)中運用加權(quán)機制(逆加權(quán)機制), 當(dāng)取不同的 α 值時, 利用(a) SA算法和(b) DA算法后NMI的計算值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ī)模的影響, 驗證結(jié)果如圖8所示, 圖中數(shù)據(jù)點為50次實驗結(jié)果的平均值.考慮兩種不同聚類規(guī)模條件下的LFR基準(zhǔn)網(wǎng)絡(luò), 其中, 每個聚類的節(jié)點數(shù)量在10—50之間為小聚類網(wǎng)絡(luò), 在20—100之間為大聚類網(wǎng)絡(luò).為了增強這兩種LFR基準(zhǔn)網(wǎng)絡(luò)的可比性, 規(guī)定它們的區(qū)別僅限于聚類的規(guī)模大小, 其他方面的性質(zhì)則完全相同.圖8驗證了在逆加權(quán)網(wǎng)絡(luò)中, SA和DA算法的準(zhǔn)確性都得到提升.此外, 通過比較不同規(guī)模LFR網(wǎng)絡(luò)的聚類結(jié)果可以看出, 大聚類網(wǎng)絡(luò)中兩種算法的精確度更低, 這可能是因為小聚類網(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)機制的有效性.

圖8 在LFR網(wǎng)絡(luò)中運用加權(quán)機制(逆加權(quán)機制), 當(dāng)α=4( α =?4 )并考慮聚類規(guī)模時, 利用(a) SA算法和(b) DA算法后NMI的計算值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)實世界網(wǎng)絡(luò)

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

表2 在不同現(xiàn)實網(wǎng)絡(luò)使用加權(quá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.

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

表3 在現(xiàn)實世界網(wǎng)絡(luò)中使用不同加權(quán)策略的實驗結(jié)果對比, 這里網(wǎng)絡(luò)聚類算法利用CNM算法, 其中RW代表隨機游走方法, 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)實挑戰(zhàn)[57,58].同時, 作為一個開放性問題, 提高網(wǎng)絡(luò)同步性能或聚類探測的算法效率往往非常困難.為此, 本文提出一個新型雙模式加權(quán)機制, 通過加權(quán)改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來提高同步性能或聚類探測的算法效率.該加權(quán)機制包括兩種模式: 一是通過提高橋點的權(quán)重以增強同步能力的原始模式: 二是通過減少橋點的權(quán)重以提高聚類探測效率的逆模式.這種加權(quán)機制僅受一個參數(shù) α 的影響, 因此非常便于實施.通過在人工基準(zhǔn)網(wǎng)絡(luò)和現(xiàn)實世界網(wǎng)絡(luò)上的實驗分析, 檢驗了模型的有效性和高效性.特別地, 通過比較發(fā)現(xiàn),本文提出的加權(quán)策略在效率上優(yōu)于以往發(fā)表的提升網(wǎng)絡(luò)計算效率的加權(quán)方法.

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

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