基于局部傳播中心性的影響力最大化算法

方 輝 姜久雷 李盛慶 李衛(wèi)民

1(北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 寧夏 銀川 750021) 2(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院 江蘇 蘇州 215500) 3(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院 上海 200444)

0 引 言

在社交網(wǎng)絡(luò)中,用戶可以通過(guò)共享新聞、圖片、視頻和產(chǎn)品促銷等信息來(lái)進(jìn)行互動(dòng)并建立聯(lián)系[1]。于是,越來(lái)越多的企業(yè)開始選擇在社交網(wǎng)絡(luò)中進(jìn)行產(chǎn)品營(yíng)銷,讓產(chǎn)品信息通過(guò)社交網(wǎng)絡(luò)傳播得更廣。例如,一家公司開發(fā)一個(gè)新產(chǎn)品,考慮到預(yù)算有限,該公司決定在產(chǎn)品銷售初期選擇一些有影響力的用戶免費(fèi)試用該產(chǎn)品,并希望這些用戶會(huì)喜歡該產(chǎn)品,然后這些用戶會(huì)推薦新產(chǎn)品給他們的朋友,而那些受影響的朋友很可能會(huì)影響他們的朋友。最終,該公司就可以擁有許多潛在客戶。從形式上來(lái)講,上述情況就稱為“影響力最大化”問(wèn)題,即在大規(guī)模社交網(wǎng)絡(luò)中挖掘一個(gè)較小的節(jié)點(diǎn)集合,使得該集合在社交網(wǎng)絡(luò)的影響范圍更大。

在社交網(wǎng)絡(luò)中,經(jīng)典的影響力的度量方法有DegreeCentrality、EigenvectorCemtrality、K-shell和ClosenessCentrality[2-5]等。除此之外,Chen等[6]利用節(jié)點(diǎn)的鄰居和下一個(gè)最近的鄰居提出LC(Local Centrality)度量節(jié)點(diǎn)的影響力。Gao等[7]在LC的基礎(chǔ)上,加入聚類系數(shù)提出LSC(Local Structure Centrality)度量節(jié)點(diǎn)影響力。Yang等[8]綜合考慮節(jié)點(diǎn)度和兩跳鄰居的聚類系數(shù),通過(guò)熵計(jì)算度和聚類系數(shù)所占權(quán)重,提出DCC度量節(jié)點(diǎn)的影響力。實(shí)驗(yàn)結(jié)果表明,LC、LSC和DCC更能區(qū)分不同節(jié)點(diǎn)的影響力。本文針對(duì)上述度量方法未考慮傳播概率對(duì)節(jié)點(diǎn)擴(kuò)展能力的影響,提出一種LPC度量方法。

