異質(zhì)社會網(wǎng)中基于信息熵的影響最大化算法

徐 行，陳紅梅，周麗華

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

隨著信息技術(shù)的快速發(fā)展，人們通過微信、FaceBook 等社交平臺建立聯(lián)系，形成了龐大復(fù)雜的社會網(wǎng).影響最大化（Influence Maximization，IM）是社會網(wǎng)分析的重要研究方向，旨在根據(jù)特定擴(kuò)散模型，尋找初始種子集，最大化傳播和擴(kuò)散的節(jié)點(diǎn)范圍，已被廣泛應(yīng)用于廣告營銷、輿情控制等領(lǐng)域.IM 已被證明是NP-hard 問題，為了有效解決IM，Kempe 等[1]提出保證求解精度為(1-1/e)的貪心算法，但該算法時(shí)間復(fù)雜度較高，不適用于大型社會網(wǎng).盡管文獻(xiàn)[2-3]對貪心算法進(jìn)行優(yōu)化，提出了CELF、NewGreedy 和MixedGreedy 算法，但是在中等規(guī)模的社會網(wǎng)上選擇50 個(gè)種子節(jié)點(diǎn)仍需數(shù)小時(shí).近年來，為了緩解貪心算法時(shí)間復(fù)雜度高的問題，研究者提出了許多啟發(fā)式算法，例如，基于度的算法[4-5]，基于路徑的算法[6-8]，基于反向可達(dá)集的算法[9-10]和基于信息熵的算法[11-13].上述方法均是針對同質(zhì)社會網(wǎng)，即將社會網(wǎng)視為所有節(jié)點(diǎn)（對象）都是同一類型，所有邊（關(guān)系）也是同一類型的網(wǎng)絡(luò)，忽視了現(xiàn)實(shí)社會網(wǎng)中對象類型及對象間關(guān)系類型的多樣性.

在異質(zhì)社會網(wǎng)中，多種類型的對象和關(guān)系共存，蘊(yùn)含著豐富的結(jié)構(gòu)和語義信息，這為發(fā)現(xiàn)網(wǎng)絡(luò)的深層信息提供了新途徑，同時(shí)也給網(wǎng)絡(luò)上的影響最大化帶來了新挑戰(zhàn).目前，異質(zhì)社會網(wǎng)影響最大化的相關(guān)研究較少.文獻(xiàn)[14-15]提出了異質(zhì)社會網(wǎng)中基于元路徑信息熵的影響最大化（Meta Path-based Information Entropy,MPIE）算法和基于有向無環(huán)圖的影響最大化算法（DAG-based Influence Maximization algorithm in heterogeneous information networks,DAGIM）.MPIE 算法根據(jù)元路徑將異質(zhì)網(wǎng)建模成多個(gè)同質(zhì)網(wǎng)，然后分別計(jì)算每個(gè)同質(zhì)網(wǎng)中節(jié)點(diǎn)的影響力，最后通過加權(quán)融合節(jié)點(diǎn)在各個(gè)同質(zhì)網(wǎng)中的影響，該算法依靠經(jīng)驗(yàn)設(shè)定元路徑，而且將異質(zhì)社會網(wǎng)中節(jié)點(diǎn)間的影響權(quán)重統(tǒng)一設(shè)定為1/d（d是節(jié)點(diǎn)入度），忽視了現(xiàn)實(shí)社會網(wǎng)中對象間關(guān)系的差異性.DAGIM 算法將異質(zhì)網(wǎng)中節(jié)點(diǎn)的影響限制在一個(gè)有向無環(huán)圖中，并區(qū)分了不同類型邊的影響程度以有效利用異質(zhì)網(wǎng)豐富的結(jié)構(gòu)和語義信息，但該算法依賴于尋找高質(zhì)量的有向無環(huán)圖及事先設(shè)定的邊類型權(quán)重，此外，采用有向無環(huán)圖限制影響的方式忽視了其他路徑對節(jié)點(diǎn)的影響，而事先設(shè)定邊類型權(quán)重的方法同樣依賴于經(jīng)驗(yàn).因此，如何度量不同類型節(jié)點(diǎn)或同類型不同節(jié)點(diǎn)之間的影響權(quán)重及節(jié)點(diǎn)的全局影響，最大化種子節(jié)點(diǎn)的影響范圍是本文要解決的問題.

