韓 婷，周麗華*，黃亞群，姜懿庭

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650504；

2.云南師范大學(xué) 信息學(xué)院，云南 昆明 650500)

0 引 言

隨著各種各樣社交網(wǎng)絡(luò)的出現(xiàn)，人與人之間的聯(lián)系越來(lái)越緊密，人們的學(xué)習(xí)、工作和生活正在不斷地被改變。社交網(wǎng)絡(luò)中信息的傳播和影響力無(wú)處不在，通過(guò)社交網(wǎng)絡(luò)，具有高影響力的名人可以影響他人的看法和行為。準(zhǔn)確度量不同對(duì)象之間的影響力，有助于識(shí)別社交網(wǎng)絡(luò)中最具影響力的對(duì)象并促進(jìn)信息的快速傳播，對(duì)謠言傳播、流行病傳播、產(chǎn)品營(yíng)銷(xiāo)以及推薦系統(tǒng)等工作起著至關(guān)重要的作用[1-3]，因此影響力最大化研究受到了研究人員的極大關(guān)注。

影響力最大化問(wèn)題被認(rèn)為是對(duì)病毒營(yíng)銷(xiāo)的一個(gè)直接數(shù)學(xué)刻畫(huà)。其目的就是希望利用病毒式營(yíng)銷(xiāo)手段，在社交網(wǎng)絡(luò)找到少數(shù)重要的節(jié)點(diǎn)作為種子集，利用這些種子集進(jìn)行信息的傳播從而達(dá)到在社交網(wǎng)絡(luò)中影響力的最大化[4]。目前，傳統(tǒng)的影響力最大化方法有基于中心度、PageRank、特征向量和啟發(fā)式算法等，其中PageRank[5]是一種重要的算法，該算法最初是Google公司為了衡量網(wǎng)頁(yè)等級(jí)和重要性而提出的，它從網(wǎng)頁(yè)數(shù)量和質(zhì)量綜合考慮了頁(yè)面的重要性，能較好地刻畫(huà)頁(yè)面的性質(zhì)，并描述對(duì)象之間的關(guān)系。這些傳統(tǒng)的算法在同質(zhì)信息網(wǎng)絡(luò)中取得了較好的結(jié)果，但是同質(zhì)信息網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈接關(guān)系類(lèi)型單一，沒(méi)有區(qū)分對(duì)象及其關(guān)系的異質(zhì)性[6]，這與實(shí)際的現(xiàn)實(shí)網(wǎng)絡(luò)不符?，F(xiàn)實(shí)中的網(wǎng)絡(luò)大多是異質(zhì)信息網(wǎng)絡(luò)，包含了多種類(lèi)型的對(duì)象及多種關(guān)聯(lián)類(lèi)型的鏈接關(guān)系[7-8]，網(wǎng)絡(luò)中的一個(gè)實(shí)體對(duì)象的影響力不僅受到同種類(lèi)型對(duì)象的影響，還與其他類(lèi)型對(duì)象有關(guān)。由此關(guān)于影響力最大化問(wèn)題的研究正逐步從同質(zhì)信息網(wǎng)絡(luò)轉(zhuǎn)向異質(zhì)信息網(wǎng)絡(luò)。

異質(zhì)信息網(wǎng)絡(luò)包含了多種類(lèi)型的對(duì)象及鏈接關(guān)系，相對(duì)于同質(zhì)信息網(wǎng)絡(luò)，節(jié)點(diǎn)和鏈接類(lèi)型、語(yǔ)義關(guān)系更為豐富[8]，這些豐富的信息可以更全面地評(píng)價(jià)節(jié)點(diǎn)的影響力。如圖1所示的文獻(xiàn)信息網(wǎng)絡(luò)DBLP就是典型的異質(zhì)信息網(wǎng)絡(luò)，它包含了四種類(lèi)型的節(jié)點(diǎn)：A(作者)、P(文章)、C(會(huì)議)和T(主題)，六種關(guān)系：A-P(編寫(xiě)/被編寫(xiě)),P-C(發(fā)表/被發(fā)表),P-T(包含/被包含)。評(píng)價(jià)一個(gè)作者的影響力不僅要從作者發(fā)表的文章數(shù)量和質(zhì)量來(lái)衡量，還要從他撰寫(xiě)的文章的內(nèi)容主題、所屬會(huì)議以及與他合作的作者等方面考慮，通過(guò)融合這些豐富的信息能更好地刻畫(huà)現(xiàn)實(shí)網(wǎng)絡(luò)中不同節(jié)點(diǎn)對(duì)象之間的影響力情況。