影響力最大化問(wèn)題首先是由Domingos等[9]提出的,并將其定義為一個(gè)算法問(wèn)題。Kempe等[10-11]形式化地表示了影響力最大化問(wèn)題,然后提出了影響范圍達(dá)到為1-1/e(63%)的貪心爬山算法對(duì)該問(wèn)題進(jìn)行求解,并證明了影響力最大化問(wèn)題是NP-hard問(wèn)題。利用貪心算法求解需要運(yùn)用多次蒙特卡羅(Monte-Carlo)模擬,導(dǎo)致算法非常耗時(shí)。為了減少算法的運(yùn)行時(shí)間,許多學(xué)者提出了啟發(fā)式算法。Chen等[12]提出DegreeDiscount算法,該算法的基本思想是當(dāng)一個(gè)節(jié)點(diǎn)有鄰居節(jié)點(diǎn)被選為種子節(jié)點(diǎn)時(shí),在計(jì)算它的度數(shù)時(shí)要減少,其性能優(yōu)于Degree算法[10]。Deng等[13]在IC模型的基礎(chǔ)上,利用節(jié)點(diǎn)的中心性計(jì)算網(wǎng)絡(luò)中每條邊的傳播概率,提出了基于中心性的獨(dú)立級(jí)聯(lián)模(Centrality-Based Independent Cascade Model, CIC),在DegreeDiscount[12]算法基礎(chǔ)上提出NewDiscount算法,實(shí)驗(yàn)結(jié)果表明,NewDiscount算法比DegreeDiscount算法影響范圍更廣。Kundu等[14]基于傳播概率和度中心性提出了基于傳播度(diffusion degree)的啟發(fā)式算法。因?yàn)樵撍惴紤]到了節(jié)點(diǎn)間傳播概率的影響,從而提高了算法的準(zhǔn)確性。Li等[15]提出了三跳速度衰減傳播模型(The three hops velocity attenuation propagation model),通過(guò)該模型為每個(gè)節(jié)點(diǎn)構(gòu)造一個(gè)三跳傳播路徑,并提出了IMMRA,實(shí)驗(yàn)結(jié)果表明,該算法的影響范圍與貪心算法十分接近,且運(yùn)行時(shí)間有很大提升。Dey等[16]通過(guò)5種不同的中心性度量方法選擇用于信息傳播的種子節(jié)點(diǎn),通過(guò)在不同數(shù)據(jù)集中使用Susceptible-Infected-Recovered(SIR)和Breadth First Search(BFS)模擬信息傳播,最終通過(guò)比較受種子節(jié)點(diǎn)影響的節(jié)點(diǎn)數(shù)量發(fā)現(xiàn),特征向量中心性優(yōu)于其他中心性度量。但是考慮到特征向量中心性時(shí)間復(fù)雜度高,作者利用k-core將原始網(wǎng)絡(luò)退化為較小的網(wǎng)絡(luò),然后選擇種子節(jié)點(diǎn),進(jìn)一步減少了算法的運(yùn)行時(shí)間。

對(duì)于影響力最大化問(wèn)題,基于貪心策略能保證算法的精度較高但算法時(shí)間復(fù)雜度高,而啟發(fā)式算法時(shí)間復(fù)雜度低但影響范圍不如貪心算法。針對(duì)該問(wèn)題,本文提出一種時(shí)間復(fù)雜度低且影響范圍更大的IMLPC。

1 影響力最大化與傳播模型

1.1 問(wèn)題定義

在本文中,將社交網(wǎng)絡(luò)建模為圖,給定一個(gè)圖G(V,E),其中:V表示節(jié)點(diǎn)集合;E表示邊集。?v∈V表示節(jié)點(diǎn),?e(u,v)∈E表示一條u指向v的邊。

影響力最大化問(wèn)題的目的就是找到有k個(gè)節(jié)點(diǎn)的種子集S(S=|k|),且S?V,使得在某種信息傳播模型下被S影響的節(jié)點(diǎn)的預(yù)期數(shù)量σ(S)最大化。即選擇k個(gè)可以使σ(S)達(dá)到最大值的種子節(jié)點(diǎn)。其表示如下：

(1)

式中：S*是選擇的初始種子集合。

1.2 傳播模型

本文采用獨(dú)立級(jí)聯(lián)(Independent Cascade, IC)模型模擬影響力的傳播過(guò)程。在IC模型中,為每條邊e(u,v)∈E指定了傳播概率puv∈[0,1],這是u通過(guò)邊影響v的概率。

給定網(wǎng)絡(luò)圖G(V,E)和種子集S?V,IC模型中節(jié)點(diǎn)有兩種狀態(tài),即激活狀態(tài)和未激活狀態(tài)。IC模型傳播過(guò)程如下。令S0=S,首先,S0中的所有節(jié)點(diǎn)都處于激活狀態(tài),而其他節(jié)點(diǎn)則處于未激活狀態(tài)。在每個(gè)時(shí)間t,每個(gè)節(jié)點(diǎn)u∈St-1都有且僅有一次機(jī)會(huì)以傳播概率puv影響其每個(gè)處于未激活狀態(tài)的鄰居v。如果v受影響,則將其添加到St并使v處于激活狀態(tài)。當(dāng)St為空時(shí),該過(guò)程結(jié)束。令A(yù)S(S)表示最終受S影響的輸出節(jié)點(diǎn)數(shù)目。因此,σ(S)表示如下：

