郭茂林，孔 兵

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

0 引 言

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

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

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

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

1 理論基礎(chǔ)

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

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

2 基于TOPSIS的MWIM算法

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

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

(1)

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

但是在計(jì)算權(quán)重時(shí)，為了避免因?yàn)槿藶榈臎Q策或者意圖導(dǎo)致計(jì)算結(jié)果受主觀偏好的影響，該文通過客觀賦權(quán)法來(lái)計(jì)算權(quán)重。

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

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

在下一節(jié)中，將通過在5個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)來(lái)評(píng)估MWIM算法。其中，C_MWIM是使用CRITIC加權(quán)法的MWIM方法，E_MWIM是使用熵權(quán)法的MWIM方法，S_MWIM是使用標(biāo)準(zhǔn)離差法的MWIM方法。

(7)

算法 1：MWIM偽代碼。

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

2.輸出：種子集SS

3.SS=φ

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

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)對(duì)DO和IDO正向化

16.對(duì)矩陣A歸一化消除量綱得矩陣Z

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

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

19.SS=SS∪{s}

20.end for

21.返回SS

3 實(shí)驗(yàn)和對(duì)建議方法的評(píng)估

3.1 實(shí)驗(yàn)網(wǎng)絡(luò)

為了評(píng)估MWIM算法的性能，與MCIM算法、CELF算法、K-shell算法、IMRank算法等方法進(jìn)行了比較。由于CELF方法的時(shí)間復(fù)雜度過高，所以只在小型生成網(wǎng)絡(luò)中與它進(jìn)行比較。聚類系數(shù)指的是一個(gè)點(diǎn)的鄰接點(diǎn)之間相互連接的程度，例如生活社會(huì)網(wǎng)絡(luò)中，你的朋友之間的相互認(rèn)識(shí)程度，所以聚類系數(shù)值越大，節(jié)點(diǎn)之間的互連程度也越大，共同鄰接點(diǎn)也越多。因此針對(duì)聚類系數(shù)的大小，選取了聚類系數(shù)值過大，適中和過小的四個(gè)真實(shí)網(wǎng)絡(luò)來(lái)對(duì)以上方法進(jìn)行比較。四個(gè)網(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]是使用來(lái)自大型歐洲研究機(jī)構(gòu)的電子郵件數(shù)據(jù)生成的。Sport(SPT)網(wǎng)絡(luò)[10]收集有關(guān)Facebook頁(yè)面的數(shù)據(jù)(2017年11月)。Gnutella(GLA)網(wǎng)絡(luò)[11]是從2002年8月開始的Gnutella對(duì)等文件共享網(wǎng)絡(luò)的快照序列。2002年8月總共收集了9個(gè)Gnutella網(wǎng)絡(luò)快照。節(jié)點(diǎn)表示Gnutella網(wǎng)絡(luò)拓?fù)渲械闹鳈C(jī)，邊緣表示Gnutella主機(jī)之間的連接。

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

3.2 評(píng)估指標(biāo)

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

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

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

3.3 在小網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)

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

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

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

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

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

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

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

3.4 在大網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)

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

圖3 各算法擴(kuò)散對(duì)比

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

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

3.5 時(shí)間對(duì)比實(shí)驗(yàn)

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

圖4 不同算法在空手道俱樂部的運(yùn)行時(shí)間對(duì)比

圖5 各算法平均運(yùn)行時(shí)間

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

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

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