圖1 DBLP網(wǎng)絡(luò)

由于異質(zhì)信息網(wǎng)絡(luò)包含了多種類(lèi)型的對(duì)象及鏈接關(guān)系，并且網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，各節(jié)點(diǎn)之間不是相互獨(dú)立的，他們通過(guò)各種關(guān)系相互影響。如何有效地利用不同類(lèi)型對(duì)象間的關(guān)系成為異質(zhì)信息網(wǎng)絡(luò)分析的一個(gè)難點(diǎn)。Zhao等人[9]對(duì)異質(zhì)信息網(wǎng)絡(luò)中兩種不同類(lèi)型的節(jié)點(diǎn)使用PageRank，保留了節(jié)點(diǎn)間的連接關(guān)系，更好地考慮到不同類(lèi)型節(jié)點(diǎn)彼此間的影響。但是他們只考慮了直接相連的兩種類(lèi)型節(jié)點(diǎn)，忽略了異質(zhì)網(wǎng)絡(luò)中同種類(lèi)型節(jié)點(diǎn)和其他非直接相連的不同類(lèi)型節(jié)點(diǎn)的影響，同時(shí)他們還將所有節(jié)點(diǎn)之間的初始連接關(guān)系的權(quán)重視為相同。然而，現(xiàn)實(shí)中并非所有節(jié)點(diǎn)間的連接關(guān)系都是同等重要的，為了能進(jìn)一步區(qū)分連接關(guān)系的重要性并考慮到所有類(lèi)型節(jié)點(diǎn)間的影響，該文針對(duì)異質(zhì)信息網(wǎng)絡(luò)提出了一種基于加權(quán)PageRank的影響力最大化算法(Comprehensive Weighted PageRank，CWPR)。CWPR根據(jù)不同節(jié)點(diǎn)之間的連接關(guān)系賦予對(duì)應(yīng)的權(quán)重，這樣可以更全面地考慮節(jié)點(diǎn)的重要性。

主要工作如下：

(1)將異質(zhì)信息網(wǎng)絡(luò)分解為若干個(gè)只含一種連接類(lèi)型的網(wǎng)絡(luò)，再根據(jù)各節(jié)點(diǎn)之間連接關(guān)系的次數(shù)分配對(duì)應(yīng)的權(quán)重。網(wǎng)絡(luò)的分解簡(jiǎn)化了復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，權(quán)重的分配區(qū)分了節(jié)點(diǎn)間連接關(guān)系的重要性，有助于準(zhǔn)確度量不同節(jié)點(diǎn)之間的影響力。

(2)提出了一種基于加權(quán)PageRank的影響力最大化算法CWPR，其中影響力的度量考慮了不同類(lèi)型節(jié)點(diǎn)的直接影響和間接影響，從而更好地描述了節(jié)點(diǎn)影響力的復(fù)雜性和異質(zhì)性，全面保留了異質(zhì)信息網(wǎng)絡(luò)中的信息，使找到的種子節(jié)點(diǎn)具有較高的影響力。

(3)在DBLP和Yelp兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，通過(guò)與其他同質(zhì)和異質(zhì)影響力最大化算法的對(duì)比，驗(yàn)證了CWPR的合理性和準(zhǔn)確性。同時(shí)討論了參數(shù)和邊權(quán)重對(duì)于算法性能的影響。

1 相關(guān)工作

