基于信息傳播影響因素的邊重要性度量方法*

徐 曼，魯富榮，馬國帥，錢宇華

(1.山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院,山西 太原 030006; 2.計算智能與中文信息處理教育部重點實驗室(山西大學(xué)),山西 太原 030006; 3.山西大學(xué)計算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006)

1 引言

復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能在科學(xué)網(wǎng)絡(luò)的許多分支中引起了極大的關(guān)注，它影響著網(wǎng)絡(luò)的拓?fù)浜托畔⒌膫鞑?。網(wǎng)絡(luò)是信息傳播的媒介，有時，少量的節(jié)點或邊就能使整個網(wǎng)絡(luò)發(fā)生巨大變化。這種信息級聯(lián)的現(xiàn)象在很多情況下都存在，如電網(wǎng)的級聯(lián)故障、通過社交網(wǎng)絡(luò)傳播的消息和謠言，以及微博消息影響最大化等。如何找到關(guān)鍵節(jié)點和邊是一項重要而有意義的研究。

復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點能夠在很大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)與功能。近年來，網(wǎng)絡(luò)中節(jié)點重要性的度量方法有很多，半局部中心性[1]、k-殼分解法[2]等都是基于節(jié)點近鄰的方法；離心中心性[3]、接近中心性[4]、Katz中心性[5]等都是基于路徑的方法；節(jié)點刪除的生成樹法[6]以及節(jié)點收縮法[7]則是基于節(jié)點移除和收縮的方法。相比之下，邊的重要性的研究雖然尚未成體系，但邊在信息擴(kuò)散過程中也起著重要作用。在能量受限的大規(guī)模工業(yè)無線傳感器網(wǎng)絡(luò)中，睡眠調(diào)度是在滿足網(wǎng)絡(luò)連通性和可靠性的前提下，節(jié)約無線節(jié)點剩余能量的方法之一。在復(fù)雜網(wǎng)絡(luò)中，有時禁止一個節(jié)點的所有通信是不切實際的，因此有必要截斷一些重要的通信鏈路。重要邊分析將有助于從全局角度引導(dǎo)或控制信息的傳播。

邊的重要性研究主要集中在從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中去尋找關(guān)鍵邊。從其研究意義來看，大多數(shù)是從維持網(wǎng)絡(luò)連通性的角度出發(fā)的。Ouyang等人[8]通過移除邊后網(wǎng)絡(luò)連通性的變化，推導(dǎo)出了一個計算邊重要性的方程。Girvan等人[9]提出了邊介數(shù)中心性，邊介數(shù)越大說明該條邊在網(wǎng)絡(luò)中越重要。Hamers等人[10]指出Jaccard系數(shù)考慮到如果節(jié)點i和節(jié)點j有較少的共同鄰居，則邊更重要。Cheng等人[11]則在Bridgeness中假設(shè)刪除1條邊，信息就會在包含刪除邊的小社團(tuán)中傳播到其他邊。直觀地說，較小的社團(tuán)中的邊更重要。最近，Yu等人[12]考慮到派系對刻畫邊重要性的影響，提出了一種基于網(wǎng)絡(luò)中的派系和路徑的邊排序算法BCCMOD(Betweenness Centrality and Clique MODel)。

此外，少量關(guān)于邊的重要性研究則是從信息傳播角度出發(fā)的。de Meo等人[13]在對K-path邊中心性的描述中指出,如果將多個消息合并在1個社交網(wǎng)絡(luò)中生成和傳播，那么如果1條邊被頻繁地用來傳播信息，它就被看作是重要的。Liu等人[14]將局部傳播的異質(zhì)性考慮在內(nèi)找出網(wǎng)絡(luò)中的冗余邊。

以上2種方法僅僅考慮到傳播過程中的一種特性。而在實際信息傳播過程中，影響信息傳播的因素往往不只1個。因此，本文嘗試綜合考慮影響信息傳播的因素，即傳播者、受傳者的作用，傳播渠道以及傳播環(huán)境這3方面因素對邊的重要性進(jìn)行度量?，F(xiàn)有的4個經(jīng)典的度量邊重要性的方法為Jaccard系數(shù)、Bridgeness、介數(shù)中心性和可達(dá)性指數(shù)[15]。通過與它們進(jìn)行比較，驗證了本文方法在網(wǎng)絡(luò)連通性和擴(kuò)散動態(tài)過程中識別重要邊這2方面均優(yōu)于其他常用方法。

