基于TOPSIS權(quán)重的社會網(wǎng)絡(luò)影響力最大化

郭茂林，孔 兵

(云南大學 信息學院，云南 昆明 650091)

0 引 言

隨著網(wǎng)絡(luò)與社會生產(chǎn)活動的關(guān)系日益緊密，社會網(wǎng)絡(luò)的種類、數(shù)量和規(guī)模也呈現(xiàn)出了多樣化、海量化和復雜化，共同鄰居共同郵件地址等重疊數(shù)據(jù)也越來越多。在這種背景下，如何快速找到網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，使網(wǎng)絡(luò)信息以最大覆蓋范圍和最小重疊范圍傳播成了當下的重要研究問題之一。

影響力最大化問題可以定義為[1]：在給定的網(wǎng)絡(luò)中找到有限個數(shù)的活躍節(jié)點集，經(jīng)過特定的網(wǎng)絡(luò)傳播模型，使得最終活躍節(jié)點的數(shù)量達到最大。求解影響力最大化問題的算法一般包括兩個步驟，一是評估給定網(wǎng)絡(luò)上節(jié)點的影響力分布，并對它進行排序；二是在排序基礎(chǔ)上，選擇節(jié)點的最佳子集，使網(wǎng)絡(luò)傳播具有最大的覆蓋范圍。

目前提出的影響力最大化算法主要是各種中心性度量排序的算法，雖然該類算法時間快，但是精度相對較低。如度中心性算法(DC)、度折扣算法(DD)、k-shell算法[2]等，選擇具有最大散布的前k個節(jié)點為種子節(jié)點集，不考慮種子節(jié)點之間可能存在的覆蓋重疊?；谶呺H影響力進行排序的IMRank算法[3]，通過對每個節(jié)點計算它的邊際影響力來進行排序，最終根據(jù)排序順序來選擇影響力最大的節(jié)點。上述算法在找影響力最大的節(jié)點集時，沒有考慮種子集成員之間的覆蓋范圍。目前的社會網(wǎng)絡(luò)中，由于人際交往的多樣性和廣泛性，導致用戶與用戶之間的共同好友越來越多，所以在對相鄰用戶進行影響力建模時，可能會出現(xiàn)好友高度重疊，因此不一定會導致影響力最大化[4]?；谝陨峡紤]，Zareie等人提出了MCIM算法[1]，在考慮節(jié)點的直接影響和間接影響的基礎(chǔ)上還考慮了節(jié)點的覆蓋情況，但是，沒有考慮節(jié)點的多個屬性可能對種子節(jié)點選擇有不同的影響，所有屬性同等重要，與實際情況不相符，最終不一定能獲得導致影響力最大化的節(jié)點集。

考慮到各種中心性度量排序算法的影響范圍重疊問題和MCIM算法中屬性權(quán)重不明確問題，該文提出了帶權(quán)多準則影響力最大化算法模型(Multi-criteria Weight Influence Maximization，MWIM)。在該模型中，首先將影響力最大化問題建模為一個加權(quán)多準則問題，然后使用多種客觀權(quán)重求解方法來計算各準則的權(quán)重。隨后使用類似于理想解的優(yōu)劣解距離法(TOPSIS)來指定開始擴散過程的最佳節(jié)點集。

1 理論基礎(chǔ)

在社會網(wǎng)絡(luò)影響力最大化研究中，一般將社會網(wǎng)絡(luò)建模成圖G(V,E),其中V表示網(wǎng)絡(luò)中節(jié)點(個體)的集合，E表示網(wǎng)絡(luò)中邊(關(guān)系)的集合。網(wǎng)絡(luò)中的節(jié)點有兩種狀態(tài)：激活狀態(tài)和未激活狀態(tài)。激活狀態(tài)表示個體接受某種行為或者事務(wù)，未激活狀態(tài)則表示個體未接受某種行為和事務(wù)。處于激活狀態(tài)的節(jié)點對處于未激活狀態(tài)的鄰居節(jié)點存在影響，它可以嘗試去激活它的所有未被激活的鄰居節(jié)點。被激活的節(jié)點又會影響其他處于未激活狀態(tài)的節(jié)點。