本文提出異質(zhì)社會網(wǎng)中基于信息熵的影響最大化算法（Influence Maximization algorithm based on Information Entropy in Heterogeneous social networks,IMIEH）.首先，考慮異質(zhì)網(wǎng)中，不同類型節(jié)點(diǎn)所攜帶信息不同，不同節(jié)點(diǎn)間所傳遞信息也不同，基于節(jié)點(diǎn)類型，提出節(jié)點(diǎn)的參與熵和交互熵，進(jìn)而計(jì)算節(jié)點(diǎn)間的影響權(quán)重.該方法不僅度量了節(jié)點(diǎn)所攜帶的信息量，也融入了網(wǎng)絡(luò)的異質(zhì)性和節(jié)點(diǎn)間影響的差異性.然后，基于線性閾值模型，通過計(jì)數(shù)節(jié)點(diǎn)在有限鄰域內(nèi)到達(dá)其他節(jié)點(diǎn)的簡單路徑，計(jì)算節(jié)點(diǎn)的全局影響，最后根據(jù)邊際增益策略選擇影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn).

具體地，本文的主要貢獻(xiàn)如下：

（1） 提出一種異質(zhì)社會網(wǎng)中計(jì)算節(jié)點(diǎn)影響權(quán)重的方法，該方法提出節(jié)點(diǎn)的參與熵和交互熵以度量不同類型節(jié)點(diǎn)所攜帶信息及不同節(jié)點(diǎn)所傳遞信息的差異，進(jìn)而度量節(jié)點(diǎn)間的影響差異；

（2） 提出計(jì)算節(jié)點(diǎn)全局影響的方法，該方法基于線性閾值模型，通過計(jì)數(shù)節(jié)點(diǎn)在有限鄰域內(nèi)到達(dá)其他節(jié)點(diǎn)的簡單路徑，計(jì)算節(jié)點(diǎn)的全局影響；

（3） 在3 個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了，所提IMIEH 算法的影響最大化效果不僅優(yōu)于同質(zhì)網(wǎng)上的SimPath 算法，還優(yōu)于異質(zhì)網(wǎng)上的MPIE 算法和DAGIM 算法.

1 相關(guān)工作

2003 年，Kempe 等[1]將IM 問題描述為一個(gè)離散優(yōu)化問題，并提出了線性閾值（Linear Threshold，LT）模型和獨(dú)立級聯(lián)（Independent Cascade，IC）模型模擬信息傳播的過程，進(jìn)而提出貪心算法，該算法需要進(jìn)行大量蒙特卡羅（Monte-Carlo，MC）模擬，運(yùn)行效率較低.為了解決效率問題，Leskovec 等[2]利用了影響函數(shù)的亞模性和單調(diào)性對傳統(tǒng)貪心算法進(jìn)行優(yōu)化.Chen 等[3]提出了兩種改進(jìn)的貪心算法NewGreedy 和MixedGreedy，進(jìn)一步對傳統(tǒng)貪心算法進(jìn)行優(yōu)化.然而，上述改進(jìn)的貪心算法的計(jì)算復(fù)雜度仍然很高，不適用于大規(guī)模的網(wǎng)絡(luò).與貪心算法相比，啟發(fā)式算法具有更好的效率和可擴(kuò)展性.Chen[3]等基于節(jié)點(diǎn)的度，提出DegreeDiscount 算法，該算法通過降低種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度中心性減少節(jié)點(diǎn)之間的影響重疊.Chen 等[16]和Goyal 等[6]利用LT 模型的特性，提出針對LT 模型的可拓展的影響力最大化算法.IRIE 算法[17]計(jì)算每個(gè)節(jié)點(diǎn)的全局影響排名，并在選中每個(gè)種子節(jié)點(diǎn)后，重新計(jì)算剩余節(jié)點(diǎn)的全局影響變化以避免節(jié)點(diǎn)影響力重疊問題.Zareie 等[18]綜合考慮節(jié)點(diǎn)的直接影響和間接影響，在最小化種子節(jié)點(diǎn)間的重疊影響的同時(shí)，最大化節(jié)點(diǎn)的影響范圍，該算法時(shí)間復(fù)雜度較高.Li 等[19]利用相對熵量化節(jié)點(diǎn)間社交距離，提出基于內(nèi)聚熵的社區(qū)重疊傳播算法劃分社區(qū)，并在縮小種子選擇范圍的基礎(chǔ)上，設(shè)計(jì)可選的動(dòng)態(tài)影響傳播算法.上述影響最大化的研究均是針對同質(zhì)網(wǎng)絡(luò).