2 相關(guān)工作

在本節(jié)中，首先給出用到的幾類節(jié)點定義，然后總結(jié)回顧已有邊中心性度量的相關(guān)工作。

2.1 基本概念

定義1(重疊節(jié)點) 許多真實的網(wǎng)絡(luò)中具有重疊的社團(tuán)，其中，一些屬于多個社團(tuán)的節(jié)點則被稱為重疊節(jié)點。

定義2(橋節(jié)點) 橋節(jié)點連接多個組或社團(tuán)，一旦去掉這些橋節(jié)點之間的連接，一些真實的網(wǎng)絡(luò)就會被分成2個社團(tuán)。

定義3(孤立節(jié)點) 除了檢測出來的社團(tuán)、重疊節(jié)點和橋節(jié)點外，一些度較低的節(jié)點不屬于任何一個社團(tuán)，這些節(jié)點在本文中稱為孤立節(jié)點。

2.2 網(wǎng)絡(luò)連通性中的邊重要性

大多數(shù)邊重要性排序方法僅考慮了單一的網(wǎng)絡(luò)拓?fù)洌叶际腔诰W(wǎng)絡(luò)連通性去尋找重要邊，下面是這些方法具體的定義。

定義4(邊介數(shù)中心性) 邊介數(shù)中心性[9]是通過計算每條邊e(u,v)的2個端點u和v之間的最短路徑來表示。其值越大表明邊e(u,v)越重要。介數(shù)中心性定義如下：

(1)

其中,σst為節(jié)點s到節(jié)點t的最短路徑數(shù)，而σst(e)則表示從s到t通過邊e的最短路徑數(shù)。值得注意的是，它計算的是每對節(jié)點之間的最短路徑，因此時間復(fù)雜度非常高。此外，它的問題在于對于有些邊，甚至關(guān)鍵邊的值可能相對較低。

定義5(橋中心性) 2個派系之間的邊稱為橋，其中，1個大小為k的派系是有著k個節(jié)點的全連接子圖。橋中心性[11]被定義為：

(2)

其中,x和y是1條邊e的2個端點。1個節(jié)點x或1條邊e的派系大小被定義為包含這個節(jié)點或這條邊的最大派系的大小。該指標(biāo)僅適用于密集網(wǎng)絡(luò)，網(wǎng)絡(luò)中類似或相關(guān)的節(jié)點易于連接并形成局部派系，如社交網(wǎng)絡(luò)和文檔網(wǎng)絡(luò)。此外，尋找每個節(jié)點和每條邊的最大派系也很費時。

定義6(可達(dá)性指數(shù)) 邊e(u,v)的可達(dá)性[15]指數(shù)被定義為：

(3)

其中，|V|是網(wǎng)絡(luò)中節(jié)點的個數(shù)，Ge(u,v)是從原始網(wǎng)絡(luò)中移除1條邊e(u,v)得到的子網(wǎng)。而R(s;Ge(u,v))是子網(wǎng)Ge(u,v)中從1個節(jié)點s可達(dá)的節(jié)點數(shù)量。

定義7(Jaccard系數(shù)) 邊e(u,v)的Jaccard系數(shù)[10]被定義為：

(4)

其中，u和v是1條邊e(u,v)相連的2個節(jié)點,而Γu是節(jié)點u的鄰居集合。

2.3 信息傳播中的邊重要性

定義8(k-path 中心性[13]) 該指標(biāo)不同于邊介數(shù)中心性，k-path中心性對信息的傳遞進(jìn)行隨機(jī)游走過程模擬，信息的傳遞至多k步，表示形式如下所示：

(5)

定義9(擴(kuò)散重要性[14]) 該指標(biāo)將局部傳播的異質(zhì)性考慮在內(nèi)，也就是從邊的2個方向出發(fā)，分別計算除去2個端點的公共鄰居后的端點鄰居節(jié)點個數(shù)總和，定義如下：

(6)

其中，nx→y是從節(jié)點x向y方向傳播的時候，可以將信息擴(kuò)散到除去x和y的公共鄰居節(jié)點之外的y的鄰居節(jié)點數(shù)量。