TOPSIS算法是一種常用的綜合評價方法之一[5-6]，它能充分利用原始數(shù)據(jù)的信息，其結(jié)果能精確地反映各評價方案之間的差距。它用于從幾個可能的選項中選擇最佳的選項。由于這種算法的簡單性和有效性，吸引了許多研究者來解決經(jīng)典的問題[5]。在決策問題中，一些屬性表示利潤，一些屬性表示成本。正理想解和負理想解是在此算法中用于找到最佳替代方案的兩個主要概念。在TOPSIS算法中，利潤屬于極大型指標，成本屬于極小型指標，積極的理想最大化利潤標準，最小化成本，而消極的理想最大化成本標準，最小化利潤。TOPSIS算法尋求選擇與正理想解離最近與負理想解離最遠的替代方案[6]。

2 基于TOPSIS的MWIM算法

為了消除種子集成員相同好友帶來的精確度問題，該文提出了基于TOPSIS的MWIM算法。它由三部分組成，首先，計算網(wǎng)絡(luò)中節(jié)點的直接覆蓋和間接覆蓋屬性值，然后通過權(quán)重計算方法計算節(jié)點的直接覆蓋和間接覆蓋權(quán)重，最后再使用優(yōu)劣解距離法(TOPSIS)找到網(wǎng)絡(luò)的理想節(jié)點并將其作為新成員添加到種子集中。

在社會網(wǎng)絡(luò)中，對于具有更多連接關(guān)系的節(jié)點，度中心性度量方式認為它們具有更高的影響力，但是鄰居節(jié)點的連接關(guān)系沒有被考慮，所以為了消除只考慮節(jié)點的度中心性的偏差，所提出的方法還考慮了節(jié)點的二階鄰居數(shù)。記節(jié)點v的直接鄰居數(shù)為DNv=dv，其中dv表示節(jié)點v的度數(shù)，由于節(jié)點的二階鄰居重疊過多，為了提高準確度，使用信息熵來度量節(jié)點v的間接影響范圍，記IDNv=E1(v)+αE2(v)，其中E1(v)和E2(v)表示節(jié)點v的一階鄰居和二階鄰居的度的熵值。

(1)

(2)

在種子集的選擇過程中，不可避免地要考慮種子集間激活節(jié)點的重疊部分，因為最終比較的是種子集激活的節(jié)點的總數(shù)，即便種子集中的每個種子節(jié)點激活的節(jié)點數(shù)非常多，但是由于重疊過多，所以導致最終的節(jié)點激活總數(shù)增量非常小，從而種子集節(jié)點在選擇時，需要考慮它們之間的距離。所以，定義直接重疊(DO)和間接重疊(IDO)。直接重疊是判斷當前節(jié)點的鄰居節(jié)點中，有多少是種子集成員。而間接重疊是種子集與當前選擇節(jié)點的直接鄰居的重疊量。種子集中節(jié)點v的鄰居數(shù)決定了節(jié)點v與該集合直接重疊的程度，使用式(3)計算：

(3)

其中，u是節(jié)點v的鄰居節(jié)點，如果u也是種子集成員，則Su的值為1，否則為0。此外，間接重疊表示節(jié)點v的直接鄰居與種子集的鄰居節(jié)點的重疊程度，使用等式(4)計算：

(4)

其中，|Nu∩Nv|表示節(jié)點u與v的鄰居節(jié)點交集數(shù)，等式(5)檢查了所有已選種子集成員與節(jié)點v之間的重疊鄰居數(shù)。在每次的迭代中使用等式(3)和(4)來動態(tài)更新節(jié)點v的直接覆蓋和間接覆蓋值，其中較低的值表示最佳選擇節(jié)點。具體步驟如下：

