吳晴晴，周麗華*，寸軒懿，杜國王，姜懿庭

（1.云南大學(xué)信息學(xué)院，昆明 650000；2.云南師范大學(xué)信息學(xué)院，昆明 650000）

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，信息逐漸進(jìn)入了網(wǎng)絡(luò)化時代，使得信息的擴(kuò)散方式與擴(kuò)散途徑不斷發(fā)生變化。影響力最大化（Influence Maximization，IM）作為信息擴(kuò)散研究中的關(guān)鍵問題，旨在尋找社交網(wǎng)絡(luò)中最具影響力的用戶，最大限度地擴(kuò)大影響力。由于該問題在市場營銷、廣告發(fā)布、輿情預(yù)警以及社會安定等方面具有重要的應(yīng)用背景，近年來引起了學(xué)術(shù)界的廣泛研究。Kempe 等［1］首先將IM 問題建模為一個算法問題，證明其是NP-hard 問題，并提出了貪心算法。為了克服傳統(tǒng)貪心算法的低效性，近年來研究者提出了許多近似算法和啟發(fā)式方法，例如基于仿真的算法［2-3］、基于中心度的算法［4-5］、基于路徑的算法［6-7］和基于社區(qū)的算法［8-10］。盡管這些研究已經(jīng)取得了可喜的成果，但是這些算法都是針對同質(zhì)信息網(wǎng)絡(luò)設(shè)計的。同質(zhì)信息網(wǎng)絡(luò)僅考慮了一種對象類型和一種關(guān)系類型，而現(xiàn)實中的社會網(wǎng)絡(luò)包含了多種對象類型和對象之間的多種關(guān)系類型，因此，同質(zhì)信息網(wǎng)絡(luò)的建?？赡軙雎砸恍ο笾g通過不同類型的關(guān)系而形成的隱性關(guān)系。這些隱性關(guān)系可能有助于信息在網(wǎng)絡(luò)中更好地擴(kuò)散，因此，同時考慮多種對象類型以及對象之間的多種關(guān)系可能更有助于影響力最大化的研究。

異質(zhì)信息網(wǎng)絡(luò)（Heterogeneous Information Network，HIN）包含多種對象類型和多種關(guān)系類型，能夠更加精確合理地描述真實的社會網(wǎng)絡(luò)，刻畫不同類型對象之間的微妙關(guān)系，表達(dá)更豐富的語義信息。例如圖1 是異質(zhì)信息網(wǎng)絡(luò)DBLP（DataBase systems and Logic Programming）的網(wǎng)絡(luò)模式，其包含四種節(jié)點類型：作者（Author，A）、論文（Paper，P）、會議（Conference，C）、術(shù)語（Term，T）；六種關(guān)系類型：撰寫∕被撰寫、發(fā)表∕被發(fā)表、包含∕被包含。

圖1 DBLP網(wǎng)絡(luò)模式示意圖Fig.1 Schematic diagram of DBLP network mode

圖2 是DBLP 異質(zhì)信息網(wǎng)絡(luò)，異質(zhì)信息網(wǎng)絡(luò)中不同類型對象之間的異質(zhì)連接負(fù)載著不同的語義信息，在信息擴(kuò)散中起不同的作用，并且相互關(guān)聯(lián)、相互影響。例如A1P1C1表示作者A1撰寫的論文P1發(fā)表在會議C1上，若C1是影響力較高的會議，作者A1可能會因為在會議C1上發(fā)表了論文而提升個人的影響力，同樣若作者A1是學(xué)術(shù)界的知名人物，會議C1可能會因為作者A1在會議C1上發(fā)表了論文而提高會議的影響力。異質(zhì)信息網(wǎng)絡(luò)中同種類型對象之間可能通過不同的路徑產(chǎn)生不同程度的影響，例如作者A1與A3可以通過路徑A1P2A3連接，表示A1與A3合著一篇論文P2，同時也可以通過路徑A1P1T1P4A3連接，表示A1與A3發(fā)表的論文包含同一種術(shù)語T1，作者A1與A3通過蘊含著不同語義信息的路徑產(chǎn)生不同方面的影響。因此，異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息更有助于影響力最大化的研究。然而，由于異質(zhì)信息網(wǎng)絡(luò)具有復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)和豐富的語義信息，有效地利用異質(zhì)信息和探索豐富的語義是異質(zhì)信息網(wǎng)絡(luò)分析的難點。

圖2 DBLP異質(zhì)信息網(wǎng)絡(luò)Fig.2 DBLP HIN

有向無環(huán)圖（Directed Acyclic Graph，DAG）是一個無回路的有向圖，具有信息量大、表達(dá)力強的特點。首先，由于DAG 結(jié)構(gòu)是有向的，與異質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)的有向性一致，并且DAG 是一種圖結(jié)構(gòu)，表達(dá)能力優(yōu)于元路徑，因此，其可以更好地描述不同對象之間的復(fù)雜關(guān)系，保留豐富的異質(zhì)信息；其次，DAG 結(jié)構(gòu)是無環(huán)的，有利于表達(dá)影響擴(kuò)散過程中一個節(jié)點對另一個節(jié)點的線性影響，避免了環(huán)形結(jié)構(gòu)導(dǎo)致的路徑冗余，從而使得影響力度量結(jié)果小于真實值；最后，由于一個節(jié)點的影響范圍有限，因此將節(jié)點的影響限制在一個局部的DAG 中是可行的。一個小規(guī)模的DAG 易于快速處理，從而有利于實現(xiàn)在線性時間內(nèi)計算DAG 中的影響力。