可以看出，基于網(wǎng)絡(luò)連通性的邊介數(shù)中心性、橋中心性、可達(dá)性指數(shù)以及Jaccard系數(shù)這4種指標(biāo)分別從網(wǎng)絡(luò)的最短路徑、派系、最大連通片以及節(jié)點的鄰居這4種角度出發(fā)，考慮到網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，刻畫了邊的重要性?；谛畔鞑サ倪呏匾远攘糠椒ㄖ衚-path 中心性以每條邊所經(jīng)過的路徑數(shù)的多少刻畫其重要性。另一個方法擴(kuò)散重要性僅考慮了從節(jié)點x向y方向傳播或從節(jié)點y向x方向傳播的2個方向。以上2種方法都只考慮到傳播過程中的一種特性。而在實際信息傳播過程中，影響信息傳播的因素往往不只1個。因此，下節(jié)將綜合考慮影響網(wǎng)絡(luò)中信息傳播的3個因素對邊的重要性進(jìn)行度量。

3 ISM方法

3.1 模型描述

影響信息傳播活動涉及4個因素：信源、信宿、信道和信息。由此對信息傳播效果產(chǎn)生影響的因素主要有4個方面，即傳播者、受傳者、傳播渠道和傳播環(huán)境[16]。

(1)傳播者和受傳者。

信息傳播過程中的主體包括2部分：傳播者和受傳者。在郵件網(wǎng)絡(luò)中，假定最簡單的“發(fā)送或接收1封郵件”是1條消息。1個人既可以接收消息，也可以向通訊錄中出現(xiàn)的其他聯(lián)系人發(fā)送消息。當(dāng)傳播者發(fā)送重要郵件時，從信息擴(kuò)散先后順序來看，他會根據(jù)聯(lián)系人的重要程度，選擇想要告訴的聯(lián)系人(即受傳者)并進(jìn)行轉(zhuǎn)發(fā)。其中，傳播者和受傳者用節(jié)點表示，他們之間的信息傳遞關(guān)系用節(jié)點間的連邊表示。從信息傳播的角度來看，與邊相連的2個節(jié)點越重要，邊就越重要[12]?？梢园l(fā)現(xiàn)，在信息傳播的過程中1條邊的重要性取決于其2個端點的重要程度。本文采用節(jié)點中心性指標(biāo)，即節(jié)點度k去刻畫傳播者和受傳者的重要程度。無向網(wǎng)絡(luò)中節(jié)點i的度ki定義為與其直接相連的邊的數(shù)目。

(2)傳播渠道。

傳播渠道是信息傳播的媒介，傳播的路徑越多，傳播的效果越好。而且，具有不同強(qiáng)度的邊在維持網(wǎng)絡(luò)連接、信息過濾、信息傳播等方面發(fā)揮著不同的作用[17]。在郵件網(wǎng)絡(luò)中，如果1條邊(即表示2個聯(lián)系人是否有郵件傳送的過程)被頻繁地用來傳播多個郵件信息，則這條邊連接的2個節(jié)點的緊密程度越大，即連接強(qiáng)度較大。同時，這條邊所承載的信息量就比較多，對信息傳播的影響也就比較大。本文則通過計算邊的介數(shù)中心性去描述信息傳播過程中的傳播渠道。

(3)傳播環(huán)境。

在信息傳遞過程中，真實的傳播方向不單單與其傳播者、受傳者和傳播渠道有關(guān)，而且還與他們所處的環(huán)境有關(guān)。傳播環(huán)境包括群體規(guī)范、人際關(guān)系等。而在社交網(wǎng)絡(luò)中，傳播環(huán)境即節(jié)點和邊所處的社團(tuán)結(jié)構(gòu)。網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)如圖1所示，每個社團(tuán)內(nèi)部的節(jié)點之間的連接相對較為緊密，各個社團(tuán)之間的連接相對來說比較稀疏。在圖1中，社團(tuán)劃分較為明顯，此時，處于社團(tuán)之間的邊則比較重要。

Figure 1 Structure of non-overlapping community圖1 非重疊社團(tuán)結(jié)構(gòu)

但現(xiàn)實生活中，大多數(shù)網(wǎng)絡(luò)社團(tuán)劃分并不像上述情況那樣有較為明顯的社團(tuán)邊界。而是如圖2所示，劃分的社團(tuán)之間出現(xiàn)了較多的重疊部分，有不少的重疊節(jié)點和邊。為了使應(yīng)用場景更接近真實場景，本文在傳播者、受傳者和傳播渠道這3個因素的基礎(chǔ)上，還考慮了傳播環(huán)境(即重疊社團(tuán)[18])對邊的重要性的影響。