首先為所有節(jié)點計算四個特征的值，然后按照等式(5)計算矩陣A：

(5)

其中，矩陣A的第i行表示第i個節(jié)點的四個特征值。

但是MCIM算法沒有考慮四個屬性的權(quán)重，其中DO和IDO屬性最大值與最小值差值很大，大多數(shù)節(jié)點的DO和IDO值為0，這就表明了四個屬性的變異程度是不一樣的，所提供的信息量也不一樣。為了更精確地基于四個屬性來選擇種子集，引入權(quán)重來考量四個屬性對節(jié)點選擇所做出的貢獻大小是很有必要的，也在此基礎(chǔ)上提出了MWIM算法。其中，在MWIM算法中，按照等式(6)來計算矩陣A：

(6)

但是在計算權(quán)重時，為了避免因為人為的決策或者意圖導致計算結(jié)果受主觀偏好的影響，該文通過客觀賦權(quán)法來計算權(quán)重。

在MWIM中，由于要考慮多個指標的綜合評價，所以考慮了三種目前應(yīng)用最廣泛的客觀賦權(quán)法、熵權(quán)法[7]、CRITIC法[8]和標準離差法[9]。

如算法1所示，在MWIM算法中，首先初始化矩陣A，其中DNv表示節(jié)點v的直接鄰居數(shù)，IDNv表示節(jié)點v的間接鄰居數(shù)，DOv表示節(jié)點v與種子集節(jié)點之間的直接重疊數(shù)，IDOv表示節(jié)點v與種子集節(jié)點之間的間接重疊數(shù)。在第5行中結(jié)合了中心性度量中的度中心性算法，通過求解節(jié)點的最大度數(shù)來確定種子集中的第一個節(jié)點u。第8行通過刪除種子節(jié)點u來更新矩陣A。9～14行通過遍歷種子集節(jié)點來更新DO與IDO值。15行說明了在MWIM算法中使用等式(7)來對DO和IDO值進行正向化。16行中通過歸一化操作對矩陣A中的數(shù)據(jù)消除量綱。第17行中的權(quán)重計算方法為上文中介紹的熵權(quán)法，CRITIC法和標準離差法。在第18行中，通過TOPSIS來計算剩余節(jié)點與種子集節(jié)點之間的方案距離并排序，以此找到的最優(yōu)方案也就是種子節(jié)點。

在下一節(jié)中，將通過在5個真實網(wǎng)絡(luò)上的實驗來評估MWIM算法。其中，C_MWIM是使用CRITIC加權(quán)法的MWIM方法，E_MWIM是使用熵權(quán)法的MWIM方法，S_MWIM是使用標準離差法的MWIM方法。

(7)

算法 1：MWIM偽代碼。

1.輸入：G，k//G是一個無向無權(quán)圖，k是種子集大小

2.輸出：種子集SS

3.SS=φ

5.s最大度的節(jié)點

6.SS=SS∪{s}

7.fori= 1 tok-1 do

8.A=A-{s}

9. for eachv∈Nsdo

10.DOv=DOv-1

11.for eachw∈Nvdo

12.IDOw=IDOw-|Nw∩Ns|

13. end for

14. end for

15.使用等式(7)對DO和IDO正向化

16.對矩陣A歸一化消除量綱得矩陣Z

17.計算矩陣Z中各個指標的權(quán)重w=(w1,w2,…,wm)T

18.通過TOPSIS(A)找到最優(yōu)方案s

19.SS=SS∪{s}

20.end for

21.返回SS

3 實驗和對建議方法的評估

3.1 實驗網(wǎng)絡(luò)