本文提出了一種在異質(zhì)信息網(wǎng)絡(luò)中基于DAG 的影響力最大化算法（DAG-based Influence Maximization algorithm in heterogeneous information networks，DAGIM）。DAGIM 首先為節(jié)點構(gòu)建DAG 結(jié)構(gòu)，然后基于構(gòu)建的DAG 度量節(jié)點的影響力并且動態(tài)地選取最具影響力的節(jié)點，實現(xiàn)影響力最大化。DAG 結(jié)構(gòu)不僅可以描述不同類型對象之間的復(fù)雜關(guān)系，保留豐富的異質(zhì)信息，而且有利于降低異質(zhì)信息網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，從而更好地實現(xiàn)影響力最大化。

本文的主要貢獻(xiàn)如下：

1）提出了一種構(gòu)建DAG 的方法，為每個節(jié)點構(gòu)建一個DAG 結(jié)構(gòu)，該DAG 包含了節(jié)點對不同類型節(jié)點的主要影響力。

2）提出了基于DAG 結(jié)構(gòu)度量節(jié)點影響力的方法，分別考慮對不同類型節(jié)點的影響來度量節(jié)點的總影響力。

3）提出了DAGIM，DAGIM 根據(jù)不同的擴(kuò)散任務(wù)，采用邊際增益策略有針對性地選擇種子節(jié)點。

在3 個真實數(shù)據(jù)集上通過實驗驗證了DAGIM 的有效性和效率，探索了參數(shù)對算法性能的影響，并驗證了影響力度量的準(zhǔn)確性，最后驗證了邊權(quán)重對信息擴(kuò)散效果的影響。

1 相關(guān)工作

影響力最大化在2003 年首次被Kempe 等［1］建模為一個算法問題，該算法具有高精度的近似結(jié)果，但同時具有較高的時間復(fù)雜度，不能擴(kuò)展到規(guī)模較大的網(wǎng)絡(luò)上。為了克服傳統(tǒng)貪心算法的低效性，一系列啟發(fā)式算法被提出以解決這個問 題［2-12］：Leskovec 等［2］提出的CELF（Cost-Effective Lazy Forward selection）算法利用子模特性大幅提高了傳統(tǒng)貪心算法的時間效率，但是，由于該算法通過大量的蒙特卡羅仿真得到近似的目標(biāo)函數(shù)，因此不適合在大規(guī)模網(wǎng)絡(luò)中應(yīng)用；Chen 等［4］對傳統(tǒng)的貪心算法進(jìn)行改進(jìn)，提出NewGreedy 算法，進(jìn)一步減少其運行時間；Kim 等［6］提出了一種基于影響路徑的算法，考慮了多個影響路徑并假設(shè)它們相互獨立地傳播；Shang 等［9］利用社區(qū)結(jié)構(gòu)，通過考慮了節(jié)點的多鄰居勢來度量節(jié)點在社區(qū)中的影響力；Chen 等［11］證明了利用有向無環(huán)圖（DAG）計算影響在時間上與圖的大小成線性關(guān)系，并提出了一個針對線性閾值模型的可伸縮影響最大化算法；Qiu等［13］提出了一種有效的兩階段選擇的影響力最大化算法，并提出了折扣度下降技術(shù)和延遲前向技術(shù)選擇一定數(shù)量的候選節(jié)點；Qiu 等［14］提出了一種基于局部影響的全局選擇算法，提出了一種候選節(jié)點的兩階段過濾策略，大幅降低了運行時間，并提出了一種新的目標(biāo)函數(shù)來估計節(jié)點集的影響擴(kuò)散。盡管目前存在的影響力最大化算法都取得了可喜的結(jié)果，但這些算法大多數(shù)是針對同質(zhì)信息網(wǎng)絡(luò)設(shè)計的［15］，不能應(yīng)用于復(fù)雜的異質(zhì)信息網(wǎng)絡(luò)。