然而，社會網(wǎng)通常是異質(zhì)的，具有豐富的結(jié)構(gòu)和語義信息.為了揭示異質(zhì)網(wǎng)蘊(yùn)含的深層信息，研究者在異質(zhì)網(wǎng)上開展了一系列的研究工作.例如，分類[20-21]，聚類[22-24]和鏈路預(yù)測[25]等.針對異質(zhì)網(wǎng)上的影響最大化問題，Li 等[26]考慮用戶類型節(jié)點(diǎn)間的關(guān)系，根據(jù)不同類型的關(guān)系，將異質(zhì)網(wǎng)轉(zhuǎn)化為概率影響圖，提出基于信息熵的啟發(fā)式算法選擇種子節(jié)點(diǎn).Liu 等[27]利用網(wǎng)絡(luò)中與每個(gè)用戶相關(guān)的異質(zhì)鏈接信息和文本內(nèi)容挖掘主題級別的影響強(qiáng)度，提出一種生成圖形模型，在學(xué)習(xí)直接影響的基礎(chǔ)上，研究了影響傳播和聚合機(jī)制：保守傳播和非保守傳播以推導(dǎo)間接影響.Wang 等[28]定義了異質(zhì)網(wǎng)中的影響最大化問題，提出了一種協(xié)同排序框架，該框架根據(jù)類型，將異質(zhì)網(wǎng)分成多個(gè)同質(zhì)網(wǎng)，并分別在多個(gè)同質(zhì)網(wǎng)上選擇種子節(jié)點(diǎn).Yang 等[14]利用元路徑提取異質(zhì)網(wǎng)中的多個(gè)語義信息，據(jù)此將異質(zhì)網(wǎng)建模成多個(gè)同質(zhì)網(wǎng)，分別計(jì)算這些具有不同語義的同質(zhì)網(wǎng)中的節(jié)點(diǎn)影響力.Molaei 等[29]結(jié)合節(jié)點(diǎn)的局部和全局信息，通過計(jì)算不同元路徑的熵來評估異質(zhì)網(wǎng)中節(jié)點(diǎn)的影響.Keikha 等[30]利用深度學(xué)習(xí)技術(shù)學(xué)習(xí)保留異質(zhì)網(wǎng)中本地和全局結(jié)構(gòu)信息的節(jié)點(diǎn)特征向量，以優(yōu)化異質(zhì)網(wǎng)中的影響最大化算法.

與上述文獻(xiàn)中的方法不同，本文著眼于異質(zhì)社會網(wǎng)中重要的“人”類型節(jié)點(diǎn)，研究以“人”類型節(jié)點(diǎn)作為種子節(jié)點(diǎn)，他們通過異質(zhì)社會網(wǎng)中的“人”類型節(jié)點(diǎn)或其他類型節(jié)點(diǎn)傳播和擴(kuò)散信息，并最大化被影響的“人”類型節(jié)點(diǎn)的數(shù)量.

2相關(guān)概念及問題描述

定義 1異質(zhì)信息網(wǎng)[12].異質(zhì)信息網(wǎng)定義為包含節(jié)點(diǎn)的映射關(guān)系φ:V→A和邊的映射關(guān)系 φ:E→R的有向圖G=(V,E,A,R)，其中每個(gè)節(jié)點(diǎn)v∈V屬于一個(gè)特定的節(jié)點(diǎn)類型φ(v)∈A，每條邊e∈E屬于一個(gè)特定的邊類型φ(e)∈R，且|A|+|R|＞2.

定義 2影響最大化[31].給定一個(gè)社會網(wǎng)G=(V,E,A,R)及基于某個(gè)信息擴(kuò)散模型的影響函數(shù)σ：P→P，其中P是節(jié)點(diǎn)集V的冪集.影響最大化的目標(biāo)就是尋找一個(gè)非空節(jié)點(diǎn)子集S∈P，使得|σ(S)|最大，即：