Kempe等人[10]首次將影響力最大化問(wèn)題表示成離散的優(yōu)化問(wèn)題，證明了該問(wèn)題是一個(gè)NP-hard問(wèn)題，并基于單調(diào)次模性提出了有效的貪心算法。該算法能得到最優(yōu)解，但是不能改進(jìn)算法的時(shí)間復(fù)雜度。后來(lái)Leskovec等人[11]提出了CELF算法，CELF算法在實(shí)驗(yàn)中的效率得到了很大的提升。隨著對(duì)影響力最大化問(wèn)題研究的進(jìn)一步深入，相關(guān)工作也越來(lái)越多，Goyal等人[12]又進(jìn)一步改進(jìn)了CELF算法，提出CELF++算法。當(dāng)問(wèn)題規(guī)模較大時(shí)，CELF++算法并不適用，于是Chen等人[13-15]又提出了DegreeDiscount、PMIA、LDAG等算法，大大提高了運(yùn)算速度。周明洋等人[16]從多節(jié)點(diǎn)的綜合影響力角度出發(fā),基于Rayleigh熵機(jī)制,提出了一種指標(biāo)刻畫(huà)多節(jié)點(diǎn)的綜合影響力算法。曹玖新等人[17]基于用戶(hù)交互的主題偏好計(jì)算不同類(lèi)別信息下節(jié)點(diǎn)間的影響概率,并結(jié)合擴(kuò)展的傳播模型和信息擴(kuò)散的特點(diǎn),提出基于節(jié)點(diǎn)子圖的影響力計(jì)算算法。楊書(shū)新等人[18]基于三度影響力原則,綜合考慮局部度量的適宜層次及大規(guī)模網(wǎng)絡(luò)的可擴(kuò)展性,提出一種基于3級(jí)鄰居的節(jié)點(diǎn)影響力度量算法。Oriedi等人[19]提出選擇性廣度優(yōu)先遍歷算法，對(duì)來(lái)自社交網(wǎng)絡(luò)成員之間實(shí)際社交行為進(jìn)行影響力建模，有效地生成影響最大化的最佳種子集。目前從運(yùn)算效率、網(wǎng)絡(luò)結(jié)構(gòu)等方面對(duì)影響力最大化問(wèn)題的研究工作越來(lái)越多，影響力最大化問(wèn)題也正逐步從同質(zhì)信息網(wǎng)絡(luò)轉(zhuǎn)向異質(zhì)信息網(wǎng)絡(luò)。

在異質(zhì)信息網(wǎng)絡(luò)中，Deng等人[20]設(shè)計(jì)了一個(gè)基于互動(dòng)記錄、社交友誼、標(biāo)簽和話(huà)題的MIF模型來(lái)衡量用戶(hù)之間的社交影響力，還有基于同元路徑考慮信息熵[21-22]來(lái)定位有影響力的節(jié)點(diǎn)等。Keikhar和Rahgoza等人[23]利用深度學(xué)習(xí)技術(shù)獲得異質(zhì)信息網(wǎng)絡(luò)節(jié)點(diǎn)的特征，根據(jù)節(jié)點(diǎn)的本地和全局結(jié)構(gòu)特性得到最具影響力的節(jié)點(diǎn)。然而，由于異質(zhì)信息網(wǎng)絡(luò)相對(duì)于同質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)、性質(zhì)更為復(fù)雜，目前對(duì)于異質(zhì)信息網(wǎng)絡(luò)影響力最大化的研究還未足夠成熟，因此在異質(zhì)信息網(wǎng)絡(luò)中對(duì)于影響力最大化的研究還存在很大的進(jìn)步空間。

2 相關(guān)概念及問(wèn)題定義

該文的主要目的是利用加權(quán)PageRank綜合考慮各種類(lèi)型節(jié)點(diǎn)之間的影響關(guān)系，從而挖掘出異質(zhì)信息網(wǎng)絡(luò)中影響力最大的節(jié)點(diǎn)。本節(jié)主要介紹所涉及到的一些相關(guān)概念及問(wèn)題定義。

2.1 相關(guān)概念