(2)

式中：S是最初選擇的種子集；ASi(S)是第i次傳播過(guò)程中影響的節(jié)點(diǎn)數(shù)目;R是IC模型的模擬次數(shù)。

2 算法實(shí)現(xiàn)

2.1 局部傳播中心性

在社會(huì)學(xué)文獻(xiàn)中,度和其他基于度中心性的啟發(fā)式算法通常用于評(píng)估社交網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力[1,17]。節(jié)點(diǎn)的度也常被作為影響力最大化問(wèn)題中種子節(jié)點(diǎn)的選擇依據(jù)。盡管選擇最大度數(shù)的節(jié)點(diǎn)作為種子會(huì)有更大的影響力擴(kuò)散,但卻未考慮到種子節(jié)點(diǎn)的實(shí)際傳播過(guò)程[14]。假設(shè)網(wǎng)絡(luò)中具有最大度數(shù)的節(jié)點(diǎn)V1與一些度數(shù)較小的節(jié)點(diǎn)相連,而另一個(gè)度數(shù)較小的節(jié)點(diǎn)V2與一些度數(shù)較大的節(jié)點(diǎn)相連。在這種情況下,我們就不能單純地選擇V1作為種子節(jié)點(diǎn),因?yàn)榕cV1的鄰居相比,V2的鄰居可以將信息發(fā)送給網(wǎng)絡(luò)中更多的節(jié)點(diǎn),V1在信息傳播過(guò)程中影響范圍反而更小。這是因?yàn)槲纯紤]節(jié)點(diǎn)鄰域的影響。

因此本文引入傳播概率來(lái)量化節(jié)點(diǎn)的實(shí)際傳播過(guò)程,并用傳播概率與度數(shù)的乘積表示節(jié)點(diǎn)的直接影響力,其計(jì)算式為：

(3)

式中：deg(u)表示節(jié)點(diǎn)u的度數(shù)；puv是u通過(guò)邊影響v的概率；neighbors(u)表示節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合。

式(3)中我們考慮了傳播概率對(duì)節(jié)點(diǎn)影響力的影響。需要注意的是,在真實(shí)的社交網(wǎng)絡(luò)中,節(jié)點(diǎn)之間的傳播概率并不是固定值,而是在區(qū)間[0,1]內(nèi)變化的。同時(shí),文獻(xiàn)[18]也證明了傳播概率在等于區(qū)間的右邊界或左邊界時(shí),傳播模型將達(dá)到最差的性能。

考慮到具有高中心性的節(jié)點(diǎn)更容易影響到具有低中心性的節(jié)點(diǎn),本文使用網(wǎng)絡(luò)中每條邊的兩個(gè)節(jié)點(diǎn)的中心性去計(jì)算傳播概率p[13]。節(jié)點(diǎn)u影響v的概率為：

(4)

Eu和Ev的值本文分別采用節(jié)點(diǎn)u和v的特征向量中心性來(lái)計(jì)算,其計(jì)算式為：

(5)

式中：λ表示鄰接矩陣的最大特征值；xi是節(jié)點(diǎn)；ai,j是節(jié)點(diǎn)xi、xj之間的權(quán)重,特征向量中心性是根據(jù)節(jié)點(diǎn)的中心性計(jì)算它們的權(quán)重,然后將與當(dāng)前節(jié)點(diǎn)可達(dá)的其他節(jié)點(diǎn)的權(quán)重的線性和視為該節(jié)點(diǎn)的中心性值[19]。

同時(shí),節(jié)點(diǎn)鄰居的拓?fù)溥B接對(duì)節(jié)點(diǎn)的影響力度量也是有影響的,對(duì)于中心性相同的節(jié)點(diǎn),若其鄰居密度較高,則有更多的相互影響的機(jī)會(huì),因此鄰居密度較高的節(jié)點(diǎn)會(huì)具有更強(qiáng)的擴(kuò)展能力[7]。另外,考慮到全局度量的計(jì)算復(fù)雜度高,將其應(yīng)用于大規(guī)模社交網(wǎng)絡(luò)時(shí)間復(fù)雜度高,因此用節(jié)點(diǎn)的局部聚類系數(shù)度量鄰居之間的拓?fù)溥B接,并將其表示為節(jié)點(diǎn)的間接影響力,其計(jì)算式為：