定義 3線性閾值模型[6].線性閾值模型是一種常用于描述網(wǎng)絡(luò)中信息傳播過程的信息擴(kuò)散模型.線性閾值模型的信息傳播擴(kuò)散過程如下：

（1） 對于每個(gè)節(jié)點(diǎn)u∈V，初始化一個(gè)[0,1]之間的隨機(jī)閾值 θu，并根據(jù)節(jié)點(diǎn)u的入度，初始化入鄰居對其的影響概率bv,u，其中表示節(jié)點(diǎn)u的入鄰居集，

（2） 給定一個(gè)種子集S，S中的節(jié)點(diǎn)設(shè)為活躍狀態(tài)，其余節(jié)點(diǎn)設(shè)為非活躍狀態(tài)，并初始化時(shí)刻t.

（3） 在時(shí)刻t，對每個(gè)非活躍節(jié)點(diǎn)u，計(jì)算所有活躍入鄰居節(jié)點(diǎn)對其的影響總和其中表示節(jié)點(diǎn)u的活躍入鄰居集.如果則節(jié)點(diǎn)u被激活，后繼時(shí)刻變?yōu)榛钴S節(jié)點(diǎn).

（4） 如果沒有節(jié)點(diǎn)被激活，則信息傳播擴(kuò)散過程結(jié)束，否則，進(jìn)入下一時(shí)刻t=t+1，重復(fù)步驟（3）～（4）.

異質(zhì)社會網(wǎng)作為一種特殊的異質(zhì)信息網(wǎng)，分析“人”類型節(jié)點(diǎn)通過其他相同類型節(jié)點(diǎn)或不同類型節(jié)點(diǎn)而產(chǎn)生的相互影響及影響最大化，在現(xiàn)實(shí)應(yīng)用中具有重要意義.因此，本文研究以“人”類型節(jié)點(diǎn)作為種子節(jié)點(diǎn)，他們通過異質(zhì)社會網(wǎng)中的“人”類型節(jié)點(diǎn)或其他類型節(jié)點(diǎn)傳播和擴(kuò)散信息，并最大化被影響的“人”類型節(jié)點(diǎn)的數(shù)量.例如，在異質(zhì)學(xué)術(shù)網(wǎng)DBLP 中，我們尋找一定數(shù)量的作者，使得這些作者通過發(fā)表論文或者參加學(xué)術(shù)會議影響更多其他的作者.

問題描述：給定一個(gè)異質(zhì)社會網(wǎng)G=(V,E,A,R)，不失一般性，設(shè)其中的“人”類型為Ap∈A，以及線性閾值模型的影響函數(shù)σ:PAp→PAp，其中PAp是Ap類型節(jié)點(diǎn)集VAp?V的冪集.影響最大化的目標(biāo)就是尋找一個(gè)非空Ap類型節(jié)點(diǎn)子集SAp∈PAp，使得最大，即：

3 IMIEH 算法

本節(jié)提出異質(zhì)社會網(wǎng)中基于信息熵的影響最大化算法IMIEH.首先提出節(jié)點(diǎn)的參與熵和交互熵，進(jìn)而計(jì)算節(jié)點(diǎn)間的影響權(quán)重；然后基于影響權(quán)重，計(jì)數(shù)節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的簡單路徑，進(jìn)而計(jì)算節(jié)點(diǎn)的全局影響；最后根據(jù)邊際增益策略選擇種子節(jié)點(diǎn).