定義1 異質(zhì)信息網(wǎng)絡(luò)[7,24]：信息網(wǎng)絡(luò)由一個(gè)帶有對(duì)象類(lèi)型的映射函數(shù)τ:V→A和關(guān)系類(lèi)型映射函數(shù)φ:E→R的有向圖G=(V,E,τ,φ)組成，其中V={v1,v2,…,vn}是對(duì)象集合，它屬于對(duì)象類(lèi)型集合A的某一個(gè)特定對(duì)象類(lèi)型集合，E={e1,e2,…,en}是對(duì)象之間的鏈接集合，屬于關(guān)系類(lèi)型集合R的某一個(gè)特定關(guān)系類(lèi)型集合，當(dāng)信息網(wǎng)絡(luò)中的對(duì)象類(lèi)型數(shù)|A|或者關(guān)系類(lèi)型數(shù)|R|大于1時(shí)，稱(chēng)這個(gè)信息網(wǎng)絡(luò)為異質(zhì)信息網(wǎng)絡(luò)。

定義2 網(wǎng)絡(luò)模式[7,24]：網(wǎng)絡(luò)模式是定義在對(duì)象類(lèi)型A上的有向圖，它的邊為R中的關(guān)系，記為T(mén)G=(A,R)，表示信息網(wǎng)絡(luò)的元模式。

定義4 加權(quán)PageRank[25]：根據(jù)信息網(wǎng)絡(luò)中對(duì)象的連接結(jié)構(gòu)及連接頻次對(duì)每個(gè)對(duì)象的質(zhì)量進(jìn)行排名，進(jìn)而利用鏈接和對(duì)象質(zhì)量排名來(lái)衡量整個(gè)網(wǎng)絡(luò)對(duì)象的重要性。其重要性的表示如下。

(1)

2.2 問(wèn)題定義

S*=argmaxS0σ(S0)

(2)

3 CWPR算法

該文提出了一種基于加權(quán)PageRank的影響力最大化算法(CWPR)，用于解決異質(zhì)信息網(wǎng)絡(luò)中的影響力最大化問(wèn)題。該算法包含兩個(gè)步驟。第一，首先將原始異質(zhì)信息網(wǎng)絡(luò)分解成若干個(gè)只含一種連接類(lèi)型的網(wǎng)絡(luò)，并根據(jù)節(jié)點(diǎn)間的連接關(guān)系分配對(duì)應(yīng)的邊權(quán)重。第二，利用加權(quán)PageRank來(lái)衡量節(jié)點(diǎn)的直接和間接影響力，最終融合所有影響力得到節(jié)點(diǎn)的最終影響力，并篩選出影響力最大的前k個(gè)節(jié)點(diǎn)。

3.1 邊權(quán)重的分配

由于異質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，每個(gè)節(jié)點(diǎn)都能通過(guò)不同的元路徑與其他類(lèi)型節(jié)點(diǎn)相連得到不同類(lèi)型的連接邊并產(chǎn)生不同的影響關(guān)系，其中每條連接邊的權(quán)重都不盡相同，這與連接邊的兩個(gè)節(jié)點(diǎn)間的交互程度密切關(guān)聯(lián)，若兩節(jié)點(diǎn)間交互次數(shù)過(guò)多，則對(duì)應(yīng)的邊權(quán)重也大。為了能減少不同類(lèi)型邊的差異性，簡(jiǎn)化整個(gè)復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)，同時(shí)保留網(wǎng)絡(luò)的異質(zhì)性和不同類(lèi)型節(jié)點(diǎn)之間的影響關(guān)系，并為影響關(guān)系分配相應(yīng)的權(quán)重，該文將包含多種連接關(guān)系的異質(zhì)信息網(wǎng)絡(luò)分解成若干個(gè)只含一種連接類(lèi)型的網(wǎng)絡(luò)。如圖1中的DBLP網(wǎng)絡(luò)，APTC四種類(lèi)型節(jié)點(diǎn)，直接相連關(guān)系A(chǔ)-P/P-A,P-T/T-P,P-C/C-P，故可以分解成只含有AP,PT,PC類(lèi)型的三個(gè)異質(zhì)信息網(wǎng)絡(luò)，使每條邊的權(quán)重分別為對(duì)應(yīng)的連接次數(shù)，如圖2所示。

(a) (b) (c)