Figure 2 Structure of overlapping community圖2 重疊社團(tuán)結(jié)構(gòu)

在信息傳播的過程中，2個聯(lián)系人之間的共同聯(lián)系人越多，那么這2個聯(lián)系人之間的聯(lián)系越容易被其他聯(lián)系所替代，即這2個聯(lián)系人之間的邊越不重要。從圖2中可以看出，這個網(wǎng)絡(luò)結(jié)構(gòu)中存在2個社團(tuán)，分別為實線和虛線連接的2部分。這2個社團(tuán)之間有著較多的重疊節(jié)點(如32，9，3，20，14等)。

為了更加詳細(xì)地描述重疊部分對邊重要性的影響，看圖3所示結(jié)構(gòu)，其中，假設(shè)1，2為圖2所示的2個社團(tuán)中的節(jié)點。3，4，5，6則對應(yīng)于圖2中的那些重疊節(jié)點?？梢园l(fā)現(xiàn)，重疊節(jié)點是比較多的，那么這2個社團(tuán)之間的邊即e(1,2)則特別容易被1-3-2這類路徑所取代。這就證明了之前的猜想，與重疊節(jié)點相連的邊是不重要的。所以，本文考慮傳播環(huán)境中重疊社區(qū)的影響去衡量邊的重要性是比較合理的。

Figure 3 Influence of overlapping nodes on the edges圖3 重疊節(jié)點對邊的影響

在接下來的小節(jié)中，將討論ISM方法如何考慮到以上描述的幾種因素來刻畫邊的重要性。

3.2 形式化定義

綜上所述，考慮到信息傳播的3個影響因素，下面來討論具體的方法。其形式化定義如定義10所示。

定義10(ISM(Information Spreading Model)方法) 對一個圖G=(V,E)的每條邊e，ISM的計算如下:

(7)

其中，ki和kj是1條邊e的2個端點的度，Betweeness(e)是通過這條邊的最短路徑的數(shù)目占所有最短路徑的比例，occur_time(e)則是與重疊節(jié)點i和j相連的邊e在重疊社團(tuán)中出現(xiàn)的次數(shù)，如果與重疊節(jié)點不相連，則此值為1。

occur_time(e)的計算過程主要包括以下3個步驟：

(1)提取最大社團(tuán)。

將網(wǎng)絡(luò)表示為G(V,E)，其中V表示網(wǎng)絡(luò)中n個節(jié)點的集合，E表示m條邊的集合?；谏疃群蛷V度遍歷，提取所有的最大社團(tuán)，初始過程如下所示：

①初始化。計算每個節(jié)點的度，并移除度為1的孤立節(jié)點。

②然后選擇1個度最大的節(jié)點[V0]，并找到它的相鄰節(jié)點。

③將[V0]作為初始節(jié)點,搜索所有標(biāo)簽“DV=1”的鄰居節(jié)點[N1],然后搜索所有[N1]的鄰居節(jié)點[N2]和有著標(biāo)簽“DV=1”的節(jié)點[V0]；搜索所有[N2]的鄰居節(jié)點[N3]和有著標(biāo)簽“DV=1”節(jié)點[V0]，直到搜索到[V0]所有鄰居節(jié)點并回到初始節(jié)點[V0]。

④上一步之后會得到1個環(huán){V0,V1,V2,…,Vj,V0}，如果節(jié)點{N1,N2,…,Nj}為頂點[V0]的鄰居節(jié)點，令頂點[N1]為起始節(jié)點，搜索其鄰居節(jié)點{N3,N4,…,Nj}并讓[N2]為起始節(jié)點，搜索其鄰居節(jié)點{N4,N5,…,Nj}直到頂點[Nj-2]是點[Nj]的鄰居節(jié)點。

⑤將“Ms”(s=1,2,…)最大社團(tuán)作為輸出，并在給定網(wǎng)絡(luò)的鄰接矩陣中用標(biāo)簽“DV=1”修改節(jié)點的度。

⑥如果一些節(jié)點的度不為零轉(zhuǎn)到步驟②;否則轉(zhuǎn)到步驟⑦。