隨著在線社交媒體的快速發(fā)展，大量涌現(xiàn)的多功能社交媒體網(wǎng)站包含許多不同類型的對象和對象之間復(fù)雜的交互，傳統(tǒng)的同質(zhì)信息網(wǎng)絡(luò)的建模方法不再適用，因此，越來越多的研究人員開始將這些互連的多類型數(shù)據(jù)建模為異質(zhì)信息網(wǎng)絡(luò)，利用網(wǎng)絡(luò)中豐富的語義信息來設(shè)計網(wǎng)絡(luò)分析方法，并且應(yīng)用于很多數(shù)據(jù)挖掘任務(wù)［16］，目前關(guān)于異質(zhì)信息網(wǎng)絡(luò)的研究主要集中在聚類［17-18］、分類［19-20］、相似性搜索［21-22］和鏈路預(yù)測［23］等。與同質(zhì)信息網(wǎng)絡(luò)相比，異質(zhì)信息網(wǎng)絡(luò)包含了更豐富的語義信息和全面的結(jié)構(gòu)信息，為數(shù)據(jù)挖掘提供了新的機遇與挑戰(zhàn)。如何有效利用異質(zhì)信息和探索豐富語義是異質(zhì)信息網(wǎng)絡(luò)分析的主要難點。作為有效利用異質(zhì)信息和探索語義的工具，元路徑被廣泛應(yīng)用于異質(zhì)信息網(wǎng)絡(luò)分析。很多基于元路徑的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)挖掘問題已經(jīng)被廣泛研究。例如，Sun 等［17］基于元路徑選擇提出了一種聚類算法，并提出了一種有效的迭代算法PathSelClus 來學(xué)習(xí)聚類質(zhì)量和元路徑權(quán)值相互增強的模型。Kong 等［19］研究了異構(gòu)網(wǎng)絡(luò)中同類對象之間的集合分類問題，開發(fā)了一種基于元路徑的異構(gòu)集體分類方法，有效地將標(biāo)簽分配給通過不同元路徑相互連接的一組實例；Sun 等［21］提出了PathSim 算法，用于在異質(zhì)信息網(wǎng)絡(luò)中基于元路徑的Top-K 相似度搜索；Chen 等［24］提出了一種基于半監(jiān)督元路徑的社區(qū)檢測算法，利用譜方法分析異構(gòu)信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并利用非負(fù)矩陣分解進(jìn)行社區(qū)檢測。大量的研究成果證明元路徑能夠有效提取異質(zhì)信息網(wǎng)絡(luò)中的異質(zhì)信息，但是，基于元路徑的分析方法還存在一些缺點：首先這些元路徑要么需要領(lǐng)域?qū)＜业南闰炛R進(jìn)行選擇，要么需要擴(kuò)展計算來合并所有小于預(yù)先確定長度的元路徑；其次路徑只是簡單的線性序列，對復(fù)雜網(wǎng)絡(luò)的表達(dá)能力有限。Liu 等［22］提出一種信息網(wǎng)絡(luò)中基于距離感知DAG的鄰近搜索算法，不僅能降低圖的復(fù)雜性，而且能夠保留豐富的信息。

盡管異質(zhì)信息網(wǎng)絡(luò)深受廣大研究者的青睞，但是關(guān)于異質(zhì)信息網(wǎng)絡(luò)中信息擴(kuò)散的研究相對較少，并且主要集中在預(yù)測任務(wù)中。例如Molaei 等［25］提出了一種異構(gòu)深度擴(kuò)散模型，利用元路徑作為網(wǎng)絡(luò)中的主要實體，以全局端到端視角，遍歷元路徑，通過一個連續(xù)的潛在表示來學(xué)習(xí)網(wǎng)絡(luò)的功能異質(zhì)結(jié)構(gòu)，然后在生成的特征上使用深度學(xué)習(xí)架構(gòu)來預(yù)測網(wǎng)絡(luò)中的擴(kuò)散過程。Liu 等［26］提出了一個生成圖形模型，利用與網(wǎng)絡(luò)中每個用戶相關(guān)的異質(zhì)鏈接信息和文本內(nèi)容來挖掘主題級的影響力，研究了影響的傳播和聚集機制：保守傳播和非保守傳播，并且分析了直接影響和間接影響，從而在異質(zhì)網(wǎng)絡(luò)中發(fā)現(xiàn)一些有趣的影響模式，提高了用戶行為預(yù)測的準(zhǔn)確性等。Li 等［27］提出了一種新的基于符號預(yù)測的異質(zhì)信息網(wǎng)絡(luò)行為預(yù)測模型，同時捕捉了用戶的社交鏈接（包括有標(biāo)簽鏈接和無標(biāo)簽鏈接）和用戶行為，提高預(yù)測的準(zhǔn)確性。針對異質(zhì)信息網(wǎng)絡(luò)中影響力最大化問題，Li 等［28］考慮了人的個體行為來模擬影響傳播，利用人節(jié)點對好友的激活具有不同的影響概率，構(gòu)造基于人的影響圖，并提出基于熵的啟發(fā)式方法來識別影響中的傳播者，以使影響傳播最大化。Wang等［29］首先闡述了異質(zhì)網(wǎng)絡(luò)中影響最大化問題，并提出了一種協(xié)同排序框架來同時選擇不同類型的種子集。Deng 等［30］提出了一個衡量影響模型來捕獲具有異質(zhì)性的社會影響，分別研究了不同因素的影響，并提出了一種影響最大化貪心算法選擇種子節(jié)點。目前，異質(zhì)信息網(wǎng)絡(luò)中影響力最大化的研究成果相對有限，有較大的研究空間。由于異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜且多樣，因此在異質(zhì)信息網(wǎng)絡(luò)中研究影響力最大化存在更多的挑戰(zhàn)和更高的復(fù)雜度。

2 相關(guān)概念

定義1異質(zhì)信息網(wǎng)絡(luò)［31］。一個異質(zhì)信息網(wǎng)絡(luò)定義為一個包含兩個映射函數(shù)φ和π的有向圖G=(V，E，T，R)，其中：V={v1，v2，…，vn}是節(jié)點集，E={e1，e2，…，en}是節(jié)點之間的邊集，T={t1，t2，…，tn}是節(jié)點類型集，|T|>1，R={r1，r2，…，rn}是邊類型集，|R|>1。φ：V→T是節(jié)點到節(jié)點類型的映射，π：E→R是邊到邊類型的映射。