一個(gè)節(jié)點(diǎn)的影響力除了與它直接相連的鄰居有關(guān)，還與它鄰居的鄰居有關(guān)，因此可以基于單中介元路徑獲得節(jié)點(diǎn)的間接相連關(guān)系，若一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)間接相連的節(jié)點(diǎn)的路徑數(shù)越多，則說(shuō)明它們之間的聯(lián)系越緊密，因此根據(jù)路徑數(shù)為節(jié)點(diǎn)的間接相連關(guān)系分配對(duì)應(yīng)的權(quán)重。對(duì)圖1中的DBLP網(wǎng)絡(luò)而言，A能通過(guò)P與A、C、T間接相連，則對(duì)應(yīng)的間接相連關(guān)系有A-A,A-C/C-A,A-T/T-A,將圖1中的間接相連關(guān)系提取出來(lái)，例如A1和C2只能通過(guò)元路徑A1P2C2相連，路徑數(shù)為1，而A4和C2可以通過(guò)元路徑A4P2C2,A4P3C2相連，路徑數(shù)為2，則A1和C2的邊權(quán)重為1，A4和C2的邊權(quán)重為2，如圖3所示。

(a) (b) (c)

3.2 影響力度量

加權(quán)PageRank延續(xù)了PageRank的優(yōu)點(diǎn)，能夠通過(guò)節(jié)點(diǎn)間的連接數(shù)量和質(zhì)量來(lái)綜合描述節(jié)點(diǎn)的重要性，同時(shí)又根據(jù)節(jié)點(diǎn)之間的交互程度分配對(duì)應(yīng)的權(quán)重。該文利用加權(quán)PageRank來(lái)度量節(jié)點(diǎn)對(duì)不同類(lèi)型節(jié)點(diǎn)的影響力，其綜合影響力主要由直接影響力和間接影響力組成。

3.2.1 直接影響力

為給定的若干個(gè)直接相連兩種不同類(lèi)型節(jié)點(diǎn)，只包含一種類(lèi)型邊的異質(zhì)信息網(wǎng)絡(luò)G構(gòu)建一個(gè)加權(quán)有向圖，i,j是兩種不同類(lèi)型A,B的節(jié)點(diǎn)，若j指向i，則j到i有邊，邊的權(quán)重等于j到i邊的個(gè)數(shù)k，即wj,i=k，否則wi,j=0，使用加權(quán)PageRank計(jì)算得到j(luò)對(duì)i貢獻(xiàn)的PR值，即i對(duì)j的重要性為：

(3)

(4)

其中,N(i)為與i直接相連的不同類(lèi)型節(jié)點(diǎn)的集合，故得i對(duì)所有與它相連的B類(lèi)型節(jié)點(diǎn)的直接影響力為：

(5)

3.2.2 間接影響力

IIi1,t1=Pi1,t1PRt1

(6)

那么i1對(duì)所有與它相連的類(lèi)型C的節(jié)點(diǎn)的間接影響力為：

(7)

其中，ii(i)為與i1間接相連的節(jié)點(diǎn)類(lèi)型的集合。

圖4 間接相連關(guān)系圖

3.2.3 綜合影響力

異質(zhì)信息網(wǎng)絡(luò)中，節(jié)點(diǎn)類(lèi)型豐富，它們之間的影響力是通過(guò)直接或間接關(guān)系相連去傳播的。該文將融合節(jié)點(diǎn)的直接影響力和間接影響力，作為節(jié)點(diǎn)的最終綜合影響力Ii，Ii的表示如下：

(8)

3.2.4 篩選種子節(jié)點(diǎn)

通過(guò)融合節(jié)點(diǎn)的直接影響力和間接影響力得到節(jié)點(diǎn)的最終影響力，因此可以對(duì)所有節(jié)點(diǎn)的最終影響力進(jìn)行排序。為了避免種子節(jié)點(diǎn)影響力重合，該文采用邊際增益策略篩選種子節(jié)點(diǎn)。先選擇一個(gè)影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，然后去除其余節(jié)點(diǎn)與其影響重疊的部分，再選擇剩余節(jié)點(diǎn)中影響力最大作為種子節(jié)點(diǎn)，不斷重復(fù)此過(guò)程，直到篩選出給定數(shù)量的節(jié)點(diǎn)作為種子集為止。

