胡 敏，孫欣然，黃宏程,2+

1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065

2.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

邊緣覆蓋去重的社交網(wǎng)絡(luò)影響力最大化算法*

胡 敏1，孫欣然1，黃宏程1,2+

1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065

2.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

社交網(wǎng)絡(luò)；影響力最大化；邊緣貢獻(xiàn)；啟發(fā)式算法

1 引言

人們因共同學(xué)習(xí)、生活、工作，形成了不同圈中的復(fù)雜社交關(guān)系，人與人在現(xiàn)實(shí)生活中的交往形成了線下的社交網(wǎng)絡(luò)，這便是復(fù)雜社交網(wǎng)絡(luò)的開(kāi)端。隨著互聯(lián)網(wǎng)的普及和高速發(fā)展，人們獲取信息的方式和途徑從以前的報(bào)刊、雜志、電視等擴(kuò)展到了互聯(lián)網(wǎng)之中，他們復(fù)雜的社會(huì)交往關(guān)系也從現(xiàn)實(shí)社會(huì)延伸到虛擬網(wǎng)絡(luò)之中，形成了線上的社交網(wǎng)絡(luò)。

Domingos等人[1]在2001年提出節(jié)點(diǎn)影響力最大化問(wèn)題，之后該問(wèn)題便得到了極大的關(guān)注。隨著社交網(wǎng)絡(luò)的興起，網(wǎng)絡(luò)監(jiān)管與輿論引導(dǎo)控制變得越來(lái)越重要。此外，互聯(lián)網(wǎng)社交網(wǎng)絡(luò)中的用戶數(shù)激增，商家逐漸趨向于在社交網(wǎng)絡(luò)這個(gè)巨大的平臺(tái)上發(fā)布廣告信息，進(jìn)行商品的推廣營(yíng)銷(xiāo)。從根本上說(shuō)，輿論引導(dǎo)和商品推廣是特定價(jià)值信息在社交網(wǎng)絡(luò)平臺(tái)上的最大范圍擴(kuò)散，其中一個(gè)關(guān)鍵問(wèn)題是如何選取網(wǎng)絡(luò)中這些信息傳播影響力最大的節(jié)點(diǎn)集，也就是影響力最大化問(wèn)題，這也一直是研究的熱點(diǎn)和難點(diǎn)。

Kempe等人[2]提出爬山貪心算法Basic-greedy，這是針對(duì)節(jié)點(diǎn)影響力最大化問(wèn)題最初始的解決方案。由于貪心算法的時(shí)間復(fù)雜度過(guò)高，不適用于大規(guī)模網(wǎng)絡(luò)。針對(duì)該問(wèn)題，研究者對(duì)算法進(jìn)行了改進(jìn)優(yōu)化[3-6]，提出了CELF（cost-effective lazy forward）、CELF++、New-greedy、Mix-greedy等算法。這些改進(jìn)算法雖提高了時(shí)間效率，但對(duì)于大規(guī)模網(wǎng)絡(luò)仍然不能適用。為了研究大規(guī)模網(wǎng)絡(luò)中的節(jié)點(diǎn)影響力最大化問(wèn)題，啟發(fā)式算法應(yīng)運(yùn)而生。啟發(fā)式算法通常具有運(yùn)行時(shí)間短的特點(diǎn)，但算法準(zhǔn)確度相對(duì)較差，傳播范圍相對(duì)較小。階段式算法是貪心算法與啟發(fā)式算法的綜合型算法[7-9]，通常在算法初始選取階段采用啟發(fā)式思想評(píng)估節(jié)點(diǎn)影響力，后續(xù)采用貪心算法細(xì)化選取。

社交網(wǎng)絡(luò)中通常節(jié)點(diǎn)數(shù)量多，關(guān)系連邊復(fù)雜，屬于大規(guī)模復(fù)雜網(wǎng)絡(luò)，貪心算法難以滿足目前大規(guī)模社交網(wǎng)絡(luò)的要求，因此本文采用啟發(fā)式算法的思想。針對(duì)啟發(fā)式算法中傳播影響范圍相對(duì)較小的問(wèn)題，本文考慮節(jié)點(diǎn)全局結(jié)構(gòu)信息和鄰近結(jié)構(gòu)信息兩方面來(lái)評(píng)估節(jié)點(diǎn)影響力，發(fā)現(xiàn)并解決了邊緣節(jié)點(diǎn)影響范圍重合問(wèn)題，提出了基于邊緣覆蓋去重的啟發(fā)式算法（edge cover algorithm，ECA）。

本文組織結(jié)構(gòu)如下：第2章介紹了相關(guān)工作；第3章研究了基于邊緣覆蓋去重的影響力最大化算法；第4章給出了實(shí)驗(yàn)結(jié)果及分析；第5章對(duì)本文工作進(jìn)行總結(jié)。

2 相關(guān)工作

2.1 傳播模型

在尋找特定網(wǎng)絡(luò)中的影響力節(jié)點(diǎn)集時(shí)，需要借助相應(yīng)的傳播模型。一般將社會(huì)網(wǎng)絡(luò)抽象為有向圖G(V,E)，將用戶抽象為節(jié)點(diǎn)，V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合；將用戶之間的連接關(guān)系抽象為連邊，E表示網(wǎng)絡(luò)中所有連邊的集合。目前常用的傳播模型有線性閾值模型（linear threshold model，LT）[10]和獨(dú)立級(jí)聯(lián)模型（independent cascade model，IC）[11]。在這兩種模型中，網(wǎng)絡(luò)中的節(jié)點(diǎn)存在活躍或非活躍兩種狀態(tài)且只處于其中之一，節(jié)點(diǎn)可以從非活躍狀態(tài)轉(zhuǎn)變?yōu)榛钴S狀態(tài)，反之則不成立。本文選取獨(dú)立級(jí)聯(lián)模型作為傳播模型，并對(duì)其進(jìn)行詳細(xì)介紹。

IC模型假設(shè)一個(gè)活躍節(jié)點(diǎn)嘗試激活其每個(gè)鄰居節(jié)點(diǎn)的機(jī)會(huì)有且只有一次，若激活失敗，則對(duì)其失去影響力，且每一次激活行為的激活概率相對(duì)獨(dú)立。假設(shè)A為初始活躍節(jié)點(diǎn)集，活躍節(jié)點(diǎn)的傳播規(guī)則如下：

（1）非活躍節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)u在傳播的t時(shí)刻嘗試激活節(jié)點(diǎn)v，且u激活v的概率為pu,v。

（2）若v被激活，則v的v+1時(shí)刻轉(zhuǎn)換為活躍節(jié)點(diǎn)；反之，v的狀態(tài)不發(fā)生改變。