為了評估MWIM算法的性能，與MCIM算法、CELF算法、K-shell算法、IMRank算法等方法進行了比較。由于CELF方法的時間復雜度過高，所以只在小型生成網(wǎng)絡(luò)中與它進行比較。聚類系數(shù)指的是一個點的鄰接點之間相互連接的程度，例如生活社會網(wǎng)絡(luò)中，你的朋友之間的相互認識程度，所以聚類系數(shù)值越大，節(jié)點之間的互連程度也越大，共同鄰接點也越多。因此針對聚類系數(shù)的大小，選取了聚類系數(shù)值過大，適中和過小的四個真實網(wǎng)絡(luò)來對以上方法進行比較。四個網(wǎng)絡(luò)特征如表1所示，其中Hamsersters(HAM)網(wǎng)絡(luò)[10]表示基于網(wǎng)站hamsterster.com的用戶之間的友誼和家庭關(guān)系的網(wǎng)絡(luò)。Company(CPY)網(wǎng)絡(luò)[10]是使用來自大型歐洲研究機構(gòu)的電子郵件數(shù)據(jù)生成的。Sport(SPT)網(wǎng)絡(luò)[10]收集有關(guān)Facebook頁面的數(shù)據(jù)(2017年11月)。Gnutella(GLA)網(wǎng)絡(luò)[11]是從2002年8月開始的Gnutella對等文件共享網(wǎng)絡(luò)的快照序列。2002年8月總共收集了9個Gnutella網(wǎng)絡(luò)快照。節(jié)點表示Gnutella網(wǎng)絡(luò)拓撲中的主機，邊緣表示Gnutella主機之間的連接。

表1 網(wǎng)絡(luò)信息

3.2 評估指標

為了模擬現(xiàn)實世界中的傳播過程，使用流行病模型[12-13]來進行節(jié)點擴散建模。SIR擴展模型早已用于評估種子集的影響傳播能力。

流行病模型：該模型被廣泛用于對社會網(wǎng)絡(luò)中的消息傳播過程進行建模[14]。該文將使用流行病模型中的SIR模型[15-16]來模擬擴展過程。在該模型中，每個節(jié)點可以處于以下三種狀態(tài)之一：S(易感染)、I(已感染)和R(已恢復)。首先，屬于初始種子集的節(jié)點處于狀態(tài)I，其余節(jié)點都處于狀態(tài)S。在每個時間戳中，處于狀態(tài)I的每個節(jié)點v都試圖感染其鄰居節(jié)點。為了這個目的，它以概率β感染狀態(tài)為S的每個鄰居節(jié)點，將它們移動到狀態(tài)I。節(jié)點v本身然后以概率α進入狀態(tài)R。當狀態(tài)為I的節(jié)點存在時，該過程將重復進行。最后，R節(jié)點的數(shù)量表示初始種子集的影響范圍。為了獲得更準確的實驗，SIR過程需要運行多次，并將R節(jié)點的平均數(shù)量視為影響力的大小。

首先將種子集節(jié)點設(shè)置為狀態(tài)I，其余節(jié)點全部為S狀態(tài)，為了消除少數(shù)次數(shù)的特殊性，將循環(huán)500次SIR過程，最后統(tǒng)計R狀態(tài)的節(jié)點數(shù)，取平均值，數(shù)值越大，說明算法效果越好。

3.3 在小網(wǎng)絡(luò)上進行實驗

為了對比MWIM算法與CELF算法的擴散效果，將使用空手道俱樂部網(wǎng)絡(luò)(Zachary karate club)[10]，如圖1所示。

圖1 空手道俱樂部網(wǎng)絡(luò)

該網(wǎng)絡(luò)包含韋恩·扎卡里(Wayne Zachary)于1977年收集的大學空手道俱樂部成員之間的社會聯(lián)系。該網(wǎng)絡(luò)有34個節(jié)點78條邊。該網(wǎng)絡(luò)劃分為兩個社區(qū)，分別以節(jié)點0和節(jié)點33為中心。

為了保證實驗結(jié)果的可靠性，在使用SIR模型來評估種子集的傳播情況時，分別迭代了1 000，3 000，6 000和10 000次，實驗結(jié)果如圖2所示。