定義2邊權(quán)重［32］。假設(shè)G中存在n種類型的邊，即R={r1，r2，…，rn}，同種類型的邊具有相同的權(quán)重，即?ri∈R，ri類型邊的權(quán)重 為wi∈(0，1)。若?u，v∈V，e(u，v) ∈E且π(e(u，v))=ri，則e(u，v)的邊權(quán)重定義為w(u，v)=wi。

定義 3路徑權(quán)重［32］。假 設(shè)P(v1，vm)=表示節(jié)點v1到節(jié)點vm的一條路徑，則P(v1，vm) 的路徑權(quán)重定義 為W(P(v1，vm))=w(v1，v2)×w(v2，v3)× …×w(vm-1，vm)。

證明 邊權(quán)重wi∈(0，1)表示節(jié)點之間的影響概率，由定義3 可知路徑權(quán)重W(P(v1，vm))隨著路徑的增長而減小，因此，節(jié)點v1對節(jié)點vm的影響概率隨著路徑的增長而減小。

定義4出、入鄰居。給定異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)，若節(jié)點u∈V到節(jié)點v∈Vu存在有向邊，則節(jié)點v稱為節(jié)點u的出鄰居，用Nout(u)表示節(jié)點u的出鄰居集；若節(jié)點v∈Vu到節(jié)點u存在有向邊，則節(jié)點v稱為節(jié)點u的入鄰居，用Nin(u)表示節(jié)點u的入鄰居集。若v∈Nout(u)，那么節(jié)點u對節(jié)點v的影響概率表示為w(u，v)；若v∈Nin(u)，那么節(jié)點v對節(jié)點u的影響概率表示為w(v，u)。

問題定義 給定一個異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)，本文的目標(biāo)是在度量節(jié)點影響力時利用異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息，考慮一個節(jié)點對不同類型節(jié)點的影響，根據(jù)不同的擴(kuò)散任務(wù)，有針對性地選擇一組最具影響的節(jié)點S，在特定的擴(kuò)散模型下，最大化總激活節(jié)點數(shù)S*：

解決上述問題的關(guān)鍵是如何度量節(jié)點的影響，并選擇影響力最大的節(jié)點作為種子節(jié)點。

由于異質(zhì)信息網(wǎng)絡(luò)中包含多種節(jié)點類型，不同類型的節(jié)點具有不同的性質(zhì)，并且它們的影響力代表著不同的含義，在信息擴(kuò)散中起不同的作用。因此，本文在研究異質(zhì)信息網(wǎng)絡(luò)中的影響力最大化問題時，將根據(jù)不同的目標(biāo)對象選擇不同的種子節(jié)點，從而更好地實現(xiàn)影響力最大化。例如，在DBLP 網(wǎng)絡(luò)中，作者對論文產(chǎn)生影響的同時，通過論文的連接也會對會議、術(shù)語和作者產(chǎn)生一定影響，假設(shè)信息擴(kuò)散任務(wù)是影響更多的作者，那么本文將會選擇對作者影響力最大的節(jié)點作為種子節(jié)點進(jìn)行信息擴(kuò)散。

3 DAGIM

DAGIM 首先為節(jié)點構(gòu)建DAG 結(jié)構(gòu)，然后基于構(gòu)建的DAG 度量節(jié)點的影響力并且動態(tài)地選取最具影響力的節(jié)點，實現(xiàn)影響力最大化。

3.1 構(gòu)建DAG

為了度量節(jié)點的影響力，本文首先為每個節(jié)點u∈V構(gòu)建一個DAG。構(gòu)建方法為：將節(jié)點u作為DAG 的源節(jié)點，查找節(jié)點u的出鄰居，將出鄰居添加到DAG 中，然后再查找出鄰居的出鄰居，并將它們添加到DAG 中，不斷循環(huán)此過程。在此過程中，若不加任何約束條件，最終構(gòu)建的DAG 可能非常大。根據(jù)性質(zhì)1 可知，隨著路徑的增長，節(jié)點u對一些遠(yuǎn)距離節(jié)點的影響非常小，并且構(gòu)建大規(guī)模的DAG 結(jié)構(gòu)非常耗時。因此，本文在構(gòu)建DAG 的過程中將引入一個參數(shù)λ(λ∈[0，1])來約束節(jié)點之間的路徑權(quán)重，從而控制DAG 的大小，使得節(jié)點u一定影響范圍內(nèi)的鄰居節(jié)點添加到DAG中，保證構(gòu)建的DAG 涵蓋節(jié)點u對其他節(jié)點的主要影響，而忽略節(jié)點u的次要影響。圖3 所示展示了一個異質(zhì)信息網(wǎng)絡(luò)中節(jié)點A1的DAG 結(jié)構(gòu)。DGA 結(jié)構(gòu)清晰地描述了A1與其他節(jié)點之間的關(guān)系，例如A1與A3合著過論文，作者A1在會議C2上發(fā)表過論文等，A1與A5之間可以通過6 條路徑到達(dá)。DAG 結(jié)構(gòu)針對一個節(jié)點將異質(zhì)信息局部化，保留了與其相關(guān)的主要信息，相較于整個異質(zhì)信息網(wǎng)絡(luò)，節(jié)點之間的關(guān)系更加明確和清晰。