（3）不斷重復(fù)上述過(guò)程，當(dāng)網(wǎng)絡(luò)中的活躍節(jié)點(diǎn)都沒(méi)有影響力時(shí)，傳播結(jié)束。

2.2 啟發(fā)式算法研究

基于Random、Degree、Centrality的算法[2]是啟發(fā)式算法最基本的算法。常見(jiàn)的權(quán)威算法包括陳衛(wèi)等人提出的Degree-discount、基于最大影響力子樹(shù)的PMIA（prefix excluding maximum influence arborescence）啟發(fā)式[12]、基于有向無(wú)環(huán)圖的LDAG（labeled directed acyclic graph）啟發(fā)式[13]以及Jung等人提出的綜合效果最優(yōu)的IRIE（influence ranking influence estimation）啟發(fā)式[14]等。很多人針對(duì)這些算法進(jìn)行了改進(jìn)，并且取得了更優(yōu)的效果。2010年，Kitsak等人[15]提出了k-core算法來(lái)評(píng)估節(jié)點(diǎn)的傳播影響力，并且提出了基于覆蓋的最大核算法和最大度算法。2011年，Goyal等人[16]分析了LDAG算法的不足，針對(duì)LDAG算法中存在的影響力路徑忽略的問(wèn)題進(jìn)行改進(jìn)，提出了基于節(jié)點(diǎn)影響力的簡(jiǎn)單路徑SIMPATH啟發(fā)式算法。2015年，曹玖新等人[17]提出了一種基于 k-core的影響力最大化算法（core covering algorithm，CCA），算法結(jié)合k-core算法和度中心性求出每個(gè)節(jié)點(diǎn)的影響力，對(duì)節(jié)點(diǎn)的影響半徑（d=1和d=2）進(jìn)行了討論。

相比于貪心算法，啟發(fā)式算法的求解時(shí)間具有較大優(yōu)勢(shì)，但其算法準(zhǔn)確度較差，因此提高算法準(zhǔn)確度是啟發(fā)式算法研究的長(zhǎng)期目標(biāo)。

在以上提到的影響力最大化啟發(fā)式算法研究中忽略了影響范圍重合問(wèn)題。一些考慮影響范圍重合的覆蓋類算法研究也并沒(méi)有考慮邊緣貢獻(xiàn)的問(wèn)題。針對(duì)這一問(wèn)題，本文在考慮邊緣貢獻(xiàn)的條件下研究了影響力最大化算法。

3 基于邊緣覆蓋去重的影響力最大化算法

本文采用啟發(fā)式算法的思想，在IC模型的基礎(chǔ)上，提出了基于邊緣覆蓋去重的啟發(fā)式算法ECA。該算法考慮節(jié)點(diǎn)全局結(jié)構(gòu)信息和鄰近結(jié)構(gòu)信息兩方面來(lái)評(píng)估節(jié)點(diǎn)影響力，并通過(guò)去除已選節(jié)點(diǎn)影響范圍內(nèi)的所有節(jié)點(diǎn)的方式來(lái)屏蔽已選節(jié)點(diǎn)對(duì)未標(biāo)記范圍內(nèi)邊緣節(jié)點(diǎn)的影響，以此來(lái)除去節(jié)點(diǎn)之間的影響重合范圍。下面首先介紹構(gòu)成ECA算法的評(píng)估單個(gè)節(jié)點(diǎn)影響力、去除邊緣節(jié)點(diǎn)影響力范圍重合兩部分，然后整體描述算法的總流程，最后進(jìn)行實(shí)例分析。

3.1 單個(gè)影響力節(jié)點(diǎn)選取

利用節(jié)點(diǎn)影響力最大化算法選取的節(jié)點(diǎn)稱為種子節(jié)點(diǎn)。根據(jù)實(shí)際需求或成本等的不同，不同應(yīng)用場(chǎng)景中需要選取的節(jié)點(diǎn)數(shù)也存在差異。若需要選取網(wǎng)絡(luò)中的k個(gè)種子節(jié)點(diǎn)，ECA算法利用以下方式來(lái)選取網(wǎng)絡(luò)中最具信息傳播影響力的節(jié)點(diǎn)集。

3.1.1 根據(jù)k-core算法批量選取

k-core算法通過(guò)對(duì)網(wǎng)絡(luò)層次結(jié)構(gòu)的層層分解，評(píng)估出節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)的全局性核心程度，即k-core算法是把網(wǎng)絡(luò)中節(jié)點(diǎn)度小于ks的節(jié)點(diǎn)去除的過(guò)程。

本文利用節(jié)點(diǎn)的k-core數(shù)ks值來(lái)評(píng)估節(jié)點(diǎn)的全局結(jié)構(gòu)影響力。從k-core算法可以看出，該算法雖然可以在一定程度上評(píng)估出節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力大小，但仍然不夠細(xì)分，無(wú)法挑選出唯一的影響力最大節(jié)點(diǎn)。因此本文在進(jìn)行節(jié)點(diǎn)信息傳播影響力評(píng)估時(shí)，在k-core的基礎(chǔ)上進(jìn)一步考慮節(jié)點(diǎn)鄰近結(jié)構(gòu)信息。

3.1.2 根據(jù)節(jié)點(diǎn)鄰近結(jié)構(gòu)信息細(xì)化選取

結(jié)合獨(dú)立級(jí)聯(lián)模型的特點(diǎn)，評(píng)估節(jié)點(diǎn)鄰近結(jié)構(gòu)影響力Iv-near時(shí)，ECA算法考慮了節(jié)點(diǎn)v對(duì)其鄰居的貢獻(xiàn)程度以及節(jié)點(diǎn)v的集聚系數(shù)。v的每一條連邊對(duì)其鄰居節(jié)點(diǎn)的貢獻(xiàn)度體現(xiàn)了v對(duì)其每個(gè)鄰居節(jié)點(diǎn)的影響程度大小，取鄰居節(jié)點(diǎn)度的倒數(shù)即1/di為貢獻(xiàn)值；節(jié)點(diǎn)集聚系數(shù)（clustering coefficient）Cv描述了節(jié)點(diǎn)的鄰居節(jié)點(diǎn)連接的緊密性，v的集聚系數(shù)越大，v的鄰居節(jié)點(diǎn)之間存在的邊數(shù)ev越大，則當(dāng)以v為初始傳播節(jié)點(diǎn)時(shí)，信息成功傳播給其鄰居節(jié)點(diǎn)的可能性越大。因此定義節(jié)點(diǎn)v的鄰近結(jié)構(gòu)影響力如下：