圖2 小網(wǎng)絡(luò)擴散結(jié)果

實驗結(jié)果表明，隨著迭代次數(shù)的增加，各方法越來越穩(wěn)定，MWIM算法的三種權(quán)值方法所得結(jié)果完全一致，CELF算法與其他方法的差值也保持不變，K-shell算法和IMRank算法隨著迭代次數(shù)的增加，也基本上完全重合。在表2中，給出了迭代次數(shù)為10 000時，各方法每次選擇的種子集。

表2 種子集大小k=2,3,4,5,6時各算法所選種子集

3.4 在大網(wǎng)絡(luò)上進行實驗

針對不同聚類系數(shù)，比較在三種重疊程度下的MWIM算法與K-shell、IMRank和MCIM算法的擴散效果。種子集的大小從10變到50，每次增加10。實驗如圖3所示。

圖3 各算法擴散對比

圖3結(jié)果表明，三種加權(quán)的MWIM方法所選擇的種子集比MICM方法具有更高的影響散布。隨著k值的增加，在HAM，CPY，SPT這三個網(wǎng)絡(luò)上，MWIM的散布情況更為突出，因為在這三個網(wǎng)絡(luò)中，節(jié)點的鄰接節(jié)點重疊區(qū)域較多，所以在等式(8)的矩陣A中直接重疊和間接重疊屬性的非零值更多，在計算四個屬性權(quán)重時，由于重疊屬性的變異程度更大，所以對于重疊屬性給出了更高的權(quán)重。IMRank方法的影響范圍最低，因為它是去計算每個節(jié)點的邊際影響力，再根據(jù)邊際影響力排序，不停地迭代這個過程，最終的排列順序就是節(jié)點的影響力大小排序，它忽略了節(jié)點的重疊。對于K-shell算法，它是通過不停地對節(jié)點分層，最后層數(shù)越高的節(jié)點認為它的影響力越大，通過對比HAM和SPT、GLA和CPY這兩組實驗結(jié)果可以發(fā)現(xiàn)，K-shell算法在HAM網(wǎng)絡(luò)上隨著k值的增加，散布情況越來越靠近MWIM算法，而在SPT網(wǎng)絡(luò)上隨著k值的增加，與MWIM算法的散布差值越來越大。對比兩個網(wǎng)絡(luò)的屬性發(fā)現(xiàn)，主要的差異表現(xiàn)在聚類系數(shù)上，聚類系數(shù)越大，節(jié)點間結(jié)成團的程度越大，比較之下，HAM網(wǎng)絡(luò)上的節(jié)點團程度更大，所以K-shell算法在劃分層數(shù)的時候，在HAM網(wǎng)絡(luò)上，更能凸顯HAM網(wǎng)絡(luò)的層次。但是對比GLA和CPY網(wǎng)絡(luò)，隨著k值的增加，GLA網(wǎng)絡(luò)的散布情況越來越與MWIM算法相近，而在CPY網(wǎng)絡(luò)上，散布差值越來越大，它們的主要差異也是表現(xiàn)在聚類系數(shù)上，由于GLA網(wǎng)絡(luò)的聚類系數(shù)過小，節(jié)點與鄰居節(jié)點的互聯(lián)程度也非常小，所以K-shell算法在對它進行層次劃分時，層數(shù)會很少，并且每一層的節(jié)點數(shù)會很多，導致節(jié)點間的重要程度都不大，MWIM算法在對GLA網(wǎng)絡(luò)計算權(quán)重時，由于節(jié)點之間離散度大，重疊程度小，所以權(quán)重差異性也不大，所以會出現(xiàn)圖3(b)的情況。