3.1 計(jì)算影響權(quán)重現(xiàn)實(shí)生活中，不同對象間的影響是不相等的.一方面，不同類型對象間形成的不同類型關(guān)系蘊(yùn)含不同的語義，有著不同的作用.另一方面，一個(gè)對象影響另一個(gè)對象的程度與該對象的交互頻率有關(guān)，通常對象在網(wǎng)絡(luò)中的交互頻率越高，則影響程度越大.因此，本文首先根據(jù)節(jié)點(diǎn)的入鄰居中“人”類型節(jié)點(diǎn)，定義“人”類型節(jié)點(diǎn)在該節(jié)點(diǎn)上的參與熵；然后根據(jù)節(jié)點(diǎn)的出鄰居節(jié)點(diǎn)，定義該節(jié)點(diǎn)的交互熵；最后融合它們，計(jì)算節(jié)點(diǎn)間的影響權(quán)重.例如，在圖1(a)中尋找最大影響其他作者的作者種子節(jié)點(diǎn)，我們關(guān)注作者類型(A)節(jié)點(diǎn)，認(rèn)為連接“A”類型節(jié)點(diǎn)的邊即“A-P”類型的邊更重要，其余類型邊的重要性取決于該邊的源節(jié)點(diǎn)與“A”類型節(jié)點(diǎn)的交互頻率.下面給出相關(guān)定義.

圖1 DBLP 異質(zhì)社會網(wǎng)示例Fig.1 An example of DBLP heterogeneous social network

定義 4指示函數(shù).給定一個(gè)異質(zhì)社會網(wǎng)G=(V,E,A,R)，VAp?V為“人”類型Ap∈A的節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)u∈V的指示函數(shù)定義為

定義 5參與熵.給定一個(gè)異質(zhì)社會網(wǎng)G=(V,E,A,R)，Ap∈A為“人”類型，為節(jié)點(diǎn)u∈V的入鄰居集，為節(jié)點(diǎn)u∈V的入鄰居中Ap類型節(jié)點(diǎn)集，pvu為節(jié)點(diǎn)v到節(jié)點(diǎn)u的概率，即則Ap類型節(jié)點(diǎn)在節(jié)點(diǎn)u上的參與熵定義為

定義 6交互熵.給定一個(gè)異質(zhì)社會網(wǎng)G=為節(jié)點(diǎn)u∈V的出鄰居集，則節(jié)點(diǎn)u的交互熵定義為

定義 7影響權(quán)重.給定一個(gè)異質(zhì)社會網(wǎng)G=(V,E,A,R)，邊e＜u,w＞∈E上節(jié)點(diǎn)u對節(jié)點(diǎn)w的影響權(quán)重定義為

其中，α表示指示函數(shù)和參與熵的權(quán)重，且α ∈[0,1].

算法 1計(jì)算影響權(quán)重

輸入異質(zhì)社會網(wǎng)絡(luò)G(V,E,A,R)，參數(shù)α

輸出帶影響權(quán)重的異質(zhì)社會網(wǎng)G(V,E,A,R,W)

步驟 1遍歷G中每個(gè)節(jié)點(diǎn)；

步驟 2使用公式（1）計(jì)算指示函數(shù)；

步驟 3使用公式（2）計(jì)算參與熵；

步驟 4使用公式（3）計(jì)算交互熵；

步驟 5遍歷G中每個(gè)一條邊；

步驟 6使用公式（4）計(jì)算每條邊的影響權(quán)重.

在算法1 中，步驟1～4 對每個(gè)節(jié)點(diǎn)u∈V，計(jì)算節(jié)點(diǎn)的指示函數(shù)、參與熵和交互熵，步驟5～6 對每條邊，計(jì)算邊上節(jié)點(diǎn)間的影響權(quán)重.算法1 的時(shí)間復(fù)雜度為O(|V|+|E|).

3.2 計(jì)算全局影響線性閾值模型等價(jià)于一個(gè)“l(fā)ive-edge”模型[1]：給定一個(gè)帶權(quán)圖G=(V,E,W)，每個(gè)節(jié)點(diǎn)v∈V，以w(u,v)的概率至多選擇一條入邊e＜u,v＞作為活動(dòng)邊，其他邊稱為阻塞邊，種子集S?V的信息傳播表示為S在G中可達(dá)節(jié)點(diǎn)的數(shù)量[6].本文采用上述思想，基于3.1 節(jié)的影響權(quán)重，計(jì)算節(jié)點(diǎn)的全局影響.

定義 8路徑影響.給定一個(gè)帶影響權(quán)重的異質(zhì)社會網(wǎng)G=(V,E,A,R,W)，節(jié)點(diǎn)u經(jīng)過簡單路徑p=(u=v1,v2,···,w=vm)對節(jié)點(diǎn)w的影響定義為