(6)

式中：cv表示節(jié)點(diǎn)v的聚類系數(shù)。局部聚類系數(shù)等于節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)之間連邊的數(shù)量與鄰居節(jié)點(diǎn)之間可達(dá)連邊的最大數(shù)量之比[20]，其計(jì)算式為：

(7)

式中：Nv為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合；deg(v)是節(jié)點(diǎn)v的度數(shù)。

基于以上闡述,節(jié)點(diǎn)之間的度數(shù)和傳播概率以及節(jié)點(diǎn)鄰居的拓?fù)溥B接對(duì)節(jié)點(diǎn)的擴(kuò)展能力都有影響,則節(jié)點(diǎn)的局部傳播中心性(LPC)計(jì)算式為：

C(u)=C1(u)+C2(u)=

(8)

式中：C1(u)表示度量節(jié)點(diǎn)的直接影響力；C2(u)表示度量節(jié)點(diǎn)的間接影響力；deg(u)表示節(jié)點(diǎn)u的度數(shù)；cv表示節(jié)點(diǎn)v的聚類系數(shù)；puv是u通過(guò)邊影響v的概率。

局部傳播中心性(LPC)的核心思想如下所述。首先用傳播概率量化節(jié)點(diǎn)的實(shí)際傳播過(guò)程, 用節(jié)點(diǎn)的度數(shù)與傳播概率的乘積表示當(dāng)前節(jié)點(diǎn)的直接影響力,其次用聚類系數(shù)度量當(dāng)前節(jié)點(diǎn)鄰居的拓?fù)溥B接,并表示對(duì)節(jié)點(diǎn)的間接影響力。最終,節(jié)點(diǎn)的影響力就是直接影響力與間接影響力的求和。

2.2 IMLPC

度和其他基于度中心性的啟發(fā)式算法常用于解決影響力最大化問(wèn)題,但是其影響范圍有限。因此本文利用局部傳播中心性(LPC)衡量每個(gè)節(jié)點(diǎn)的擴(kuò)展能力,并提出IMLPC,該算法的種子節(jié)點(diǎn)選擇依賴于每個(gè)節(jié)點(diǎn)的局部傳播中心性(LPC)計(jì)算結(jié)果。在選擇網(wǎng)絡(luò)中的k個(gè)節(jié)點(diǎn)構(gòu)成種子集S時(shí),選擇當(dāng)前迭代中局部傳播中心性(LPC)最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。

算法1IMLPC

輸入：社交網(wǎng)絡(luò)G(V,E),傳播概率P,節(jié)點(diǎn)聚類系數(shù)C,種子集大小k。

輸出：種子節(jié)點(diǎn)集合S。

1．InitializeS=?

2．For each nodeudo

3． Calculate its degreedu；

4．lpcu=du；

5．End For

6．Fori=1 tok

7． Selectu=argmaxu{lpcu|u∈VS}；

8．S=S∪{u}；

9. For each neighborvofuandu,v∈VS,puv∈P,cv∈C,do

11． End For

12．End For

13．Output S

在IMPLC中,算法的輸入為圖G(V,E),種子節(jié)點(diǎn)數(shù)k,由式(4)計(jì)算得到節(jié)點(diǎn)之間傳播概率P,以及由式(7)計(jì)算得到的每個(gè)節(jié)點(diǎn)的聚類系數(shù)C,輸出為最終選擇的種子集S。算法第1行初始化種子集S為空。第2-第5行,計(jì)算所有節(jié)點(diǎn)的度數(shù),并讓每個(gè)節(jié)點(diǎn)的局部傳播中心性(LPC)等于其度數(shù)。第6-第12行,由式(8)計(jì)算每次循環(huán)中節(jié)點(diǎn)的局部傳播中心性并將計(jì)算結(jié)果最大的節(jié)點(diǎn)添加到種子集S中。第13行,輸出種子集,算法結(jié)束。