通過實驗結(jié)果可以看出，使用熵權(quán)法和標準離差法的賦權(quán)結(jié)果較為接近，因為熵權(quán)法和標準離差法的基本思路非常相似，都是通過指標變異的大小來確定權(quán)重。對于CRITIC賦權(quán)法，它還額外考慮了各指標之間的沖突性，所以在聚類系數(shù)更大的網(wǎng)絡(luò)上，它的結(jié)果更好一些。

3.5 時間對比實驗

在這個實驗中，將比較MWIM算法與其他算法在不同k值時的平均運行時間。實驗結(jié)果如圖4、圖5所示。圖4結(jié)果表明，CELF算法平均運行時間較長，不適用于大型網(wǎng)絡(luò)的種子集求解。在小網(wǎng)絡(luò)上MWIM算法與K-shell算法和IMRank算法的平均運行時間相差不大。

圖4 不同算法在空手道俱樂部的運行時間對比

圖5 各算法平均運行時間

圖5的結(jié)果表明，在HAM網(wǎng)絡(luò)上，MWIM算法的平均運行時間大于K-shell算法和IMRank算法，因為HAM網(wǎng)絡(luò)的聚類系數(shù)過大，所以節(jié)點與節(jié)點之間的聯(lián)系更為緊密，在計算重疊部分時所需時間更多。在GLA，CPY和SPT網(wǎng)絡(luò)上，IMRank算法的平均運行時間最大。其中，在四個網(wǎng)絡(luò)中K-shell算法的平均運行時間都是最小。由于IMRank算法是通過遍歷一遍所有節(jié)點，求每個節(jié)點的邊際影響力，再根據(jù)邊際影響力進行排序，由于計算所有節(jié)點的邊際影響力的時間遠遠大于選擇種子集的時間，所以IMRank算法隨k值的變化不明顯。在GLA網(wǎng)絡(luò)上，K-shell算法與MWIM算法的平均運行時間相差不大，因為GLA網(wǎng)絡(luò)的聚類系數(shù)非常小，所以節(jié)點與節(jié)點之間的聯(lián)系稀疏，導致節(jié)點間的重疊部分少，MWIM算法在計算重疊部分時所花時間就大大減少。

4 結(jié)束語

近年來，信息在社會網(wǎng)絡(luò)上的傳播引起了極大的關(guān)注，選擇有影響力的用戶集對于信息的傳播尤為重要，如何選擇用戶即成了一個關(guān)鍵問題。針對不同的網(wǎng)絡(luò)，學者們提出了不同的方法。在選擇有影響力的用戶集時應(yīng)該不單單只看用戶的鄰居數(shù)量，還應(yīng)該考慮鄰居的影響范圍以及他們影響的重疊量和距離。該文提出了一種MWIM方法來選擇具有最大影響力的用戶集，在該方法中，不僅考慮了直接鄰居的影響范圍，還考慮了間接鄰居的影響范圍，在考慮如何度量各個因素的影響力大小時，引入客觀權(quán)重來解決這個問題。在度量了各個因素的權(quán)重之后，使用TOPSIS方法來選擇一組當前最優(yōu)的節(jié)點作為后續(xù)擴展的種子集節(jié)點。在各種真實網(wǎng)絡(luò)上進行了一系列不同的實驗，以研究和評估該方法的準確性和效率。使用SIR模型來對種子集進行模擬擴散，結(jié)果表明MWIM算法在選擇種子集時，比其他算法更為精確。在使用小網(wǎng)絡(luò)進行影響力種子集選擇實驗中，MWIM算法的結(jié)果更接近于CELF算法，在每一輪的種子集選擇中，都能準確地選取到重要節(jié)點。在提出的各種算法中，種子集大小k已被視為影響力最大化問題的輸入值，尚未指定最佳k值的標準。但是，適當?shù)膋值可以使信息傳播所需消耗和收益達到一個最佳值。在未來的工作中可以考慮最佳k值的選取研究，還有在聚類系數(shù)特別小的網(wǎng)絡(luò)上怎么對MWIM算法進行優(yōu)化。