式中，α是權(quán)值，根據(jù)實(shí)驗(yàn)結(jié)果調(diào)整得出具體值且α＞0.5；Nv是v的鄰居節(jié)點(diǎn)集，根據(jù)圖論知識(shí)可以推出；dv(dv-1)/2是v的鄰居節(jié)點(diǎn)組成的全連通圖具有的連邊數(shù)量。通過(guò)式（1）計(jì)算Iv-near值，選取Iv-near值最大的節(jié)點(diǎn)為種子節(jié)點(diǎn)。

3.2 去除邊緣節(jié)點(diǎn)影響范圍重合

節(jié)點(diǎn)影響范圍定義為：利用節(jié)點(diǎn)（集）作為信息初始傳播節(jié)點(diǎn)，信息傳播結(jié)束后已激活的節(jié)點(diǎn)總數(shù)。節(jié)點(diǎn)影響范圍重合是指：通過(guò)指定的方法評(píng)估出來(lái)的具有較大影響力節(jié)點(diǎn)的影響區(qū)域部分重疊的情況。

影響范圍重合出現(xiàn)的原因是種子節(jié)點(diǎn)之間存在共鄰節(jié)點(diǎn)，且任意兩個(gè)節(jié)點(diǎn)i、j影響力重合范圍（overlapped range，OR）滿足：

由于在獨(dú)立級(jí)聯(lián)傳播模型中，每條邊具有傳播概率獨(dú)立的特性，基于獨(dú)立級(jí)聯(lián)模型的影響力最大化算法在選取種子節(jié)點(diǎn)時(shí)需要考慮將節(jié)點(diǎn)可能影響范圍最大化。節(jié)點(diǎn)影響力重合問(wèn)題使節(jié)點(diǎn)信息傳播影響力不能得到最大的發(fā)揮。針對(duì)上述問(wèn)題，覆蓋類算法如最大度覆蓋、最大核覆蓋以及CCA算法均利用標(biāo)記已選取節(jié)點(diǎn)的影響區(qū)域的方法來(lái)解決。但由于此類算法在選取節(jié)點(diǎn)后，并沒(méi)有考慮已標(biāo)記區(qū)域?qū)ξ礃?biāo)記區(qū)域邊緣節(jié)點(diǎn)的影響，從而導(dǎo)致后續(xù)選取的節(jié)點(diǎn)仍然存在邊緣影響范圍的重合問(wèn)題。為了更好地闡述邊緣節(jié)點(diǎn)影響范圍重合問(wèn)題，現(xiàn)做出以下定義。

定義1（邊緣貢獻(xiàn)）邊緣貢獻(xiàn)是指在覆蓋類影響力最大化算法中，由于已標(biāo)記區(qū)域與未標(biāo)記區(qū)域節(jié)點(diǎn)存在連邊，從而對(duì)這些節(jié)點(diǎn)的傳播影響力評(píng)估產(chǎn)生貢獻(xiàn)。

圖1表示節(jié)點(diǎn)X、Y與已標(biāo)記區(qū)域的連接結(jié)構(gòu)。從圖中可以看出，覆蓋類算法選取種子節(jié)點(diǎn)后將其鄰居節(jié)點(diǎn)標(biāo)記為節(jié)點(diǎn)影響范圍，而已標(biāo)記區(qū)域與未標(biāo)記區(qū)域的邊緣節(jié)點(diǎn)X仍存在連邊，即已標(biāo)記區(qū)域?qū)?jié)點(diǎn)X存在邊緣貢獻(xiàn)，這就導(dǎo)致了選取后續(xù)種子節(jié)點(diǎn)時(shí)節(jié)點(diǎn)影響力評(píng)估存在過(guò)量估計(jì)。在X、Y的節(jié)點(diǎn)影響力比較中對(duì)邊緣節(jié)點(diǎn)X更有利，從而導(dǎo)致邊緣節(jié)點(diǎn)影響范圍重合且重合范圍滿足：

Fig.1 Sketch map of edge node圖1 邊緣節(jié)點(diǎn)示意圖

下面通過(guò)一個(gè)具體的網(wǎng)絡(luò)W直觀分析現(xiàn)有覆蓋類影響力算法存在的邊緣節(jié)點(diǎn)影響范圍重合問(wèn)題。圖2展示了W的網(wǎng)絡(luò)拓?fù)洹?/p>

Fig.2 Network topology structure ofW圖2 網(wǎng)絡(luò)W的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

若需要的種子節(jié)點(diǎn)數(shù)為2，即k=2，利用CCA算法（d=1）的節(jié)點(diǎn)影響力評(píng)估方法可以得到以下結(jié)果。

不同核數(shù)的節(jié)點(diǎn)集合分別是：

不同度數(shù)的節(jié)點(diǎn)集合分別是：

綜合節(jié)點(diǎn)核數(shù)與度數(shù)選取出的備選種子節(jié)點(diǎn)為{1,3,6}。從這里可以看出，最大核覆蓋、最大度覆蓋、CCA算法的節(jié)點(diǎn)影響力評(píng)估方式均無(wú)法將節(jié)點(diǎn)影響力進(jìn)一步細(xì)分。為了后面問(wèn)題分析更為直觀，這里將節(jié)點(diǎn)1選為種子節(jié)點(diǎn)，則按照現(xiàn)存覆蓋類算法的標(biāo)記方式，將節(jié)點(diǎn)1的鄰居節(jié)點(diǎn)標(biāo)記。繼續(xù)根據(jù)節(jié)點(diǎn)原有核、度屬性選取標(biāo)記區(qū)域以外的節(jié)點(diǎn)，則下一個(gè)種子節(jié)點(diǎn)為6，選取結(jié)束。

從上述算法種子節(jié)點(diǎn)第二輪選取過(guò)程中可以看出，由于已標(biāo)記區(qū)域（圖3中的紅色節(jié)點(diǎn)）中節(jié)點(diǎn)3、5與未標(biāo)記區(qū)域邊緣節(jié)點(diǎn)6存在連邊，則已標(biāo)記區(qū)域?qū)?jié)點(diǎn)6產(chǎn)生邊緣貢獻(xiàn)，導(dǎo)致節(jié)點(diǎn)1與節(jié)點(diǎn)6的影響范圍重合且重合范圍OR1,6滿足：

Fig.3 Edge node influence range overlap圖3 邊緣節(jié)點(diǎn)影響范圍重合