由于節(jié)點(diǎn)vi,vi+1之間的影響權(quán)重W(vi,vi+1)∈(0,1)，因此路徑p的長度越長，節(jié)點(diǎn)u對節(jié)點(diǎn)w的影響越小，甚至可以忽略.此外，在真實(shí)的社會網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)的影響局限在一個(gè)較小的鄰域內(nèi).因此，為了提升算法效率，本文引入一個(gè)影響閾值參數(shù)θ ∈[0,1]，將節(jié)點(diǎn)的影響限制在一個(gè)局部鄰域內(nèi)，即當(dāng)節(jié)點(diǎn)的影響小于閾值 θ時(shí)，則忽略該影響.

定義 9總路徑影響.給定一個(gè)帶影響權(quán)重的異質(zhì)社會網(wǎng)G=(V,E,A,R,W)，是節(jié)點(diǎn)u到節(jié)點(diǎn)w的所有簡單路徑集，則節(jié)點(diǎn)u對節(jié)點(diǎn)w的總路徑影響定義為

在異質(zhì)社會網(wǎng)中，不同類型節(jié)點(diǎn)間蘊(yùn)含著不同的信息，因此在計(jì)算節(jié)點(diǎn)影響力時(shí)，我們將分別計(jì)算節(jié)點(diǎn)對各種類型節(jié)點(diǎn)的影響力.假設(shè)G中存在n種類型的節(jié)點(diǎn)，即A={a1,a2,···,an}，Vai?V為類型ai∈A的節(jié)點(diǎn)集，節(jié)點(diǎn)u對ai類型節(jié)點(diǎn)的影響定義為

定義 10全局影響.給定一個(gè)帶影響權(quán)重的異質(zhì)社會網(wǎng)G=(V,E,A,R,W)，對每個(gè)節(jié)點(diǎn)u∈V，節(jié)點(diǎn)u的全局影響定義為

在圖1（b）中，A1 到P1 存在兩條簡單路徑，p1:A1→P1 和p2:A1→P2→A2→P1，則A1 通過路p1和p2對P1 的總路徑影響為0.51+1×1×0.49=1；A1 對P類型節(jié)點(diǎn)的影響為σP(A1)=FA1,P1+FA1,P2+FA1,P3=1+1+1=3；A1 的總影響為σ (A1)=σA(A1)+σP(A1)+σC(A1)=2+3+1.42=6.42.計(jì)算單個(gè)節(jié)點(diǎn)的全局影響的算法描述如下：

算法 2計(jì)算節(jié)點(diǎn)u的全局影響

在算法2 中，3～11 行計(jì)算節(jié)點(diǎn)u對每個(gè)ai∈A類型節(jié)點(diǎn)的影響，其中的5～9 行計(jì)算節(jié)點(diǎn)u對每個(gè)節(jié)點(diǎn)w∈Vai的總路徑影響，并通過7～8 行剪去小于閾值的路徑影響.算法2 的時(shí)間復(fù)雜度為O(|V|l)，其中l(wèi)為圖中節(jié)點(diǎn)間簡單路徑的平均數(shù).

基于計(jì)算節(jié)點(diǎn)間影響權(quán)重的算法1 和計(jì)算節(jié)點(diǎn)全局影響的算法2，本文所提IMIEH 算法的完整描述如算法3 所示.

算法 3IMIEH 算法

在算法3 中，第2 行使用算法1 計(jì)算節(jié)點(diǎn)間的影響權(quán)重，3～5 行使用算法2 計(jì)算每個(gè)節(jié)點(diǎn)的全局影響，6～9 行采用邊際增益策略[6]依次選擇k個(gè)影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn).算法3 中第2行的時(shí)間復(fù)雜度為O(|V|+|E|)，3～4 行為O(l|V|2)，6～9行為O(k|V|)，因?yàn)閨E|≤|V|2，k＜＜|V|，所以算法3的時(shí)間復(fù)雜度為O(l|V|2).

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