⑦如果每個節(jié)點的度為零，停止循環(huán)，最終得到所有的最大社團(tuán)。

(2) 擴(kuò)展最大的社團(tuán)。

以下規(guī)則用來擴(kuò)展最大社團(tuán)。首先檢測社團(tuán)結(jié)構(gòu)，找到屬于多個具有“DV”標(biāo)簽的最大社團(tuán)中的重疊節(jié)點。然后，找到連接2個以上的不屬于任何1個最大社團(tuán)的橋節(jié)點，和一些不屬于任何1個最大社團(tuán)的、度較低的孤立節(jié)點。

其次，NM是2個最大社團(tuán)中節(jié)點的總數(shù)，N0是2個最大社團(tuán)中公共節(jié)點的總數(shù)。在無權(quán)網(wǎng)絡(luò)中，當(dāng)NM/2≤N0時，這2個最大社團(tuán)可以合并成1個更大的子圖。否則，這2個最大社團(tuán)就不能合并成更大的子圖。最后，孤立節(jié)點不屬于任何最大社團(tuán)。如果1個孤立節(jié)點只連接1個非重疊頂點,這種孤立節(jié)點可與它連接的非重疊節(jié)點分為同一社團(tuán)。

(3) 計算重疊節(jié)點在同一社團(tuán)中出現(xiàn)的次數(shù)。

根據(jù)上述步驟所得結(jié)果，統(tǒng)計出節(jié)點i與節(jié)點j同時出現(xiàn)在1個最大社團(tuán)中的次數(shù)，即occur_time(e)。

根據(jù)式(7)，給出本文的ISM方法流程如下：

Step1初始化每條邊的得分為0;

Step2根據(jù)模型描述中的(1)計算與每條邊相連的節(jié)點的度的乘積;

Step3根據(jù)式(1)計算所有邊的邊介數(shù)中心性;

Step4根據(jù)形式化定義中的具體步驟找到重疊社團(tuán);

Step5計算與重疊節(jié)點相連的邊在重疊社團(tuán)中出現(xiàn)的次數(shù)occur_time(e);

Step6按照式(10)計算所有邊的得分;

Step7將所有邊的分?jǐn)?shù)從大到小進(jìn)行排序;

Step8結(jié)束。

4 實驗與結(jié)果

本節(jié)將在9個真實網(wǎng)絡(luò)的數(shù)據(jù)集上驗證ISM的有效性。

4.1 度量標(biāo)準(zhǔn)

一般地，將易感指數(shù)S和最大連通片σ作為評估排序重要邊性能的標(biāo)準(zhǔn)。

在網(wǎng)絡(luò)連通性度量中，常用易感指數(shù)S[19]來評價方法的性能。定義易感指數(shù)S如下所示：

(8)

其中，n為整個網(wǎng)絡(luò)的大小，ns表示大小為s的連通片的數(shù)目，而Smax是最大連通片的大小。至于細(xì)節(jié)部分，先根據(jù)排序算法的分?jǐn)?shù)降序排邊，然后從網(wǎng)絡(luò)中一條一條地按照分?jǐn)?shù)降序移除邊，并計算易感指數(shù)S。在這個過程中，定義移除邊的比例參數(shù)p為：

(9)

其中，mr表示移除的邊的條數(shù)，m表示整個網(wǎng)絡(luò)的邊數(shù)。

除了易感指數(shù)S，另一個常用于評估方法性能的指標(biāo)是最大連通片的大小σ[20]。具體是根據(jù)分?jǐn)?shù)降序排邊，然后按照從高到低的排序分?jǐn)?shù)，一條一條地移除邊，同時計算移除邊后的最大連通片的大小σ。

4.2 數(shù)據(jù)集

本文將在9個有著不同信息傳播的無權(quán)無向網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實驗。除了TRN-Yeast-1[21]和TRN-Yeast-2[20]，其余數(shù)據(jù)均可從芝加哥網(wǎng)絡(luò)數(shù)據(jù)集[22]上下載。