CWPR是基于加權(quán)PageRank迭代計(jì)算獲得節(jié)點(diǎn)的影響力，因此使用鄰接矩陣對(duì)節(jié)點(diǎn)間的關(guān)系進(jìn)行表示存儲(chǔ)，需要的空間復(fù)雜度為O(n2)，其中n為節(jié)點(diǎn)數(shù)，而PR值的計(jì)算是一個(gè)迭代過(guò)程，向量與矩陣相乘所需要的時(shí)間復(fù)雜度為O(n2)，經(jīng)過(guò)若干次迭代達(dá)到收斂所需的時(shí)間復(fù)雜度為O(cn2)，其中c為迭代次數(shù)。

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)準(zhǔn)備

數(shù)據(jù)集：使用了兩個(gè)最常見(jiàn)的文獻(xiàn)網(wǎng)絡(luò)數(shù)據(jù)集DBLP和Yelp，數(shù)據(jù)集的情況分別如表1和表2所示。

表1 DBLP數(shù)據(jù)集詳細(xì)信息

表2 Yelp數(shù)據(jù)集詳細(xì)信息

對(duì)比算法：為了驗(yàn)證CWPR方法的有效性，該文將與已有的同質(zhì)信息網(wǎng)絡(luò)影響力度量方法Degree(DC)、PageRank(PR)以及異質(zhì)的方法APR和CWPR的變種方法CWPR-II進(jìn)行實(shí)驗(yàn)對(duì)比。由于目前對(duì)于網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的度量方法大多都是針對(duì)同質(zhì)信息網(wǎng)絡(luò)的，而本實(shí)驗(yàn)是利用異質(zhì)信息網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)進(jìn)行影響力最大化研究，為了進(jìn)行對(duì)比實(shí)驗(yàn)，故將常用的同質(zhì)信息網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的度量方法直接運(yùn)用于異質(zhì)信息網(wǎng)絡(luò)，在使用這些方法時(shí)，忽略不同類(lèi)型節(jié)點(diǎn)之間關(guān)系的差異，根據(jù)度量方法計(jì)算得到每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的度量值。在選取種子集時(shí)，由于不同類(lèi)型節(jié)點(diǎn)在信息擴(kuò)散中扮演的角色不同，為了減少實(shí)驗(yàn)的差異性，種子集類(lèi)型固定，本實(shí)驗(yàn)以人作為目標(biāo)類(lèi)型，選取度量值最大的目標(biāo)類(lèi)型節(jié)點(diǎn)作為種子集。對(duì)比算法描述如下。

Degree centrality(DC)：一個(gè)節(jié)點(diǎn)v與它直接相連的鄰居節(jié)點(diǎn)的個(gè)數(shù)，稱(chēng)為度，一個(gè)節(jié)點(diǎn)度越大，就意味著這個(gè)節(jié)點(diǎn)越重要。

PageRank(PR)：網(wǎng)頁(yè)重要性度量方法，如果一個(gè)網(wǎng)頁(yè)被很多網(wǎng)頁(yè)鏈接，或者被知名度很高的網(wǎng)頁(yè)鏈接，則這個(gè)網(wǎng)頁(yè)的重要性就越大，也可以用于社交網(wǎng)絡(luò)節(jié)點(diǎn)分析。

APR：一種在異質(zhì)的文獻(xiàn)網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性度量方法，利用PageRank度量的異質(zhì)信息網(wǎng)絡(luò)中作者和文章兩種類(lèi)型節(jié)點(diǎn)之間的影響力，對(duì)于DBLP、Yelp則分別考慮了作者和文章，用戶(hù)和商業(yè)之間的影響力。

CWPR-II：該文提出的CWPR的變體，在異質(zhì)網(wǎng)絡(luò)中只考慮人與人之間的影響力。

CWPR：該文提出的異質(zhì)信息網(wǎng)絡(luò)影響力的度量算法，基于異質(zhì)信息網(wǎng)絡(luò)的連接結(jié)構(gòu)，考慮了不同類(lèi)型節(jié)點(diǎn)之間的影響力。