4.1 實(shí)驗(yàn)設(shè)置本文使用來自兩個(gè)領(lǐng)域的3 個(gè)真實(shí)的異質(zhì)社會網(wǎng)數(shù)據(jù)集，其中DBLP 數(shù)據(jù)集來自學(xué)術(shù)領(lǐng)域，包含4 種對象類型和3 種關(guān)系類型，YELP 數(shù)據(jù)集來自商業(yè)領(lǐng)域，包含3 種對象類型和3 種關(guān)系類型，Amazon 數(shù)據(jù)集來自商業(yè)領(lǐng)域，包含5 種對象類型和4 種關(guān)系類型，數(shù)據(jù)集的描述信息如表1 所示.

表1 異質(zhì)網(wǎng)數(shù)據(jù)集Tab.1 The heterogeneous network dataset

為了驗(yàn)證所提IMIEH 算法的有效性，本文選取兩個(gè)異質(zhì)社會網(wǎng)的影響最大化算法MPIE 和DAGIM，一個(gè)同質(zhì)社會網(wǎng)的影響最大化算法SimPath 作為對比算法.

（1） MPIE 算法[14]：MPIE 算法利用含有不用語義信息的元路徑將異質(zhì)社會網(wǎng)建模成多個(gè)同質(zhì)網(wǎng)，利用信息熵度量每個(gè)同質(zhì)網(wǎng)中節(jié)點(diǎn)的直接影響力和間接影響力，最后結(jié)合所有同質(zhì)網(wǎng)中的這兩種影響力作為節(jié)點(diǎn)的影響力，并選擇影響力最高的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn).在實(shí)驗(yàn)中，我們在[0,1]之間隨機(jī)生成并歸一化邊的權(quán)重.

（2） DAGIM 算法[15]：DAGIM 算法首先為每個(gè)節(jié)點(diǎn)構(gòu)建一個(gè)有向無環(huán)圖，計(jì)算節(jié)點(diǎn)在有向無環(huán)圖中的局部影響力，最后根據(jù)邊際增益策略，選擇影響力最大的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn).

（3） SimPath 算法[6]：SimPath 算法通過枚舉節(jié)點(diǎn)在有限范圍內(nèi)的簡單路徑，計(jì)算節(jié)點(diǎn)的影響力并選擇影響力最高的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn).在實(shí)驗(yàn)中，為了將SimPath 算法應(yīng)用于異質(zhì)社會網(wǎng)，我們將異質(zhì)社會網(wǎng)中所有節(jié)點(diǎn)視為同類型，所有邊視為同一類型，但是我們只選擇“人”類型節(jié)點(diǎn)作為種子節(jié)點(diǎn).

為了評估影響最大化算法的效果，通常采用種子集的影響范圍作為評價(jià)指標(biāo)[31].本文也采用此指標(biāo)，即基于線性閾值模型，模擬算法選出的種子節(jié)點(diǎn)集的擴(kuò)散過程，計(jì)數(shù)最終激活的節(jié)點(diǎn)數(shù)量，以此評價(jià)算法的優(yōu)劣.

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

4.2.1 影響擴(kuò)散范圍比較 DAGIM 算法和SimPath算法的最佳閾值參數(shù) θ為0.001[6,15]，IMIEH 算法的閾值參數(shù)取值范圍為[0.001,0.1]，默認(rèn)為0.001.本文所提算法和3 個(gè)對比算法在不同大小種子集上的影響擴(kuò)展范圍如圖2 所示.

圖2 不同種子集大小對算法的影響Fig.2 The effect of different seed set sizes on algorithms

可以看出，3 個(gè)數(shù)據(jù)集中，IMIEH 算法的總體表現(xiàn)最好，說明該算法能夠更好地捕獲和利用異質(zhì)社會網(wǎng)中豐富的結(jié)構(gòu)和語義信息并最大化種子節(jié)點(diǎn)的影響范圍.在DBLP 和Amazon 數(shù)據(jù)集上，當(dāng)種子節(jié)點(diǎn)數(shù)量較小時(shí)，DAGIM 算法略優(yōu)于IMIEH算法，可能原因是DAGIM 算法為這兩個(gè)社會網(wǎng)的邊設(shè)定了較合適的影響權(quán)重，但由于DAGIM 算法利用有向無環(huán)圖將節(jié)點(diǎn)的影響限制在有限區(qū)域內(nèi)，所以隨著種子節(jié)點(diǎn)數(shù)量的增加，種子節(jié)點(diǎn)的影響可能存在重疊，導(dǎo)致了效果不佳.

