徐 曼，魯富榮，馬國(guó)帥，錢宇華

(1.山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院,山西 太原 030006; 2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)),山西 太原 030006; 3.山西大學(xué)計(jì)算機(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ò)是信息傳播的媒介，有時(shí)，少量的節(jié)點(diǎn)或邊就能使整個(gè)網(wǎng)絡(luò)發(fā)生巨大變化。這種信息級(jí)聯(lián)的現(xiàn)象在很多情況下都存在，如電網(wǎng)的級(jí)聯(lián)故障、通過(guò)社交網(wǎng)絡(luò)傳播的消息和謠言，以及微博消息影響最大化等。如何找到關(guān)鍵節(jié)點(diǎn)和邊是一項(xiàng)重要而有意義的研究。

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

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

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

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

2 相關(guān)工作

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

2.1 基本概念

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

2.3 信息傳播中的邊重要性

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

(5)

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

(6)

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

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

3 ISM方法

3.1 模型描述

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

(1)傳播者和受傳者。

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

(2)傳播渠道。

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

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

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

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

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

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

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

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

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

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

3.2 形式化定義

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

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

(7)

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

occur_time(e)的計(jì)算過(guò)程主要包括以下3個(gè)步驟：

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

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

①初始化。計(jì)算每個(gè)節(jié)點(diǎn)的度，并移除度為1的孤立節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step8結(jié)束。

4 實(shí)驗(yàn)與結(jié)果

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

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

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

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

(8)

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

(9)

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

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

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

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

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

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

4.3 信息傳播因素對(duì)邊重要性的影響

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

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

4.4 實(shí)驗(yàn)和結(jié)果

圖4表示邊排序分?jǐn)?shù)與最大連通片大小σ相對(duì)差異的Spearman相關(guān)系數(shù)。Spearman相關(guān)系數(shù)的大小反映了變量間相關(guān)程度。網(wǎng)絡(luò)中移除的邊越重要，則對(duì)網(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ù)的值來(lái)看，Reachability指標(biāo)的邊排序分?jǐn)?shù)與最大連通片大小σ相對(duì)差異的相關(guān)性值最??；接下來(lái)，Jaccard和Bridgeness的相關(guān)性居中，而B(niǎo)etweeness和ISM的相關(guān)性的值基本上都接近1，相關(guān)程度都比較大?？傮w上來(lái)看，ISM中有5個(gè)值都高于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ù)和σ的相對(duì)差異的Spearman相關(guān)系數(shù)

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

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

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

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

5 結(jié)束語(yǔ)

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