針對(duì)上述邊緣節(jié)點(diǎn)影響范圍重合問(wèn)題，本文通過(guò)去除已標(biāo)記區(qū)域節(jié)點(diǎn)及連邊，并在下一次循環(huán)選取種子節(jié)點(diǎn)之前更新網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，最后根據(jù)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)重新計(jì)算節(jié)點(diǎn)影響力值，以新的節(jié)點(diǎn)影響力值大小為標(biāo)準(zhǔn)選取種子節(jié)點(diǎn)，以此來(lái)達(dá)到屏蔽已標(biāo)記區(qū)域?qū)ξ礃?biāo)記區(qū)域邊緣產(chǎn)生影響的目的。具體實(shí)現(xiàn)流程如下。

對(duì)于網(wǎng)絡(luò)G=(V,E)，當(dāng)選取第一個(gè)種子節(jié)點(diǎn)u后，刪除種子節(jié)點(diǎn)u和鄰居節(jié)點(diǎn)及其它們所有連邊，即：

式中，V′loop+1是刪除u及u的鄰居節(jié)點(diǎn)后的網(wǎng)絡(luò)節(jié)點(diǎn)集；Eloop+1是選取下一個(gè)種子節(jié)點(diǎn)前網(wǎng)絡(luò)的邊集；Eu、分別是u和其鄰居的邊集。

已標(biāo)記區(qū)域刪除后，在下一次循環(huán)開(kāi)始前網(wǎng)絡(luò)更新為：

式中，Visolated是網(wǎng)絡(luò)中的孤立節(jié)點(diǎn)集；Vloop+1是選取下一個(gè)種子節(jié)點(diǎn)前網(wǎng)絡(luò)的節(jié)點(diǎn)集。

由于刪除已標(biāo)記區(qū)域而出現(xiàn)的孤立節(jié)點(diǎn)信息傳播影響力極小，不具有被選取為種子節(jié)點(diǎn)的可能。因此利用式（10）檢測(cè)網(wǎng)絡(luò)中存在的孤立節(jié)點(diǎn)集，并將其從當(dāng)前網(wǎng)絡(luò)中刪除，最后形成全新的連通網(wǎng)絡(luò)并進(jìn)入下一次循環(huán)。通過(guò)上述去重方法，可有效避免邊緣貢獻(xiàn)帶來(lái)的節(jié)點(diǎn)影響力評(píng)估誤差，從而解決邊緣節(jié)點(diǎn)影響力范圍重合問(wèn)題。

3.3 ECA算法總流程

綜上所述，結(jié)合單個(gè)影響力節(jié)點(diǎn)選取和去重方案，ECA算法整體詳細(xì)步驟為：

（1）根據(jù)k-core算法選取ks值最大的節(jié)點(diǎn)。若出現(xiàn)多個(gè)節(jié)點(diǎn)ks值相同的情況，則到第（2）步；若結(jié)果唯一，則選為種子節(jié)點(diǎn)，到第（3）步。

（2）選取Iv-near值最大的節(jié)點(diǎn)。若出現(xiàn)多個(gè)節(jié)點(diǎn)Iv-near值相同的情況，則任意選取其中之一，到第（3）步；若結(jié)果唯一，則選為種子節(jié)點(diǎn)，到第（3）步。

（3）將選取的種子節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)從網(wǎng)絡(luò)中刪除，同時(shí)也刪除它們的所有連邊。

（4）更新網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

（5）檢測(cè)網(wǎng)絡(luò)中是否存在孤立節(jié)點(diǎn)，若存在則刪除孤立節(jié)點(diǎn)，更新網(wǎng)絡(luò)結(jié)構(gòu)；若不存在，則到第（6）步。

（6）回到步驟（1）繼續(xù)選取節(jié)點(diǎn)，直到選取k個(gè)種子節(jié)點(diǎn)為止。

根據(jù)上述原理，算法偽代碼如下。

算法1 ECA

假設(shè)網(wǎng)絡(luò)G=(V,E)有n個(gè)節(jié)點(diǎn)，m1條邊，要選取k個(gè)種子節(jié)點(diǎn)，ECA算法的復(fù)雜度分析如下：首次進(jìn)行種子節(jié)點(diǎn)選取時(shí)，利用k-core算法，復(fù)雜度為O(m1)；在選取種子節(jié)點(diǎn)后，刪除相關(guān)節(jié)點(diǎn)及連邊后更新網(wǎng)絡(luò)，此時(shí)網(wǎng)絡(luò)中有m2條邊，再次利用k-core算法，選取下一種子節(jié)點(diǎn)，此時(shí)復(fù)雜度為O(m1+m2)；以此類推，選取第k個(gè)種子節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)中的邊為mk，復(fù)雜度為O(mk-1+mk)。一共需要選取k個(gè)節(jié)點(diǎn)，因此ECA算法的復(fù)雜度為O[m1+(m1+m2)+…+(mk-1+mk)]，即O[2(m1+m2+…+mk)-mk]。相比于CCA算法的復(fù)雜度O(km)，該算法的復(fù)雜度略高，處于同一個(gè)數(shù)量級(jí)，但其準(zhǔn)確度優(yōu)于CCA算法。相比于貪心算法的復(fù)雜度O(kmn)，該算法的復(fù)雜度明顯優(yōu)于貪心算法。

4 仿真驗(yàn)證

4.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證ECA算法的合理性，本文利用IC模型作為傳播模型，美國(guó)安然公司E-mail網(wǎng)絡(luò)、DBLP網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)作為算法的仿真網(wǎng)絡(luò)。E-mail網(wǎng)絡(luò)是公司員工郵件交流形成的社交網(wǎng)絡(luò)。DBLP（Digital Bibliography Library Project）網(wǎng)絡(luò)是論文作者合作網(wǎng)絡(luò)。ca-HepPh（High Energy Physics-Phenomenology）網(wǎng)絡(luò)是高能物理現(xiàn)象科學(xué)合作作者提交論文的協(xié)作網(wǎng)絡(luò)。3個(gè)網(wǎng)絡(luò)均屬于無(wú)向網(wǎng)絡(luò)，且具有明顯的無(wú)標(biāo)度特性。網(wǎng)絡(luò)基本數(shù)據(jù)如表1所示。

Table 1 Network basic data表1 網(wǎng)絡(luò)基本數(shù)據(jù)

4.2 衡量指標(biāo)

通常情況下，準(zhǔn)確度是在給定的傳播模型基礎(chǔ)上，算法選定的種子節(jié)點(diǎn)在傳播結(jié)束后最終能夠影響到的節(jié)點(diǎn)數(shù)量，即節(jié)點(diǎn)影響范圍。在社交網(wǎng)絡(luò)的商品推廣等應(yīng)用領(lǐng)域中，商品信息的傳播范圍一定程度上代表了推廣工作的成功程度，算法準(zhǔn)確度越高，節(jié)點(diǎn)影響范圍越大，則影響到的社交用戶越多。因此，準(zhǔn)確度是評(píng)價(jià)影響力最大化算法的重要指標(biāo)。本文考察種子節(jié)點(diǎn)數(shù)k從1增加到30傳播范圍的變化情況，并與其他相關(guān)算法進(jìn)行比較分析。另外，為了更加顯著地體現(xiàn)出每種算法效果的差異性，定義：