擴(kuò)散模型：采用線(xiàn)性閾值模型LT作為傳播模型，將每一節(jié)點(diǎn)的入度邊的度數(shù)歸一化，作為每個(gè)節(jié)點(diǎn)被自己入鄰居節(jié)點(diǎn)激活的概率，使它們和為1，每個(gè)非激活節(jié)點(diǎn)都有一個(gè)[0,1]的激活閾值，當(dāng)非激活節(jié)點(diǎn)的已激活鄰居節(jié)點(diǎn)對(duì)其影響總和超過(guò)該閾值，則此節(jié)點(diǎn)被激活。該文的擴(kuò)散指標(biāo)分別為在k個(gè)有影響力的作者和用戶(hù)作為種子集時(shí)被影響的作者和用戶(hù)的個(gè)數(shù)，影響的人越多說(shuō)明實(shí)驗(yàn)效果越好。為了減小實(shí)驗(yàn)的偶然性，進(jìn)行了10 000次蒙特卡洛仿真來(lái)估計(jì)影響擴(kuò)散結(jié)果

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 算法參數(shù)的影響

圖5 算法參數(shù)的影響

對(duì)以上實(shí)驗(yàn)結(jié)果分析可知，在數(shù)據(jù)集DBLP中，當(dāng)λAP=0.4,ηAA=0.2,ηAC=0.2,ηAT=0.2時(shí)，影響范圍的值達(dá)到最大，這表明在信息擴(kuò)散過(guò)程中作者對(duì)論文的影響力是作者的綜合影響力的重要組成部分。而對(duì)于數(shù)據(jù)集Yelp，當(dāng)λUB=0.3,ηUU=0.3,ηBC=0.3,ηBCat=0.1時(shí)，影響范圍的值達(dá)到最大，此時(shí)在信息擴(kuò)散過(guò)程中，用戶(hù)和領(lǐng)域的之間的影響力在用戶(hù)的綜合影響力所占的比重最小。用戶(hù)和用戶(hù)、商業(yè)、城市之間的影響力則是用戶(hù)綜合影響力的重要組成部分。

4.2.2 邊權(quán)重參數(shù)的影響

在異質(zhì)信息網(wǎng)絡(luò)中，包含了多種類(lèi)型的邊，每種類(lèi)型的邊在信息擴(kuò)散中同不同類(lèi)型的節(jié)點(diǎn)一樣也是扮演著不同的角色。同不同類(lèi)型節(jié)點(diǎn)一樣，該文也假設(shè)異質(zhì)信息網(wǎng)絡(luò)中不同類(lèi)型邊的權(quán)重等于1，則數(shù)據(jù)集DBLP中有WAP+WPC+WPT=1,數(shù)據(jù)集Yelp中有WUB+WBC+WBCat=1。通過(guò)設(shè)置多種不同的權(quán)重并選出k=50個(gè)種子所得到的影響范圍大小進(jìn)行結(jié)果對(duì)比，從而獲得一組合理的邊權(quán)值。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 邊權(quán)重的影響

由實(shí)驗(yàn)結(jié)果可知，在數(shù)據(jù)集DBLP中，當(dāng)WAP=0.5,WPC=0.4,WPT=0.1時(shí)，影響范圍的值達(dá)到最大，此時(shí)作者與論文之間的邊權(quán)值是三個(gè)中間最大的，這說(shuō)明在信息擴(kuò)散過(guò)程中作者與論文之間的關(guān)系起著重要作用，同時(shí)發(fā)現(xiàn)對(duì)于每一組權(quán)重，若是論文與主題之間的邊權(quán)重是三者中最大的一個(gè)，則影響范圍的值將會(huì)下降，則可以認(rèn)為在信息擴(kuò)散中，論文與主題之間的關(guān)系影響作用較小。在數(shù)據(jù)集Yelp中，當(dāng)WUB=0.5,WBC=0.25,WBCat=0.25，影響范圍的值達(dá)到最大，此時(shí)用戶(hù)和商業(yè)之間的關(guān)系在信息擴(kuò)散過(guò)程中起著重要的作用。通過(guò)對(duì)這兩個(gè)數(shù)據(jù)集的邊權(quán)重分析發(fā)現(xiàn)，均是人和與人直接相連的類(lèi)型節(jié)點(diǎn)的邊權(quán)重在所有邊權(quán)重所占的比重是最大的，這也表明了直接的影響會(huì)比間接影響更有力。