算法1利用啟發(fā)式策略,選擇局部傳播中心性最大的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn),因此可以保證算法運(yùn)行時(shí)間,同時(shí)選擇種子節(jié)點(diǎn)時(shí)考慮了傳播概率,算法的精度也有所提高。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集介紹

由于本文討論在線社交網(wǎng)絡(luò),因此實(shí)驗(yàn)中用到的所有數(shù)據(jù)集都是從在線社交網(wǎng)絡(luò)收集的。為了解決影響傳播模型中的噪聲問(wèn)題,選擇兩種不同規(guī)模的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。MIT數(shù)據(jù)集是從在線社交網(wǎng)站Facebook收集的數(shù)據(jù)集,包含在麻省理工學(xué)院學(xué)習(xí)的Facebook用戶,該數(shù)據(jù)集中用戶之間的聯(lián)系比較緊密。douban數(shù)據(jù)集是由LongQiu (lqiu4@asu.edu)從豆瓣網(wǎng)站(Douban.com)爬取的友誼網(wǎng)絡(luò)。詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集介紹

3.2 對(duì)比算法及實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)運(yùn)行環(huán)境為：CPU為3.40 GHz Inter Core i7,內(nèi)存10 GB,操作系統(tǒng)為Windows 10,本文算法使用Python語(yǔ)言編程實(shí)現(xiàn)。

本文采用IC模型模擬種子集的影響范圍,采用蒙特卡羅(Monte-Carlo)模擬了1 000次實(shí)驗(yàn),然后得到影響范圍的平均值。為驗(yàn)證IMLPC的性能,與其他算法進(jìn)行實(shí)驗(yàn)對(duì)比,對(duì)比算法如表2所示。

表2 對(duì)比算法基本介紹

3.3 結(jié)果分析

本文主要從種子集的影響范圍和算法的運(yùn)行時(shí)間兩方面衡量算法的性能，對(duì)IMLPC和四個(gè)對(duì)比算法在兩種不同的數(shù)據(jù)集上進(jìn)行評(píng)估。

3.3.1 影響范圍對(duì)比

圖1和圖2分別描述了本文提出的IMLPC以及DegreeDiscount、Degree、EigenvectorCentrality和NewDiscount四個(gè)對(duì)比算法在MIT和douban數(shù)據(jù)集上的種子集影響范圍。

圖1 不同算法在MIT數(shù)據(jù)集上的影響范圍

圖2 不同算法在douban數(shù)據(jù)集上的影響范圍

通過(guò)比較不同數(shù)據(jù)集上的影響范圍,可以發(fā)現(xiàn)EigenvectorCentrality的影響范圍較低。例如,當(dāng)k=10時(shí),其影響范圍在MIT和douban數(shù)據(jù)集上分別低于IMLPC15.6%和14.8%。本文提出的IMLPC在兩種數(shù)據(jù)集上的影響范圍明顯優(yōu)于其他算法,這也表明傳播概率和節(jié)點(diǎn)拓?fù)溥B接對(duì)節(jié)點(diǎn)影響力的度量有很重要的作用,例如在douban數(shù)據(jù)集上,當(dāng)k=40時(shí),IMLPC的影響范圍較DegreeDiscount、Degree、EigenvectorCentrality和NewDicount算法分別提高10.9%、10.7%、21.6%和3.9%。在MIT數(shù)據(jù)集上;當(dāng)k=40時(shí),IMLPC的影響范圍較DegreeDiscount、Degree、Eigenvector Centrality和NewDicount算法分別提高14.3%、14.3%、37.4%和3.9%。雖然在MIT數(shù)據(jù)集上,IMLPC在k=20時(shí)影響范圍略微低于NewDicount算法,但在整體上仍然較好,因?yàn)樵趯?shí)驗(yàn)中當(dāng)k>24時(shí),IMLPC的影響范圍會(huì)高于NewDiscount算法,并且在此之后,IMLPC都優(yōu)于NewDiscount算法。綜上所述,IMLPC的影響范圍是優(yōu)于其他啟發(fā)式算法的,該算法適用于大規(guī)模社交網(wǎng)絡(luò)。