式中，wk是兩種算法在種子節(jié)點(diǎn)數(shù)為k時(shí)的影響范圍差異；RECA是ECA算法的節(jié)點(diǎn)傳播影響范圍；RA是算法A的節(jié)點(diǎn)傳播影響范圍；A分別是度啟發(fā)式（2003年）、k-core啟發(fā)式（2010年）、最大度覆蓋（2010年）、最大核覆蓋（2010年）以及CCA算法（2015年）；waverage是差異百分比平均值。每種算法選取1到30個(gè)節(jié)點(diǎn)分別在IC模型中運(yùn)行50次，影響范圍結(jié)果取平均值。

4.3 結(jié)果分析

4.3.1 DBLP網(wǎng)絡(luò)上的結(jié)果分析

圖4～圖8分別展示了傳播概率 p取0.01到0.10之間5種不同值時(shí)各種算法的影響范圍情況，橫軸代表種子節(jié)點(diǎn)數(shù)k，縱軸代表節(jié)點(diǎn)影響范圍。從圖中可以看出：ECA算法在傳播概率大于等于0.03時(shí)，效果優(yōu)于其他算法；隨著種子節(jié)點(diǎn)數(shù)增大，不同算法的差別更加明顯；隨著傳播概率的增大，ECA算法的優(yōu)勢(shì)更加顯著。下面針對(duì)不同傳播概率下的算法結(jié)果走勢(shì)進(jìn)行具體分析。

當(dāng)傳播概率為0.01時(shí)，由于概率極小，除k-core算法外，其他最大化算法之間的效果差異較小。這種情況下，Degree算法表現(xiàn)出了微弱的優(yōu)勢(shì)，這是因?yàn)楫?dāng)傳播概率極小時(shí)，單個(gè)節(jié)點(diǎn)可能影響到的范圍非常有限，節(jié)點(diǎn)局部影響力發(fā)揮相對(duì)重要的作用。此時(shí)節(jié)點(diǎn)的度數(shù)基本決定了影響范圍的大小。另外，在種子節(jié)點(diǎn)數(shù)越大時(shí)，k-core算法的表現(xiàn)越差，這是由于k-core算法注重節(jié)點(diǎn)全局影響力，并且根據(jù)kcore算法選取出的核數(shù)最大的節(jié)點(diǎn)集通常聯(lián)系較為緊密，從而節(jié)點(diǎn)影響范圍存在大面積重合，導(dǎo)致算法結(jié)果較差。

Fig.4 Influence range ofp=0.01in DBLP network圖4 DBLP網(wǎng)絡(luò)中p=0.01時(shí)不同算法影響范圍

Fig.6 Influence range ofp=0.05in DBLP network圖6 DBLP網(wǎng)絡(luò)中p=0.05時(shí)不同算法影響范圍

Fig.8 Influence range ofp=0.10in DBLP network圖8 DBLP網(wǎng)絡(luò)中p=0.10時(shí)不同算法影響范圍

Fig.5 Influence range ofp=0.03in DBLP network圖5 DBLP網(wǎng)絡(luò)中p=0.03時(shí)不同算法影響范圍

Fig.7 Influence range ofp=0.07in DBLP network圖7 DBLP網(wǎng)絡(luò)中p=0.07時(shí)不同算法影響范圍

當(dāng)傳播概率為0.03時(shí)，雖然各大算法的差距并不算特別明顯，但可以看出，Degree算法的效果有了較大幅度下降，基于覆蓋類算法ECA、CCA、最大度覆蓋、最大核覆蓋的效果開(kāi)始提升。這是因?yàn)殡S著傳播概率的增大，節(jié)點(diǎn)影響力不再局限于節(jié)點(diǎn)局部度數(shù)，全局結(jié)構(gòu)信息開(kāi)始發(fā)揮作用。在種子節(jié)點(diǎn)數(shù)大于24時(shí)，ECA算法具有明顯的優(yōu)勢(shì)。

當(dāng)傳播概率為0.05時(shí)，算法之間出現(xiàn)了較為明顯的差距，特別是基于k-core的啟發(fā)式算法效果已經(jīng)無(wú)法和其他算法相提并論，這也體現(xiàn)了節(jié)點(diǎn)影響力最大化算法中去除重合范圍的重要性。ECA、CCA算法略領(lǐng)先于其他算法，兩者差距不明顯。

當(dāng)傳播概率為0.07時(shí)，ECA、CCA算法的優(yōu)勢(shì)已經(jīng)相當(dāng)明顯。特別是當(dāng)種子節(jié)點(diǎn)數(shù)越大時(shí)，ECA算法優(yōu)勢(shì)極其明顯。相對(duì)的，Degree算法效果急劇下降，在除了k-core算法的幾種算法中，結(jié)果最為不理想，說(shuō)明了隨著傳播概率的增大，節(jié)點(diǎn)影響力范圍從鄰居節(jié)點(diǎn)逐步擴(kuò)大，因此僅僅考慮節(jié)點(diǎn)度數(shù)不能恰當(dāng)評(píng)估節(jié)點(diǎn)影響力。

當(dāng)傳播概率為0.10時(shí)，ECA和CCA算法已經(jīng)和其他算法存在較大差距。種子節(jié)點(diǎn)數(shù)較少時(shí)，CCA算法表現(xiàn)優(yōu)異，但當(dāng)種子節(jié)點(diǎn)數(shù)增多時(shí)，ECA算法表現(xiàn)更為優(yōu)異且與CCA有明顯差距。

表2展示了DBLP網(wǎng)絡(luò)中ECA算法與其他算法的影響范圍平均差異百分比。從表2中可以看出，度啟發(fā)式算法隨著傳播概率的增大算法效果下降趨勢(shì)最為明顯，k-core啟發(fā)式算法效果最差，CCA算法在5種對(duì)比算法中最優(yōu)，而本文算法ECA比CCA算法更有優(yōu)勢(shì)。整體來(lái)說(shuō)，ECA算法在傳播概率大于0.03時(shí)優(yōu)勢(shì)明顯，并且隨著k值增加，ECA算法的優(yōu)化效果更加顯著。這是因?yàn)镋CA算法在去除影響范圍重合時(shí)考慮了未標(biāo)記區(qū)域邊緣節(jié)點(diǎn)影響范圍的重合問(wèn)題。因此，相比其他算法而言，選取的節(jié)點(diǎn)數(shù)越多，ECA算法在去重方面更具有優(yōu)勢(shì)，最后的優(yōu)化結(jié)果也更為明顯。

