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

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

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

1 引言

復雜網絡的結構和功能在科學網絡的許多分支中引起了極大的關注，它影響著網絡的拓撲和信息的傳播。網絡是信息傳播的媒介，有時，少量的節點或邊就能使整個網絡發生巨大變化。這種信息級聯的現象在很多情況下都存在，如電網的級聯故障、通過社交網絡傳播的消息和謠言，以及微博消息影響最大化等。如何找到關鍵節點和邊是一項重要而有意義的研究。

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

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

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

以上2種方法僅僅考慮到傳播過程中的一種特性。而在實際信息傳播過程中，影響信息傳播的因素往往不只1個。因此，本文嘗試綜合考慮影響信息傳播的因素，即傳播者、受傳者的作用，傳播渠道以及傳播環境這3方面因素對邊的重要性進行度量。現有的4個經典的度量邊重要性的方法為Jaccard系數、Bridgeness、介數中心性和可達性指數[15]。通過與它們進行比較，驗證了本文方法在網絡連通性和擴散動態過程中識別重要邊這2方面均優于其他常用方法。

2 相關工作

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

2.1 基本概念

定義1(重疊節點) 許多真實的網絡中具有重疊的社團，其中，一些屬于多個社團的節點則被稱為重疊節點。

定義2(橋節點) 橋節點連接多個組或社團，一旦去掉這些橋節點之間的連接，一些真實的網絡就會被分成2個社團。

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

2.2 網絡連通性中的邊重要性

大多數邊重要性排序方法僅考慮了單一的網絡拓撲，且都是基于網絡連通性去尋找重要邊，下面是這些方法具體的定義。

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

(1)

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

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

(2)

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

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

(3)

其中，|V|是網絡中節點的個數，Ge(u,v)是從原始網絡中移除1條邊e(u,v)得到的子網。而R(s;Ge(u,v))是子網Ge(u,v)中從1個節點s可達的節點數量。

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

(4)

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

2.3 信息傳播中的邊重要性

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

(5)

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

(6)

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

可以看出，基于網絡連通性的邊介數中心性、橋中心性、可達性指數以及Jaccard系數這4種指標分別從網絡的最短路徑、派系、最大連通片以及節點的鄰居這4種角度出發，考慮到網絡的拓撲結構，刻畫了邊的重要性。基于信息傳播的邊重要性度量方法中k-path 中心性以每條邊所經過的路徑數的多少刻畫其重要性。另一個方法擴散重要性僅考慮了從節點x向y方向傳播或從節點y向x方向傳播的2個方向。以上2種方法都只考慮到傳播過程中的一種特性。而在實際信息傳播過程中，影響信息傳播的因素往往不只1個。因此，下節將綜合考慮影響網絡中信息傳播的3個因素對邊的重要性進行度量。

3 ISM方法

3.1 模型描述

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

(1)傳播者和受傳者。

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

(2)傳播渠道。

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

(3)傳播環境。

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

Figure 1 Structure of non-overlapping community圖1 非重疊社團結構

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

Figure 2 Structure of overlapping community圖2 重疊社團結構

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

為了更加詳細地描述重疊部分對邊重要性的影響，看圖3所示結構，其中，假設1，2為圖2所示的2個社團中的節點。3，4，5，6則對應于圖2中的那些重疊節點。可以發現，重疊節點是比較多的，那么這2個社團之間的邊即e(1,2)則特別容易被1-3-2這類路徑所取代。這就證明了之前的猜想，與重疊節點相連的邊是不重要的。所以，本文考慮傳播環境中重疊社區的影響去衡量邊的重要性是比較合理的。

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

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

3.2 形式化定義

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

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

(7)

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

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

(1)提取最大社團。

將網絡表示為G(V,E)，其中V表示網絡中n個節點的集合，E表示m條邊的集合。基于深度和廣度遍歷，提取所有的最大社團，初始過程如下所示：

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

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

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

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

⑤將“Ms”(s=1,2,…)最大社團作為輸出，并在給定網絡的鄰接矩陣中用標簽“DV=1”修改節點的度。

⑥如果一些節點的度不為零轉到步驟②;否則轉到步驟⑦。

⑦如果每個節點的度為零，停止循環，最終得到所有的最大社團。

(2) 擴展最大的社團。

以下規則用來擴展最大社團。首先檢測社團結構，找到屬于多個具有“DV”標簽的最大社團中的重疊節點。然后，找到連接2個以上的不屬于任何1個最大社團的橋節點，和一些不屬于任何1個最大社團的、度較低的孤立節點。

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

(3) 計算重疊節點在同一社團中出現的次數。

根據上述步驟所得結果，統計出節點i與節點j同時出現在1個最大社團中的次數，即occur_time(e)。

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

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

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

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

Step4根據形式化定義中的具體步驟找到重疊社團;

Step5計算與重疊節點相連的邊在重疊社團中出現的次數occur_time(e);

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

Step7將所有邊的分數從大到小進行排序;

Step8結束。

4 實驗與結果

本節將在9個真實網絡的數據集上驗證ISM的有效性。

4.1 度量標準

一般地，將易感指數S和最大連通片σ作為評估排序重要邊性能的標準。

在網絡連通性度量中，常用易感指數S[19]來評價方法的性能。定義易感指數S如下所示：

(8)

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

(9)

其中，mr表示移除的邊的條數，m表示整個網絡的邊數。

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

4.2 數據集

本文將在9個有著不同信息傳播的無權無向網絡數據集上進行實驗。除了TRN-Yeast-1[21]和TRN-Yeast-2[20]，其余數據均可從芝加哥網絡數據集[22]上下載。

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

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

Table 1 Basic information of the nine networks 表1 9個網絡的基本統計信息

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

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

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

4.4 實驗和結果

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

Figure 4 Spearman correlation coefficients between the ranking scores and the relative differences of σ圖4 邊排序分數和σ的相對差異的Spearman相關系數

Figure 5 Susceptibility index S over different values of p圖5 不同p值對應的易感指數S

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

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

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

5 結束語

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