(1)Football網(wǎng)絡(luò)是2000年秋季美國甲級聯(lián)賽各學(xué)院之間的美式足球比賽網(wǎng)絡(luò)。(2)Grasslands和Seagrass是來自水生和陸地系統(tǒng)的小規(guī)模食物網(wǎng)絡(luò)。(3)TRN-Yeast-1和TRN-Yeast-2是酵母的2個轉(zhuǎn)錄網(wǎng)絡(luò)。(4)Euroroad是國際性的電子道路網(wǎng)，主要位于歐洲。網(wǎng)絡(luò)是無向的，節(jié)點表示城市，2個節(jié)點之間的邊表示它們由1條e路連接。(5)Power是1個包含美國西部各州電網(wǎng)信息的網(wǎng)絡(luò)。(6)Netscience是1個由Newman在2006年收集的網(wǎng)絡(luò)，其中網(wǎng)絡(luò)的節(jié)點表示科學(xué)家，連邊表示科學(xué)家之間的合作關(guān)系。(7)Router是1個包含相互連接的自治系統(tǒng)的網(wǎng)絡(luò)。

網(wǎng)絡(luò)的基本統(tǒng)計信息如表1所示。為保證網(wǎng)絡(luò)的多樣性，每個網(wǎng)絡(luò)在節(jié)點數(shù)目N和邊的數(shù)量|E|、平均度〈k〉、最大度kmax、平均聚類系數(shù)H和度異質(zhì)性C等方面都存在著差異。其中，平均度為所有節(jié)點的度的和的平均值，最大度即網(wǎng)絡(luò)中所有節(jié)點的度值的最大值，而節(jié)點的度則定義為與該節(jié)點連接的其他節(jié)點的數(shù)目；在簡單圖中，假設(shè)節(jié)點相鄰的節(jié)點有ki個，節(jié)點的聚類系數(shù)Ci定義則為ki個節(jié)點間存在的邊數(shù)與圖中總的可能邊數(shù)之比，而網(wǎng)絡(luò)的平均聚類系數(shù)H則為所有節(jié)點聚類系數(shù)Ci的平均值，體現(xiàn)了網(wǎng)絡(luò)的凝聚力；最后，度異質(zhì)性C=1-P(K),其中P(K)為網(wǎng)絡(luò)的度分布。

Table 1 Basic information of the nine networks 表1 9個網(wǎng)絡(luò)的基本統(tǒng)計信息

4.3 信息傳播因素對邊重要性的影響

影響信息傳播的因素包括：傳播者、受傳者的作用，傳播渠道和傳播環(huán)境[17]。接下來將具體分析每種因素對邊重要性的影響。以圖3所示的網(wǎng)絡(luò)數(shù)據(jù)為例，分別計算影響傳播的每種因素的值，得到的結(jié)果如表2所示。雖然圖3中最重要的邊較難識別和判斷，但直觀上來看，節(jié)點1與2之間的邊承載著較多的信息傳播，較其他邊來說更為重要。表2中傳播者、受傳者的作用(即1條邊Edged的2節(jié)點的度值乘積ki*kj)和傳播渠道(即經(jīng)過這條邊的最短路徑的個數(shù)B)都與邊的重要性成正比。而與傳播環(huán)境(即邊在重疊社區(qū)中出現(xiàn)的次數(shù)Occur_time(e))成反比，其意義為若一條邊位于多個社團(tuán)中，則這條邊的重要程度較小。以上結(jié)果均與圖3觀察到的結(jié)果相符。

Table 2 Influence of information dissemination factors on each edge表2 信息傳播因素對每條邊的影響

4.4 實驗和結(jié)果

圖4表示邊排序分?jǐn)?shù)與最大連通片大小σ相對差異的Spearman相關(guān)系數(shù)。Spearman相關(guān)系數(shù)的大小反映了變量間相關(guān)程度。網(wǎng)絡(luò)中移除的邊越重要，則對網(wǎng)絡(luò)的最大連通片造成的影響最大，即邊排序分?jǐn)?shù)與最大連通片大小的差異越大(呈現(xiàn)負(fù)相關(guān))，相關(guān)系數(shù)越大，找出的邊越重要。從圖4能夠看出，這些方法的排序分?jǐn)?shù)都與最大連通片的大小相關(guān)。邊排序分?jǐn)?shù)與從顏色深淺與其相關(guān)系數(shù)的值來看，Reachability指標(biāo)的邊排序分?jǐn)?shù)與最大連通片大小σ相對差異的相關(guān)性值最?。唤酉聛?，Jaccard和Bridgeness的相關(guān)性居中，而Betweeness和ISM的相關(guān)性的值基本上都接近1，相關(guān)程度都比較大?？傮w上來看，ISM中有5個值都高于Betweeness的，這表明與其它方法相比，ISM的排序結(jié)果與最大連通片的變化最相關(guān)，故其排序性能最好。以上比較直觀地探討了ISM方法與邊重要性的相關(guān)性。稍后將分別敘述最大連通片σ的變化和易感指數(shù)S如何能夠反映出邊重要性方法性能的好壞。