Table 2 Mean difference of influence range of ECA algorithm and other algorithms in DBLP network表2 DBLP網(wǎng)絡(luò)中ECA算法與其他算法影響范圍平均差異

Fig.9 Influence range ofp=0.01in E-mail network圖9 E-mail網(wǎng)絡(luò)中p=0.01時(shí)不同算法影響范圍

4.3.2 E-mail網(wǎng)絡(luò)上的結(jié)果分析

圖9～圖13分別展示了傳播概率取0.01到0.10之間5種不同值時(shí)各種算法的影響范圍情況。從圖中可以看出：ECA算法在傳播概率大于等于0.05時(shí)，效果優(yōu)于其他算法；隨著種子節(jié)點(diǎn)數(shù)k增大，ECA算法的優(yōu)勢(shì)更加顯著。

從前面DBLP網(wǎng)絡(luò)的結(jié)果分析可知，當(dāng)傳播概率為0.01時(shí)，由于傳播概率極小，信息很難在網(wǎng)絡(luò)中擴(kuò)散，導(dǎo)致各種算法的影響范圍較為接近。

傳播概率為0.03時(shí)，Degree算法具有相當(dāng)?shù)膬?yōu)勢(shì)，除了k-core算法，其他算法的差距較小。從E-mail網(wǎng)絡(luò)和DBLP網(wǎng)絡(luò)的基本數(shù)據(jù)可以看出，DBLP網(wǎng)絡(luò)的平均集聚系數(shù)是E-mail網(wǎng)絡(luò)的2.3倍左右。經(jīng)過(guò)仿真運(yùn)算，在DBLP網(wǎng)絡(luò)中，節(jié)點(diǎn)核數(shù)最大為23，相同核數(shù)的節(jié)點(diǎn)數(shù)量為322；在E-mail網(wǎng)絡(luò)中，節(jié)點(diǎn)核數(shù)最大為11，共有66個(gè)節(jié)點(diǎn)。從這些數(shù)據(jù)可以看出，E-mail網(wǎng)絡(luò)結(jié)構(gòu)更為疏松，因此度中心性在節(jié)點(diǎn)信息傳播影響力中發(fā)揮了非常重要的作用，這也是Degree算法在E-mail網(wǎng)絡(luò)比DBLP網(wǎng)絡(luò)表現(xiàn)更為優(yōu)越的原因。

Fig.10 Influence range ofp=0.03in E-mail network圖10 E-mail網(wǎng)絡(luò)中p=0.03時(shí)不同算法影響范圍

Fig.11 Influence range ofp=0.05in E-mail network圖11 E-mail網(wǎng)絡(luò)中p=0.05時(shí)不同算法影響范圍

Fig.12 Influence range ofp=0.07in E-mail network圖12 E-mail網(wǎng)絡(luò)中p=0.07時(shí)不同算法影響范圍

Fig.13 Influence range ofp=0.10in E-mail network圖13 E-mail網(wǎng)絡(luò)中p=0.10時(shí)不同算法影響范圍

隨著傳播概率增大到0.05，以Degree算法為代表的通過(guò)局部影響力來(lái)評(píng)估節(jié)點(diǎn)影響力的方法結(jié)果開(kāi)始變差，基于影響力覆蓋的算法開(kāi)始發(fā)揮優(yōu)勢(shì)，ECA、CCA算法目前效果較優(yōu)。

傳播概率為0.07時(shí)，ECA算法仍然存在優(yōu)勢(shì)，而Degree算法效果持續(xù)下降，但k-core算法和其他算法的差距卻逐漸縮小，比起DBLP網(wǎng)絡(luò)中k-core算法極差的表現(xiàn)，在E-mail網(wǎng)絡(luò)中其效果較好。出現(xiàn)這種現(xiàn)象的原因是對(duì)于拓?fù)浣Y(jié)構(gòu)越疏松的網(wǎng)絡(luò)，利用k-core算法選取的節(jié)點(diǎn)影響力重合范圍越小，因此算法效果比平均集聚系數(shù)大的網(wǎng)絡(luò)較優(yōu)。

當(dāng)傳播概率為0.10時(shí)，ECA較其他算法存在一定優(yōu)勢(shì)，效果優(yōu)化程度由大到小為ECA＞CCA＞最大度覆蓋＞最大核覆蓋＞Degree＞k-core。

表3展示了E-mail網(wǎng)絡(luò)中ECA算法與其他算法的影響范圍平均差異百分比，從表中可以更為清晰地看出，ECA算法在基于k-core的最大化算法中具有較大的優(yōu)勢(shì)，而Degree啟發(fā)式的效果隨著傳播概率增大明顯變差。

Table 3 Mean difference of influence range of ECA algorithm and other algorithms in E-mail network表3 E-mail網(wǎng)絡(luò)中ECA算法與其他算法影響范圍平均差異

4.3.3 ca-HepPh網(wǎng)絡(luò)上的結(jié)果分析

圖14～圖18分別展示了傳播概率取0.01到0.10之間的5種不同值時(shí)各種算法的影響范圍情況。從圖中可以看出：ECA算法在傳播概率大于等于0.01時(shí)，效果優(yōu)于其他算法；隨著種子節(jié)點(diǎn)數(shù)k和傳播概率的增大，ECA算法優(yōu)勢(shì)更加明顯。下面是針對(duì)不同傳播概率下的算法結(jié)果的具體分析。

從前面兩個(gè)網(wǎng)絡(luò)的結(jié)果分析可知，當(dāng)傳播概率取0.01時(shí)，傳播概率極小，信息在網(wǎng)絡(luò)中進(jìn)行傳播較為困難，因此各種算法之間的效果差異較小。

當(dāng)傳播概率為0.03時(shí)，各個(gè)算法的差距不大，隨著種子節(jié)點(diǎn)數(shù)量的增加，ECA算法的優(yōu)勢(shì)越來(lái)越明顯。

在傳播概率大于0.05時(shí)，基于影響力覆蓋的ECA算法與CCA算法優(yōu)勢(shì)明顯，并且隨著種子節(jié)點(diǎn)數(shù)量的增加及傳播概率的增大，ECA算法優(yōu)勢(shì)更為明顯。而僅考慮局部影響力評(píng)估節(jié)點(diǎn)影響力的Degree算法等效果較差。

表4展示了ca-HepPh網(wǎng)絡(luò)中ECA算法與其他算法的影響范圍平均差異百分比。整體來(lái)說(shuō)，ECA算法在傳播概率大于0.03時(shí)優(yōu)勢(shì)明顯，并且隨著k值增加，ECA算法的優(yōu)勢(shì)更加顯著。