圖3 加權(quán)路徑的HIN和節(jié)點A1的DAG結(jié)構(gòu)Fig.3 HIN with weighting path and DAG structure of A1

在構(gòu)建Du(X，Y)的過程中，本文將節(jié)點u的DAG 表示為Du(X，Y)，其中X表示節(jié)點集，Y表示邊集。首先將源節(jié)點u添加到X中，然后從節(jié)點u開始查找它的出鄰居v∈Nout(u)，若X中不包含v且節(jié)點u到節(jié)點v的路徑權(quán)重W(P(u，v))≥λ，則將v添加到X中，添加X中的節(jié)點到節(jié)點v的有向邊到Y(jié)中，然后依次查找Nout(u)的出鄰居節(jié)點，不斷重復(fù)上述操作。隨著路徑長度不斷增長，路徑權(quán)重逐漸減小，當(dāng)W(P(u，v)) <λ時，循環(huán)結(jié)束。本文所提的異質(zhì)信息網(wǎng)絡(luò)中構(gòu)建DAG 的方法如算法1 所示。

算法1 構(gòu)建Du(X，Y)。

3.2 影響力度量

異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的節(jié)點，一個節(jié)點可能對不同類型的節(jié)點產(chǎn)生不同程度的影響。因此，本文將分別考慮對不同類型節(jié)點的影響來度量節(jié)點的總影響力。由于Du(X，Y)包含了節(jié)點u一定影響范圍內(nèi)的鄰居節(jié)點，所以Du(X，Y)涵蓋了節(jié)點u對不同類型節(jié)點的大部分影響力。本節(jié)考慮如何基于Du(X，Y)度量節(jié)點u對這些節(jié)點的影響力，從而得到節(jié)點u的總影響力。

在Du(X，Y)中，若u是激活節(jié)點，利用DAG 結(jié)構(gòu)的特點，節(jié)點u可以通過蘊含不同語義信息的路徑達(dá)到Du(X，Y)中的任意一個節(jié)點。由于到達(dá)不同節(jié)點的路徑條數(shù)、路徑長度及路徑上邊的類型均不相同，因此u對不同節(jié)點產(chǎn)生的影響程度不同。對于?v∈Xu，假設(shè)節(jié)點u到節(jié)點v存在l條路徑，節(jié)點u到節(jié)點v的影響概率記為IPu(v)，則IPu(v)的計算方式如式（2）所示：

算法2 描述了計算節(jié)點u對Du(X，Y)中節(jié)點的影響概率過程。

算法2 計算節(jié)點u對Du(X，Y)中節(jié)點的影響概率。

一般而言，Du(X，Y)中包含了多種類型的節(jié)點，而節(jié)點u對每種類型節(jié)點的影響意義不同，因此本文將分別計算對不同類型節(jié)點的影響力。節(jié)點u對t∈T類型節(jié)點的影響力表示為Inft(u)，如式（3）所示：

設(shè)Du(X，Y)中包含n種節(jié)點類型T={t1，t2，…，tn}，本文將結(jié)合對n種類型節(jié)點的影響來度量節(jié)點u的總影響力，用Inf(u)表示，如式（4）所示：

其中αi等于1 或0，若αi=1，則表示度量節(jié)點u的影響力時考慮了對ti類型節(jié)點的影響，否則就忽略了對ti類型節(jié)點的影響。

例在圖3（b）中，A1到C1之間存在一條路徑，即，A1對C1的影響概率為IPA1(C1)=0.5× 0.2=0.1；A1對會議的影響 為Inf會議(A1)=IPA1(C1)+IPA1(C2)=0.1+0.1=0.2；設(shè)αi=1，A1的總影響力為Inf(A1)=Inf論文(A1)+Inf會議(A1)+Inf術(shù)語(A1)+Inf作者(A1)=1.2+0.2+0.15+0.65=2.2。

3.3 DAGIM描述

DAGIM 首先構(gòu)建DAG 結(jié)構(gòu)來度量節(jié)點的影響力，然后采用邊際增益策略選擇種子節(jié)點，選擇一個影響力最大的節(jié)點作為種子節(jié)點后，去除其他節(jié)點與其重疊的影響，重新計算剩余節(jié)點的影響力，從中再選擇一個影響力最大的節(jié)點作為下一個種子節(jié)點，重復(fù)上述操作，直到選取一定數(shù)量的種子節(jié)點。

算法3 DAGIM。

輸入G(V，E，T，R)，參數(shù)λ，種子節(jié)點數(shù)量k；

輸出 種子集S。

算法3 描述了DAGIM 的偽代碼，首先運用算法1 構(gòu)建Du(X，Y)，然后利用算法2 計算節(jié)點u對Du(X，Y)中的每個節(jié)點的影響概率IPu(v)，利用式（3）、（4）計算節(jié)點u的影響力Inf(u)。為了避免影響力重復(fù)計算，算法3 采用邊際增益策略選擇k個種子節(jié)點。最后，這些種子節(jié)點通過特定的擴(kuò)散模型在網(wǎng)絡(luò)中進(jìn)行擴(kuò)散，使影響范圍達(dá)到最大。

