基于TOPSIS權重的社會網絡影響力最大化

郭茂林，孔 兵

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

0 引 言

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

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

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

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

1 理論基礎

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

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

2 基于TOPSIS的MWIM算法

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

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

(1)

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

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

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

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

在下一節中，將通過在5個真實網絡上的實驗來評估MWIM算法。其中，C_MWIM是使用CRITIC加權法的MWIM方法，E_MWIM是使用熵權法的MWIM方法，S_MWIM是使用標準離差法的MWIM方法。

(7)

算法 1：MWIM偽代碼。

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

2.輸出：種子集SS

3.SS=φ

5.s最大度的節點

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中各個指標的權重w=(w1,w2,…,wm)T

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

19.SS=SS∪{s}

20.end for

21.返回SS

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

3.1 實驗網絡

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

表1 網絡信息

3.2 評估指標

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

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

首先將種子集節點設置為狀態I，其余節點全部為S狀態，為了消除少數次數的特殊性，將循環500次SIR過程，最后統計R狀態的節點數，取平均值，數值越大，說明算法效果越好。

3.3 在小網絡上進行實驗

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

圖1 空手道俱樂部網絡

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

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

圖2 小網絡擴散結果

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

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

3.4 在大網絡上進行實驗

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

圖3 各算法擴散對比

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

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

3.5 時間對比實驗

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

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

圖5 各算法平均運行時間

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

4 結束語

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