4.2.2 參數(shù) θ對IMIEH 算法的影響 為提高算法效率，IMIEH 算法采用閾值參數(shù) θ控制簡單路徑的長短.本節(jié)分析參數(shù)θ 對IMIEH 算法效果的影響，實(shí)驗(yàn)結(jié)果如圖3 所示.可以看出，在DBLP 和YELP數(shù)據(jù)集上，θ對IMIEH 算法的影響不顯著，可能的原因在于DBLP 和YELP 數(shù)據(jù)集相對稀疏，邊的影響權(quán)重占比較高即影響權(quán)重值偏大，導(dǎo)致閾值參數(shù)θ對其影響較小.而在Amazon 數(shù)據(jù)集上，θ對IMIEH 算法的影響較大，但當(dāng) θ減小到一定程度時(shí)，對IMIEH 算法的影響變小.總的來說，當(dāng) θ逐漸減小時(shí)，影響范圍逐漸增大，但增幅逐漸減小并趨于穩(wěn)定.因此，在度量節(jié)點(diǎn)影響力時(shí)，我們可以忽略節(jié)點(diǎn)對較遠(yuǎn)節(jié)點(diǎn)的影響，選擇恰當(dāng)?shù)膮?shù)θ，以兼顧IMIEH 算法的效果和效率.

圖3 參數(shù) θ對IMIEH 算法的影響Fig.3 The effect of the threshold θ on IMLH algorithm

4.2.3 參數(shù)α對IMIEH 算法的影響 為調(diào)節(jié)參與熵和交互熵的作用，IMIEH 算法采用權(quán)重參數(shù) α控制參與熵和交互熵的權(quán)重，本節(jié)分析參與熵權(quán)重α和交互熵權(quán)重(1-α)對IMIEH 算法的影響.實(shí)驗(yàn)中，設(shè)置種子集大小k=50，實(shí)驗(yàn)結(jié)果如圖4 所示.

圖4 參數(shù) α對IMIEH 算法的影響Fig.4 The effect of the weights α on IMLH algorithm

可以看出，不同數(shù)據(jù)集由于數(shù)據(jù)分布的差異性，交互熵和參與熵的作用不同.在DBLP 數(shù)據(jù)集上，隨著α值增大，影響擴(kuò)散范圍逐漸增加，在α=0.6時(shí)達(dá)到最大值；之后，隨著α值進(jìn)一步增大，影響擴(kuò)散范圍逐漸減小，說明在DBLP 數(shù)據(jù)集上，參與熵和交互熵都對IMIEH 算法有作用.而在YELP和Amazon 數(shù)據(jù)集上，隨著 α值的增大，影響擴(kuò)散范圍呈下降趨勢，說明在YELP 和Amazon 數(shù)據(jù)集上，IMIEH 算法主要受交互熵的影響，這可能是因?yàn)樵赮ELP 和Amazon 數(shù)據(jù)集中，“人”類型節(jié)點(diǎn)主導(dǎo)的邊占比較大，占比分別為84.5%和93.3%，使得節(jié)點(diǎn)的參與熵變化不大，進(jìn)而使得節(jié)點(diǎn)的交互熵成為主要影響因素.

5 結(jié)束語

本文提出了異質(zhì)社會網(wǎng)中基于信息熵的影響最大化算法IMIEH，該算法首先定義參與熵和交互熵，進(jìn)而度量節(jié)點(diǎn)間的影響權(quán)重，然后通過計(jì)數(shù)節(jié)點(diǎn)間的簡單路徑，度量節(jié)點(diǎn)的全局影響力，最后采用邊際增益策略選擇影響力最大的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn).實(shí)驗(yàn)結(jié)果表明，本文所提算法選擇的種子節(jié)點(diǎn)具有更廣的影響范圍.然而，IMIEH 算法中的最佳參數(shù)是通過實(shí)驗(yàn)獲取，在今后的研究中，將研究最佳參數(shù)的自適應(yīng)獲取方法.此外，現(xiàn)實(shí)生活中社會關(guān)系會隨著時(shí)間變化，在未來的研究中，將考慮時(shí)間因素，研究動(dòng)態(tài)社會網(wǎng)的影響最大化.