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

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

0 引 言

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

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

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

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

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

1.1 問題定義

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

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

(1)

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

1.2 傳播模型

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

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

(2)

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

2 算法實現(xiàn)

2.1 局部傳播中心性

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

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

(3)

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

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

基于以上闡述,節(jié)點之間的度數(shù)和傳播概率以及節(jié)點鄰居的拓撲連接對節(jié)點的擴展能力都有影響,則節(jié)點的局部傳播中心性(LPC)計算式為：

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

(8)

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

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

2.2 IMLPC

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

算法1IMLPC

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

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

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

3 實 驗

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

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

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

3.2 對比算法及實驗環(huán)境

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

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

表2 對比算法基本介紹

3.3 結果分析

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

3.3.1 影響范圍對比

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

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

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

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

3.3.2 運行時間對比

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

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

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

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

隨著種子節(jié)點數(shù)k增大,IMLPC相對于其他對比算法的影響范圍會越來越大。在大規(guī)模的douban數(shù)據(jù)集上效果更加顯著。IMLPC的運行時間與其他對比算法都十分接近,甚至會有所提升,并且IMLPC的運行時間會隨著k的不斷增加而趨于穩(wěn)定。說明該算法適用于在大規(guī)模社交網(wǎng)絡中去解決影響力最大化問題。

4 結 語

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