3.3.2 運(yùn)行時(shí)間對(duì)比

算法的運(yùn)行時(shí)間同樣是衡量算法性能的一個(gè)因素,算法的運(yùn)行時(shí)間會(huì)因?yàn)椴煌瑪?shù)據(jù)集的特征而有所不同。圖3和圖4分別描述了種子節(jié)點(diǎn)數(shù)k=10、30和50時(shí),IMLPC和其他4個(gè)對(duì)比算法在MIT和douban數(shù)據(jù)集上的運(yùn)行時(shí)間。

圖3 不同算法在MIT數(shù)據(jù)集上的運(yùn)行時(shí)間

圖4 不同算法在douban數(shù)據(jù)集上的運(yùn)行時(shí)間

可以看出,IMLPC算法與EigenvectorCentrality和NewDiscount算法相比,在不同數(shù)據(jù)集上的運(yùn)行時(shí)間都有所提高。例如在規(guī)模最大的douban數(shù)據(jù)集上,k=30時(shí),IMLPC的運(yùn)行時(shí)間較Eigenvector Centrality、NewDiscount算法相比分別提高了8.8%、3.1%；k=50時(shí),分別提高了11.3%和3.1%。IMLPC與DegreDiscount和Degree算法相比,在MIT數(shù)據(jù)集上的運(yùn)行時(shí)間接近；在douban數(shù)據(jù)集上的運(yùn)行時(shí)間相差在0.3 s,可能的原因是douban數(shù)據(jù)規(guī)模更大,IMLPC在度量節(jié)點(diǎn)的影響力時(shí),需要多次對(duì)節(jié)點(diǎn)鄰居的聚類系數(shù)進(jìn)行累加運(yùn)算,導(dǎo)致運(yùn)行時(shí)間稍長(zhǎng)。但是,IMLPC在douban數(shù)據(jù)集上的影響范圍是明顯優(yōu)于DegreeDiscout和Degree算法的,所以相差的運(yùn)行時(shí)間仍在可接受范圍內(nèi)。

隨著種子節(jié)點(diǎn)數(shù)k增大,IMLPC相對(duì)于其他對(duì)比算法的影響范圍會(huì)越來(lái)越大。在大規(guī)模的douban數(shù)據(jù)集上效果更加顯著。IMLPC的運(yùn)行時(shí)間與其他對(duì)比算法都十分接近,甚至?xí)兴嵘?并且IMLPC的運(yùn)行時(shí)間會(huì)隨著k的不斷增加而趨于穩(wěn)定。說(shuō)明該算法適用于在大規(guī)模社交網(wǎng)絡(luò)中去解決影響力最大化問(wèn)題。

4 結(jié) 語(yǔ)

本文針對(duì)度中心性等方法選擇種子節(jié)點(diǎn)時(shí)未考慮節(jié)點(diǎn)間傳播概率及鄰居拓?fù)溥B接的影響,提出LPC方法度量節(jié)點(diǎn)影響力,該方法用傳播概率量化節(jié)點(diǎn)的實(shí)際傳播過(guò)程,同時(shí)用節(jié)點(diǎn)鄰居的拓?fù)溥B接度量節(jié)點(diǎn)的間接影響力。然后提出基于局部傳播中心性的影響力最大化算法(IMLPC)。實(shí)驗(yàn)結(jié)果表明,IMLPC在IC模型上的影響范圍相對(duì)比現(xiàn)有啟發(fā)式算法有顯著提升,且算法的運(yùn)行時(shí)間也有所改進(jìn),驗(yàn)證了算法的有效性和可行性。未來(lái)考慮使用除節(jié)點(diǎn)的屬性外的知識(shí)(如機(jī)器學(xué)習(xí)等)更加準(zhǔn)確地量化節(jié)點(diǎn)間的傳播概率,并減少傳播模型的隨機(jī)性。