Fig.14 Influence range ofp=0.01in ca-HepPh network圖14 ca-HepPh網(wǎng)絡(luò)中p=0.01時(shí)不同算法影響范圍

Fig.16 Influence range ofp=0.05in ca-HepPh network圖16 ca-HepPh網(wǎng)絡(luò)中p=0.05時(shí)不同算法影響范圍

Fig.18 Influence range ofp=0.10in ca-HepPh network圖18 ca-HepPh網(wǎng)絡(luò)中p=0.10時(shí)不同算法影響范圍

Fig.15 Influence range ofp=0.03in ca-HepPh network圖15 ca-HepPh網(wǎng)絡(luò)中p=0.03時(shí)不同算法影響范圍

Fig.17 Influence range ofp=0.07in ca-HepPh network圖17 ca-HepPh網(wǎng)絡(luò)中p=0.07時(shí)不同算法影響范圍

Table 4 Mean difference of influence range of ECA algorithm and other algorithms in ca-HepPh network表4 ca-HepPh網(wǎng)絡(luò)中ECA算法與其他算法影響范圍平均差異

在同等的硬件壞境下，DBLP網(wǎng)絡(luò)和E-mail網(wǎng)絡(luò)中Degree啟發(fā)式和最大度覆蓋的運(yùn)行時(shí)間平均在2 s以下，k-core啟發(fā)式、最大核覆蓋以及CCA算法的運(yùn)行時(shí)間在37 s左右，ECA算法為80 s左右。在數(shù)據(jù)規(guī)模較大的ca-HepPh網(wǎng)絡(luò)中，Degree啟發(fā)式和最大度覆蓋的運(yùn)行時(shí)間在100 s以下，k-core啟發(fā)式、最大核覆蓋以及CCA算法的運(yùn)行時(shí)間在4 000 s左右，ECA算法為7 000 s左右。Degree啟發(fā)式算法運(yùn)行時(shí)間較短，但其效果最差。相較于其他算法中效果最好的是CCA算法，ECA算法運(yùn)行時(shí)間略長(zhǎng)，但是ECA算法的準(zhǔn)確度優(yōu)于其他算法，其運(yùn)行時(shí)間在可被接受的范圍內(nèi)，可以看出ECA算法整體效果較優(yōu)。

通過(guò)在3種網(wǎng)絡(luò)中的影響范圍結(jié)果比較可以看出，種子節(jié)點(diǎn)越多、網(wǎng)絡(luò)規(guī)模越大時(shí)，ECA算法的效果越好。此外，p從0.01到0.10，DBLP網(wǎng)絡(luò)中節(jié)點(diǎn)影響力最大范圍依次為56，80，118，214，281；E-mail網(wǎng)絡(luò)中節(jié)點(diǎn)影響力最大范圍依次為58，119，203，325，487。在相同的傳播概率條件下，兩者差距極其明顯，E-mail網(wǎng)絡(luò)的最大范圍比DBLP網(wǎng)絡(luò)更大。由此可以得出結(jié)論，在相同初始條件下，集聚系數(shù)越大的網(wǎng)絡(luò)信息傳播范圍越小。

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

影響力最大化問(wèn)題是社會(huì)網(wǎng)絡(luò)信息傳播研究中的關(guān)鍵問(wèn)題之一，目的是發(fā)現(xiàn)網(wǎng)絡(luò)中最具有傳播影響力的節(jié)點(diǎn)，在廣告發(fā)布、輿情控制、市場(chǎng)營(yíng)銷(xiāo)等許多重要場(chǎng)景中都有廣泛的應(yīng)用。本文提出了基于IC模型的節(jié)點(diǎn)影響力最大化算法ECA，結(jié)合k-core算法及節(jié)點(diǎn)鄰近結(jié)構(gòu)信息來(lái)評(píng)估節(jié)點(diǎn)影響力，并通過(guò)去除已選節(jié)點(diǎn)影響范圍的方式來(lái)屏蔽已選區(qū)域?qū)吘壒?jié)點(diǎn)的影響，以此來(lái)除去節(jié)點(diǎn)之間的影響重合范圍。仿真結(jié)果證明ECA算法能夠增大節(jié)點(diǎn)信息傳播影響范圍，比其他算法效果更優(yōu)。

在后續(xù)研究工作中，考慮將網(wǎng)絡(luò)結(jié)構(gòu)基本數(shù)據(jù)分析與節(jié)點(diǎn)影響力最大化問(wèn)題聯(lián)系起來(lái)，根據(jù)網(wǎng)絡(luò)實(shí)際情況和初始傳播節(jié)點(diǎn)數(shù)量需求不同，實(shí)現(xiàn)算法中節(jié)點(diǎn)影響力評(píng)估方法的自適應(yīng)調(diào)整，從而在影響傳播范圍以及運(yùn)行時(shí)間優(yōu)化方面提高影響力最大化算法的性能，進(jìn)而拓展影響力最大化算法應(yīng)用領(lǐng)域。

[1]Domingos P,Richardson M.Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco,USA,Aug 26-29,2001.New York ACM,2001: 57-66.

[2]Kempe D,Kleinberg J,Tardos é.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27, 2003.New York:ACM,2003:137-146.

[3]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,USA,Aug 12-15,2007.New York:ACM,2007:420-429.

[4]Goyal A,Lu Wei,Lakshmanan L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International World Wide Web Conference,Hyderabad,India,Mar 28-Apr 1, 2011.New York:ACM,2011:47-48.

[5]Chen Wei,Wang Yajun,Yang Siyu.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,Jun 28-Jul 1,2009.New York:ACM,2009:199-208.

[6]Liu Xiaodong.Research on efficient processing techniques of influence maximization in large-scale socialnetworks[D]. Changsha:National University of Defense Technology,2013.

[7]Tian Jiatang,Wang Yitong,Feng Xiaojun.A new hybrid algorithm for influence maximization in social networks[J]. Chinese Journal of Computers,2011,34(10):1956-1965.

[8]Chen Hao,Wang Yitong.Threshold-based heuristic algorithm for influence maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.

[9]Guo Jingfeng,Lv Jiaguo.Influence maximization based on information preference[J].Journal of Computer Research and Development,2015,52(2):533-541.

[10]Guo Jing,Cao Yanan,Zhou Chuan,et al.Influence weights learning under linear threshold model in social networks[J]. Journal of Electronics and Information Technology,2014, 36(8):1804-1809.

[11]Zhang Bolei,Qian Zhuzhong,Wang Qinhui,et al.Maximize information coverage algorithm for target marke[J]. Chinese Journal of Computers,2014,37(4):894-904.