算法1 的時間復(fù)雜度為O(nd)，算法2 的時間復(fù)雜度為O(nml)，因此，DAGIM 的時間復(fù)雜度為O(nd+nml+k)，其中n表示異質(zhì)信息網(wǎng)絡(luò)中節(jié)點的數(shù)量n=|V|；d表示節(jié)點的平均度；m表示DAG 中節(jié)點的平均數(shù)量；l表示DAG 中節(jié)點的平均路徑數(shù)量；k表示所選取的種子節(jié)點的數(shù)量k=|S|。

4 實驗評估

4.1 實驗準(zhǔn)備

數(shù)據(jù)集 本文使用了3 個真實的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)集（DBLP 數(shù)據(jù)集、Yelp 數(shù)據(jù)集和Amazon 數(shù)據(jù)集）驗證DAGIM的性能。DBLP 數(shù)據(jù)集包含4 種對象類型和三種關(guān)系類型，Yelp 數(shù)據(jù)集包含4 種對象類型和4 種關(guān)系類型，Amazon 數(shù)據(jù)集包含5 種對象和4 種關(guān)系類型，3 個數(shù)據(jù)集的詳細(xì)描述如表1 所示。

表1 數(shù)據(jù)集詳細(xì)信息Tab.1 Dataset detailed information

對比算法 為了驗證所提DAGIM 的有效性，本文采用了PageRank［12］、Degree［12］、基于元路徑的信息熵（Meta-Pathbased Information Entropy，MPIE）［33］和局部有向無環(huán)圖（Local Directed Acyclic Graph，LDAG）［11］作為對比算法。PageRank 算法度量每個節(jié)點的重要程度，然后選擇PageRank值高的節(jié)點作為種子節(jié)點。Degree 算法是一種基于度中心的影響力度量方法。MPIE 算法是面向異質(zhì)信息網(wǎng)絡(luò)的方法，該方法首先通過元路徑將異質(zhì)網(wǎng)絡(luò)轉(zhuǎn)化為同質(zhì)網(wǎng)絡(luò)，然后度量節(jié)點的直接影響力和間接影響力，最后結(jié)合兩種影響力選取種子節(jié)點。LDAG 算法是基于局部DAG 的影響力最大化算法。Degree 算法、PageRank 算法和LADG 算法均采用文獻(xiàn)中最佳的參數(shù)值。由于這些算法只針對一種類型的節(jié)點和一種類型的邊，所以在實驗中運行對比算法時不區(qū)分節(jié)點和邊的類型，但運行DAGIM 和對比實驗結(jié)果時，需要區(qū)分節(jié)點和邊的類型。

由于異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的節(jié)點，不同類型的節(jié)點具有不同的性質(zhì)，并且它們的影響力代表著不同的含義，在信息擴(kuò)散中起不同的作用，因此，將不同類型節(jié)點的影響力進(jìn)行比較是不合理且沒有意義的。為了使實驗結(jié)果有意義，在實驗過程中，本文選擇了一種節(jié)點類型作為研究對象，即DBLP 網(wǎng)絡(luò)中的作者節(jié)點，Yelp 和Amazon 網(wǎng)絡(luò)中的用戶節(jié)點。其他類型節(jié)點的比較與此類似，不再贅述。

擴(kuò)散模型 本文采用線性閾值模型（Linear Threshold，LT）作為擴(kuò)散模型。對于LT 模型，每個非激活節(jié)點有一個[0，1]范圍的激活閾值，本文將每個節(jié)點的入度邊的權(quán)值歸一化，使它們的和為1，若非激活節(jié)點的已激活鄰居對其的影響力總和超過該閾值，則該節(jié)點被激活。

評價指標(biāo) 影響范圍（Influence Spread）［10］是一種廣泛使用的評價指標(biāo)，定義為擴(kuò)散結(jié)束時能夠成功激活的節(jié)點數(shù)，Influence Spread值越大表明算法的性能越好，因此本文使用Influence Spread 作為算法性能的評價指標(biāo)。為了消除結(jié)果的偶然性，通過執(zhí)行10 000 次蒙特卡羅（Monte Carlo，MC）仿真來估計影響擴(kuò)散值，并隨機設(shè)置每個節(jié)點的激活閾值。本文采用時間（Time）作為算法效率的評價指標(biāo)，其數(shù)值越小表示算法的運行時間越短，算法的運行效率越高。

4.2 實驗結(jié)果

4.2.1 有效性驗證

對于Degree 算法、PageRank 算法、MPIE 算法和LDAG 算法，實驗中將所有邊權(quán)重設(shè)為0.5。DAGIM 區(qū)分不同的節(jié)點類型和不同的邊類型，DBLP 網(wǎng)絡(luò)中不同類型的邊權(quán)重分別設(shè)為wAP=0.5，wPC=0.3，wPT=0.2，Yelp 網(wǎng)絡(luò)中不同類型的邊權(quán)重設(shè)為wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2，Amazon 網(wǎng)絡(luò)中，wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1。在影響力擴(kuò)散階段，本文將使用LT 模型作為擴(kuò)散模型，并將邊權(quán)值歸一化，避免了權(quán)值的不同導(dǎo)致結(jié)果的差異性。

四種算法在DBLP、Yelp 和Amazon 數(shù)據(jù)集上針對不同初始種子節(jié)點數(shù)目K最終激活的作者節(jié)點和用戶節(jié)點數(shù)如圖4所示。