Figure 4 Spearman correlation coefficients between the ranking scores and the relative differences of σ圖4 邊排序分?jǐn)?shù)和σ的相對差異的Spearman相關(guān)系數(shù)

Figure 5 Susceptibility index S over different values of p圖5 不同p值對應(yīng)的易感指數(shù)S

9個代表性的網(wǎng)絡(luò)在不同p下的易感指數(shù)S變化情況如圖5所示。從圖5可以看出，ISM方法在統(tǒng)計上優(yōu)于其它方法。例如，ISM在Football、TRN-Yeast-1、TRN-Yeast-2、Euroroad、Netscience這5個數(shù)據(jù)集上，敏感指數(shù)S最大時，其對應(yīng)的移除邊的比例p最小。在Grasslands、Router和Power中，ISM中最大的S出現(xiàn)得較早，其對應(yīng)的p值非常接近最小值。因此，與其他方法相比，ISM的最大S值在大多數(shù)情況下出現(xiàn)得都早，表明ISM可以快速地破壞網(wǎng)絡(luò)，使網(wǎng)絡(luò)瓦解。注意到，ISM適用于除Seagrass外的網(wǎng)絡(luò)，ISM方法在對網(wǎng)絡(luò)的控制和抑制信息傳播方面具有更好的效果。以上分析結(jié)果表明，ISM綜合考慮了信息傳播過程中的3個因素來度量邊的重要性是合理的。

Figure 6 Size of giant component σ over different value of p圖6 不同p值對應(yīng)的最大連通片大小σ

網(wǎng)絡(luò)在不同p下的最大連通片的大小σ比較結(jié)果如圖6所示。該曲線下降得越快，表明方法的效果越好。從圖6可以看出，ISM方法優(yōu)于其它方法。例如，對于Football、Grasslands、Euroroad、Router、Netscience數(shù)據(jù)集，ISM的曲線下降最快，這意味著該方法可以快速地分解網(wǎng)絡(luò)。在數(shù)據(jù)集TRN-Yeast-2和Power上曲線的下降速度接近于最好的Betweeness的曲線。在圖6中，Seagrass網(wǎng)絡(luò)的最大連通片的大小總體上來看，隨著移除邊的比例增加，下降得最快。以上分析結(jié)果表明，ISM在大多數(shù)情況下可以快速分解網(wǎng)絡(luò)，可以有效地度量邊的重要性。

5 結(jié)束語

分析真實網(wǎng)絡(luò)的結(jié)構(gòu)是理解和控制網(wǎng)絡(luò)動態(tài)行為的重要思路。本文通過綜合考慮影響信息傳播的3個因素：傳播者、受傳者作用，傳播渠道和傳播環(huán)境，提出了一種基于信息傳播影響因素的邊重要性度量方法ISM(信息傳播模型)。與4個基于拓?fù)涞慕?jīng)典邊重要性度量方法相比：(1)ISM在邊滲流過程中網(wǎng)絡(luò)衰減的速度更快，也就是說，移除同樣數(shù)量的邊后，最大連通片的大小要小得多；(2)最大連通片的大小變化越明顯，則表明網(wǎng)絡(luò)能較快地被分解。實證分析表明，該方法在網(wǎng)絡(luò)連通性意義下識別重要邊優(yōu)于其他經(jīng)典方法。綜上所述，ISM在現(xiàn)實生活中有很大的意義，例如控制疾病或謠言的傳播，特別是由大量重疊社團(tuán)組成的網(wǎng)絡(luò)中，對目標(biāo)攻擊進(jìn)行防御。值得注意的是，ISM綜合考慮了較多的影響信息傳播的因素，導(dǎo)致了其時間復(fù)雜度較高，使其很難在特大規(guī)模網(wǎng)絡(luò)中應(yīng)用。此外，對更大規(guī)模網(wǎng)絡(luò)的研究也將是未來工作的一部分。