通過(guò)對(duì)算法參數(shù)和邊權(quán)重設(shè)置不同值，分別選取了各自最好的結(jié)果，作為該算法有效性驗(yàn)證的參數(shù)。

4.2.3 有效性驗(yàn)證

對(duì)于數(shù)據(jù)集DBLP和Yelp，本實(shí)驗(yàn)的種子集的類(lèi)型分別設(shè)為作者和用戶(hù)，由于本實(shí)驗(yàn)基于不同元路徑考慮了不同類(lèi)型的節(jié)點(diǎn)直接的影響，在數(shù)據(jù)集DBLP中，對(duì)不同類(lèi)型的邊權(quán)重設(shè)為WAP=0.5,WPC=0.4,WPT=0.1。在數(shù)據(jù)集Yelp中，設(shè)各類(lèi)型的邊權(quán)重為WUB=0.5,WBC=0.25,WBCat=0.25，實(shí)驗(yàn)對(duì)比方法中的同質(zhì)方法DC和PageRank不區(qū)分邊的類(lèi)型，權(quán)重都為0.5。實(shí)驗(yàn)效果如圖7所示。

圖7 影響范圍

由這些實(shí)驗(yàn)對(duì)比結(jié)果可知，保留各種類(lèi)型節(jié)點(diǎn)信息的三種異質(zhì)方法要明顯優(yōu)于其他兩種同質(zhì)方法，在DBLP中該文所提出的CWPR方法明顯優(yōu)于其他兩種異質(zhì)方法CWPR-II、APR，而在Yelp中CWPR也同樣優(yōu)于其他兩種異質(zhì)方法，但是差距并不如DBLP明顯。該文給出的三種異質(zhì)方法都區(qū)分了不同類(lèi)型的邊的權(quán)重，但CWPR考慮了不同類(lèi)型節(jié)點(diǎn)之間的影響，而APR,CWPR-II只考慮了部分的類(lèi)型節(jié)點(diǎn)的影響。通過(guò)以上實(shí)驗(yàn)結(jié)果可以表明，在異質(zhì)信息網(wǎng)絡(luò)中，保留節(jié)點(diǎn)與其他類(lèi)型節(jié)點(diǎn)之間的語(yǔ)義信息比只保留部分信息能更全面地評(píng)價(jià)節(jié)點(diǎn)的特征，得到更好的實(shí)驗(yàn)效果，從而可以借助這種方法得到最有影響力的節(jié)點(diǎn)。

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

該文提出了一種基于加權(quán)PageRank的異質(zhì)信息網(wǎng)絡(luò)影響力最大化算法CWPR，該算法將包含多種類(lèi)型節(jié)點(diǎn)的異質(zhì)信息網(wǎng)絡(luò)分解成若干個(gè)只含一種連接類(lèi)型的網(wǎng)絡(luò)，然后通過(guò)節(jié)點(diǎn)之間的連接方式考慮了所有不同類(lèi)型節(jié)點(diǎn)之間的影響關(guān)系，去獲得影響力最大的節(jié)點(diǎn)作為信息擴(kuò)散的種子節(jié)點(diǎn)，從而實(shí)現(xiàn)異質(zhì)信息網(wǎng)絡(luò)影響力的最大化。通過(guò)在兩個(gè)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，在異質(zhì)信息網(wǎng)絡(luò)中，保留節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的信息越多，篩選出的種子節(jié)點(diǎn)得到的影響效果越好。但是該算法的不足在于對(duì)異質(zhì)信息網(wǎng)絡(luò)中不同類(lèi)型的邊權(quán)重的設(shè)置是基于先驗(yàn)知識(shí)設(shè)定的，在未來(lái)的研究中，可以通過(guò)機(jī)器學(xué)習(xí)去自主獲得不同類(lèi)型的邊權(quán)重，使得邊權(quán)重結(jié)果更加真實(shí)可靠。