圖4 不同算法影響范圍的對比Fig.4 Impact range comparison of different algorithms

從圖4 可以看出，在三個數(shù)據(jù)集上，DAGIM 表現(xiàn)最好，Degree 算法和PageRank 算法表現(xiàn)最差，LDAG 算法優(yōu)于這兩種算法，說明DAG 結(jié)構(gòu)有助于準(zhǔn)確地度量節(jié)點的影響力，區(qū)分節(jié)點和邊的類型能夠提升節(jié)點影響力度量的精度。MPIE算法在DBLP 和Yelp 這兩個數(shù)據(jù)集上表現(xiàn)不佳，主要原因可能是MPIE 算法實驗表現(xiàn)依賴于元路徑的選取，使用多條元路徑引入了噪聲，同時影響了網(wǎng)絡(luò)結(jié)構(gòu)的完整性，導(dǎo)致節(jié)點影響力的度量不夠準(zhǔn)確。在Amazon 數(shù)據(jù)集中，MPIE 算法的性能和DAGIM 接近，是因為選取了比較合適的元路徑，對節(jié)點影響力的度量較為準(zhǔn)確。

4.2.2 效率對比

為了比較評價不同算法的效率，本節(jié)將種子節(jié)點數(shù)量K分別設(shè)為{10，20，30，40，50}，對比不同算法選出K個種子節(jié)點的運行時間。表2 展示了DBLP、Yelp 以及Amazon 數(shù)據(jù)集上的運行時間。

表2 不同算法在三個數(shù)據(jù)集上的運行時間比較Tab.2 Running time comparison of different algorithms on three datasets

從表2 可以看出，PageRank 算法和Degree 算法具有較高的時間效率，但是從圖4 可知它們的性能相對較差。MPIE算法的時間復(fù)雜度也較高，因為該算法需要從異質(zhì)網(wǎng)絡(luò)中提取同質(zhì)子網(wǎng)，然后進(jìn)行節(jié)點信息熵的計算。DAGIM 和LDAG算法都是基于DAG 結(jié)構(gòu)的算法，構(gòu)建節(jié)點的DAG 需要花費一定的時間，因此，這兩種算法效率相對較低；但是DAGIM的效率高于LDAG 算法，這是由于DAGIM 只是針對特定類型的節(jié)點構(gòu)建DAG，而不是對所有類型的節(jié)點都構(gòu)建。此外，從表2 中可以看出，所有算法的運行時間隨著K值的增大而增加，但是增加幅度不大。這是因為：Degree 和PageRank 時間復(fù)雜度較低，屬于高效率算法，受參數(shù)K值的影響較??；MPIE 算法的運行時間大部分消耗在了同質(zhì)網(wǎng)絡(luò)的提取以及節(jié)點熵值的計算，所以受參數(shù)K值的影響也較?。籇AGIM 和LDAG 算法的運行時間主要消耗在DAG 的構(gòu)建，選擇種子節(jié)點消耗的時間相對較少，因此，這兩種算法對參數(shù)K的變化不敏感。

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

DAGIM 中參數(shù)λ控制著DAG 的大小，隨著λ值的減小，DAG 涵蓋的鄰居節(jié)點越多，并且DAG 的規(guī)模越大且越復(fù)雜，這可能有助于更全面地度量節(jié)點的影響力。因此，為了探索DAG 結(jié)構(gòu)如何影響DAGIM 性能，本文將算法參數(shù)λ為分別設(shè)置為{0.1，0.08，0.06，0.04，0.02，0.008，0.005，0.001}進(jìn)行實驗。實驗結(jié)果如圖5 所示，從中可以看出隨著λ值的減小，在DBLP 以及Yelp 這兩個數(shù)據(jù)集上Influence Spread 的值逐漸增大，這表明復(fù)雜的DAG 結(jié)構(gòu)涵蓋了更多的異質(zhì)信息，有助于更準(zhǔn)確地度量節(jié)點的影響力，從而提升影響力最大化效果。在Amazon 數(shù)據(jù)集上實驗結(jié)果較為特殊，參數(shù)λ在取前六個值時，Influence Spread 的變化趨勢和其余兩個數(shù)據(jù)集保持一致，但在λ={0.005，0.001}時，Influence Spread 的值出現(xiàn)下降。這是由于Amazon 數(shù)據(jù)的數(shù)據(jù)分布比較緊密，隨著λ值的減小，DAG 涵蓋的節(jié)點增多，產(chǎn)生了噪聲，導(dǎo)致節(jié)點影響力的度量不夠準(zhǔn)確、Influence Spread值減小的情況發(fā)生。同時，構(gòu)建復(fù)雜的DAG 需要花費大量的時間，并且從圖中可以看出當(dāng)λ值減小到一定程度時，Influence Spread值幾乎保持不變，這是因為隨著路徑長度的增長，節(jié)點對一些遠(yuǎn)距離節(jié)點的影響微乎其微，不足以激活它們。因此，有必要選擇適當(dāng)?shù)摩藖硗瑫r兼顧DAGIM 的有效性和效率。

圖5 參數(shù)λ對影響范圍的影響Fig.5 Effect of parameterλ on influence spread

4.2.4 影響力度量的準(zhǔn)確性

