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

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

0 引言

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

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

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

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

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

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

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

本文的主要貢獻如下：

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

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

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

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

1 相關工作

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

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

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

2 相關概念

定義1異質信息網(wǎng)絡［31］。一個異質信息網(wǎng)絡定義為一個包含兩個映射函數(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邊權重［32］。假設G中存在n種類型的邊，即R={r1，r2，…，rn}，同種類型的邊具有相同的權重，即?ri∈R，ri類型邊的權重 為wi∈(0，1)。若?u，v∈V，e(u，v) ∈E且π(e(u，v))=ri，則e(u，v)的邊權重定義為w(u，v)=wi。

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

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

定義4出、入鄰居。給定異質信息網(wǎng)絡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)。

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

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

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

3 DAGIM

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

3.1 構建DAG

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

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

在構建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的路徑權重W(P(u，v))≥λ，則將v添加到X中，添加X中的節(jié)點到節(jié)點v的有向邊到Y中，然后依次查找Nout(u)的出鄰居節(jié)點，不斷重復上述操作。隨著路徑長度不斷增長，路徑權重逐漸減小，當W(P(u，v)) <λ時，循環(huán)結束。本文所提的異質信息網(wǎng)絡中構建DAG 的方法如算法1 所示。

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

3.2 影響力度量

異質信息網(wǎng)絡中包含多種類型的節(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é)點u可以通過蘊含不同語義信息的路徑達到Du(X，Y)中的任意一個節(jié)點。由于到達不同節(jié)點的路徑條數(shù)、路徑長度及路徑上邊的類型均不相同，因此u對不同節(jié)點產(chǎn)生的影響程度不同。對于?v∈Xu，假設節(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）所示：

設Du(X，Y)中包含n種節(jié)點類型T={t1，t2，…，tn}，本文將結合對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；設αi=1，A1的總影響力為Inf(A1)=Inf論文(A1)+Inf會議(A1)+Inf術語(A1)+Inf作者(A1)=1.2+0.2+0.15+0.65=2.2。

3.3 DAGIM描述

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

算法3 DAGIM。

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

輸出 種子集S。

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

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

4 實驗評估

4.1 實驗準備

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

表1 數(shù)據(jù)集詳細信息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 算法是面向異質信息網(wǎng)絡的方法，該方法首先通過元路徑將異質網(wǎng)絡轉化為同質網(wǎng)絡，然后度量節(jié)點的直接影響力和間接影響力，最后結合兩種影響力選取種子節(jié)點。LDAG 算法是基于局部DAG 的影響力最大化算法。Degree 算法、PageRank 算法和LADG 算法均采用文獻中最佳的參數(shù)值。由于這些算法只針對一種類型的節(jié)點和一種類型的邊，所以在實驗中運行對比算法時不區(qū)分節(jié)點和邊的類型，但運行DAGIM 和對比實驗結果時，需要區(qū)分節(jié)點和邊的類型。

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

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

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

4.2 實驗結果

4.2.1 有效性驗證

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

四種算法在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é)點的影響力，區(qū)分節(jié)點和邊的類型能夠提升節(jié)點影響力度量的精度。MPIE算法在DBLP 和Yelp 這兩個數(shù)據(jù)集上表現(xiàn)不佳，主要原因可能是MPIE 算法實驗表現(xiàn)依賴于元路徑的選取，使用多條元路徑引入了噪聲，同時影響了網(wǎng)絡結構的完整性，導致節(jié)點影響力的度量不夠準確。在Amazon 數(shù)據(jù)集中，MPIE 算法的性能和DAGIM 接近，是因為選取了比較合適的元路徑，對節(jié)點影響力的度量較為準確。

4.2.2 效率對比

為了比較評價不同算法的效率，本節(jié)將種子節(jié)點數(shù)量K分別設為{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算法的時間復雜度也較高，因為該算法需要從異質網(wǎng)絡中提取同質子網(wǎng)，然后進行節(jié)點信息熵的計算。DAGIM 和LDAG算法都是基于DAG 結構的算法，構建節(jié)點的DAG 需要花費一定的時間，因此，這兩種算法效率相對較低；但是DAGIM的效率高于LDAG 算法，這是由于DAGIM 只是針對特定類型的節(jié)點構建DAG，而不是對所有類型的節(jié)點都構建。此外，從表2 中可以看出，所有算法的運行時間隨著K值的增大而增加，但是增加幅度不大。這是因為：Degree 和PageRank 時間復雜度較低，屬于高效率算法，受參數(shù)K值的影響較?。籑PIE 算法的運行時間大部分消耗在了同質網(wǎng)絡的提取以及節(jié)點熵值的計算，所以受參數(shù)K值的影響也較小；DAGIM 和LDAG 算法的運行時間主要消耗在DAG 的構建，選擇種子節(jié)點消耗的時間相對較少，因此，這兩種算法對參數(shù)K的變化不敏感。

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

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

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

4.2.4 影響力度量的準確性

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

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

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

4.2.5 邊權重的影響

異質信息網(wǎng)絡中包含多種類型的邊，而不同類型的邊在信息擴散中起不同的作用，本節(jié)將使用DAGIM 在三個異質信息網(wǎng)絡中探索不同類型的邊在信息擴散任務中的重要程度。本文假設所有類型的邊權重和為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é)將設置多組不同的邊權重組合進行實驗，選出K=50 個種子節(jié)點并比較它們的Influence Spread。實驗結果如圖7所示。

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

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

5 結語

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