[12]Chen Wei,Wang Chi,Wang Yajun.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Jul 25-28,2010.New York:ACM,2010: 1029-1038.

[13]Chen Wei,Yuan Yifei,Zhang Li.Scalable influence maximization in social networks under the linear threshold model[C]//Proceedings of the 10th International Conference on Data Mining,Sydney,Dec 13-17,2010.Washington:IEEE Computer Society,2010:88-97.

[14]Jung K,Heo W,Chen Wei.IRIE:a scalable influence maximization algorithm for independent cascade model and its extensions[J].arXiv:1111.4795,2011.

[15]Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics, 2010,6(11):888-893.

[16]Goyal A,Lu Wei,Lakshmanan L V S.SIMPATH:an efficient algorithm for influence maximization under the linear threshold model[C]//Proceedings of the 11th International Conference on Data Mining,Vancouver,Canada,Dec 11-14, 2011.Washington:IEEE Computer Society,2011:211-220.

[17]Cao Jiuxin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social networks[J].Chinese Journal of Computers,2015,38(2):238-248.

附中文參考文獻(xiàn)：

[6]劉曉東.大規(guī)模社會(huì)網(wǎng)絡(luò)中影響最大化問(wèn)題高效處理技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2013.

[7]田家堂,王軼彤,馮小軍.一種新型的社會(huì)網(wǎng)絡(luò)影響最大化算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1956-1965.

[8]陳浩,王軼彤.基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(10):2181-2188.

[9]郭景峰,呂加國(guó).基于信息偏好的影響最大化算法研究[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):533-541.

[10]郭靜,曹亞男,周川,等.基于線性閾值模型的影響力傳播權(quán)重學(xué)習(xí)[J].電子與信息學(xué)報(bào),2014,36(8):1804-1809.

[11]張伯雷,錢(qián)柱中,王欽輝,等.面向目標(biāo)市場(chǎng)的信息最大覆蓋算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(4):894-904.

[17]曹玖新,董丹,徐順,等.一種基于k-核的社會(huì)網(wǎng)絡(luò)影響最大化算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):238-248.

HU Min was born in 1971.She received the M.S.degree from Chongqing University of Posts and Telecommunications in 2002.Now she is an associate professor and M.S.supervisor at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications.Her research interests include wireless communication,communication network system and protocol etc.

胡敏（1971—），女，重慶人，2002年于重慶郵電大學(xué)獲得碩士學(xué)位，現(xiàn)為重慶郵電大學(xué)通信與信息工程學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)闊o(wú)線通信通信，網(wǎng)體系與協(xié)議等。

SUN Xinran was born in 1991.She is an M.S.candidate at School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications.Her research interest is communication network.

孫欣然（1991—），女，河北石家莊人，重慶郵電大學(xué)通信與信息工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)橥ㄐ啪W(wǎng)絡(luò)。

HUANG Hongcheng was born in 1979.He received the M.S.degree in communication and information engineering from Chongqing University of Posts and Telecommunications in 2006.Now he is an associate professor at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,and the member of CCF.His research interests include ad hoc network and delay tolerant network,etc.

黃宏程（1979—），男，河南南陽(yáng)人，2006年于重慶郵電大學(xué)通信與信息工程專業(yè)獲得碩士學(xué)位，現(xiàn)為重慶郵電大學(xué)通信與信息工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)闊o(wú)線自組織網(wǎng)絡(luò)，容遲網(wǎng)絡(luò)等。

Edge-CoverAlgorithm for Influence Maximization in Social Network*

HU Min1,SUN Xinran1,HUANG Hongcheng1,2+
1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications, Chongqing 400065,China
2.College of Computer Science,Chongqing University,Chongqing 400044,China

+Corresponding author:E-mail:huanghc@cqupt.edu.cn

HU Min,SUN Xinran,HUANG Hongcheng.Edge-cover algorithm for influence maximization in social network.Journal of Frontiers of Computer Science and Technology,2017,11(5)：720-731.

Influence maximization is a problem of obtaining a subset of nodes in social network to maximize the influence spread.Aiming at the problem of the poor accuracy of heuristic algorithm,existing works consider the overlapped range,and ignore the problem of edge contributions.This paper focuses on how to select a seed set that has the maximum influence based on edge contributions.The algorithm evaluates the influence of information spread by calculating the global influence and adjacent influence.Then it removes the selected node influence range and updates the network to eliminate the interference of edge contributions to node influence evaluation.Finally,this paper proposes an edge-cover algorithm for influence maximization based on independent cascade model.The experimental results show that the proposed algorithm has a greater impact on the spread of range.

social network;influence maximization;edge contributions;heuristic algorithm

10.3778/j.issn.1673-9418.1605063

A

：TP391.9

*The National Natural Science Foundation of China under Grant No.61401051(國(guó)家自然科學(xué)基金);the Foundation and Frontier Research Project of Chongqing Science and Technology Commission under Grant No.cstc2014jcyjA40039(重慶市科委基礎(chǔ)和前沿研究項(xiàng)目);the Science and Technology Research Project of Chongqing Municipal Education Committee under Grant No.KJ1400402 (重慶市教委科學(xué)技術(shù)研究項(xiàng)目).

Received 2016-05,Accepted 2016-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.012.html

摘 要：影響力最大化問(wèn)題是在社交網(wǎng)絡(luò)中尋找具有最大影響范圍的節(jié)點(diǎn)集。針對(duì)啟發(fā)式算法準(zhǔn)確度相對(duì)較差的問(wèn)題，現(xiàn)有的研究考慮了影響范圍重合，但忽略了邊緣貢獻(xiàn)導(dǎo)致的節(jié)點(diǎn)影響力過(guò)量評(píng)估。重點(diǎn)研究了在考慮邊緣貢獻(xiàn)的情況下，如何選取影響范圍最大的節(jié)點(diǎn)集合。采用啟發(fā)式算法的思想，首先計(jì)算節(jié)點(diǎn)全局和鄰近影響力來(lái)評(píng)估節(jié)點(diǎn)信息傳播影響力，通過(guò)去除已選節(jié)點(diǎn)影響范圍并更新網(wǎng)絡(luò)的方式，消除邊緣貢獻(xiàn)對(duì)節(jié)點(diǎn)影響力評(píng)估的干擾，在獨(dú)立級(jí)聯(lián)模型基礎(chǔ)上提出了基于邊緣去重的節(jié)點(diǎn)影響力最大化算法。仿真結(jié)果表明所提出算法相比其他算法，能夠有效增大節(jié)點(diǎn)信息傳播影響范圍。