異質(zhì)信息網(wǎng)絡(luò)中包含多種節(jié)點類型，一個節(jié)點對不同類型的節(jié)點產(chǎn)生不同程度的影響。為了評價通過多種類型節(jié)點的影響來度量節(jié)點影響力是否有助于更準(zhǔn)確地度量節(jié)點的影響力，將使用DAGIM 在三個數(shù)據(jù)集上進(jìn)行測試。

在度量節(jié)點影響力時，本文采用了兩種度量方式，僅考慮對一種類型節(jié)點的影響和考慮對所有類型節(jié)點的影響，分別用INFone 和INFmult 表示。實驗考慮DBLP 網(wǎng)絡(luò)中的作者節(jié)點、Yelp 和Amazon 網(wǎng)絡(luò)中的用戶節(jié)點作為研究對象，因此，對于僅考慮一種類型節(jié)點的情況，DBLP 選擇作者節(jié)點，Yelp 和Amazon 選擇用戶節(jié)點。根據(jù)影響力的度量結(jié)果，選出K（K={10，20，30，40，50}）個種子節(jié)點并比較它們的Influence Spread值。實驗結(jié)果如圖6 所示，從結(jié)果中可以看出，INFmult 的Influence Spread值高于INFone，并且兩者之間的差距隨著K值增大而增大，說明考慮多種類型節(jié)點的影響有利于準(zhǔn)確地度量節(jié)點的影響力。

圖6 不同影響力度量方式的對比Fig.6 Comparison of different measures of influence

4.2.5 邊權(quán)重的影響

異質(zhì)信息網(wǎng)絡(luò)中包含多種類型的邊，而不同類型的邊在信息擴(kuò)散中起不同的作用，本節(jié)將使用DAGIM 在三個異質(zhì)信息網(wǎng)絡(luò)中探索不同類型的邊在信息擴(kuò)散任務(wù)中的重要程度。本文假設(shè)所有類型的邊權(quán)重和為1：對于DBLP 數(shù)據(jù)集，wAP+wPC+wPT=1；對 于Yelp 數(shù)據(jù)集，wUU+wUB+wBCat+wBCit=1；對于Amazon 數(shù)據(jù)集，wUI+wIB+wIC+wIV=1。本節(jié)將設(shè)置多組不同的邊權(quán)重組合進(jìn)行實驗，選出K=50 個種子節(jié)點并比較它們的Influence Spread。實驗結(jié)果如圖7所示。

圖7 邊權(quán)重對影響范圍的影響Fig.7 Effect of edge weights on influence spread

從圖7（a）可以觀察到，在DBLP 網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時，邊權(quán)重wAP是三者中的最大值，這表明作者與論文之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread 達(dá)到最小值時，邊權(quán)重wPT是三者中的最大值，這表明論文與術(shù)語之間的關(guān)系在信息擴(kuò)散中的影響相對較小。當(dāng)wAP=0.5，wPC=0.3，wPT=0.2 時，Influence Spread值達(dá)到最大，因此本文在DBLP 數(shù)據(jù)集上驗證算法的有效性實驗中采用了這組參數(shù)。從圖7（b）中可以觀察到，在Yelp網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時，邊權(quán)重wUB是最大值，這表明用戶與商業(yè)之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread值較小時，邊權(quán)重wBCat或wBCit是最大值，這表明商業(yè)與領(lǐng)域之間的關(guān)系、商業(yè)與城市之間的關(guān)系在信息擴(kuò)散中的影響相對較小。當(dāng)wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2 時，Influence Spread值達(dá)到最大，因此本文在數(shù)據(jù)集上驗證算法的有效性實驗中采用了這組參數(shù)。在Amazon 網(wǎng)絡(luò)中，當(dāng)Influence Spread 達(dá)到最大值時，邊權(quán)重wUI是最大值，這表明用戶與商品之間的關(guān)系在信息擴(kuò)散中起關(guān)鍵作用。當(dāng)Influence Spread值較小時，邊權(quán)重wIV是最大值，這表明商品與評價之間的關(guān)系在信息擴(kuò)散中的影響相對較小。當(dāng)wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1 時，Influence Spread值達(dá)到最大，因此本文在Amazon 數(shù)據(jù)集上驗證算法的有效性實驗中采用了這組參數(shù)。

5 結(jié)語

本文提出了一種在異質(zhì)信息網(wǎng)絡(luò)中基于DAG 的影響力最大化算法DAGIM，該算法首先為每個節(jié)點構(gòu)建DAG，然后利用DAG 結(jié)構(gòu)度量節(jié)點的影響力，根據(jù)度量結(jié)果動態(tài)地選擇影響力最大的節(jié)點作為種子節(jié)點，從而實現(xiàn)影響力最大化。由于DAGIM 中控制DAG 結(jié)構(gòu)大小的最佳參數(shù)是通過多次實驗得到的，在未來研究中，將考慮根據(jù)不同的網(wǎng)絡(luò)結(jié)構(gòu)自適應(yīng)地選擇最佳參數(shù)。此外，針對不同的數(shù)據(jù)集，本文根據(jù)先驗知識給不同類型的邊賦予不同的權(quán)重，在未來研究中，可以考慮通過表征學(xué)習(xí)得到不同類型邊的權(quán)重，使得邊權(quán)重更加真實有效。