异质信息网络中基于有向无环图的影响力最大化算法

吴晴晴，周丽华*，寸轩懿，杜国王，姜懿庭

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

0 引言

随着互联网技术的迅速发展，信息逐渐进入了网络化时代，使得信息的扩散方式与扩散途径不断发生变化。影响力最大化（Influence Maximization，IM）作为信息扩散研究中的关键问题，旨在寻找社交网络中最具影响力的用户，最大限度地扩大影响力。由于该问题在市场营销、广告发布、舆情预警以及社会安定等方面具有重要的应用背景，近年来引起了学术界的广泛研究。Kempe 等［1］首先将IM 问题建模为一个算法问题，证明其是NP-hard 问题，并提出了贪心算法。为了克服传统贪心算法的低效性，近年来研究者提出了许多近似算法和启发式方法，例如基于仿真的算法［2-3］、基于中心度的算法［4-5］、基于路径的算法［6-7］和基于社区的算法［8-10］。尽管这些研究已经取得了可喜的成果，但是这些算法都是针对同质信息网络设计的。同质信息网络仅考虑了一种对象类型和一种关系类型，而现实中的社会网络包含了多种对象类型和对象之间的多种关系类型，因此，同质信息网络的建模可能会忽略一些对象之间通过不同类型的关系而形成的隐性关系。这些隐性关系可能有助于信息在网络中更好地扩散，因此，同时考虑多种对象类型以及对象之间的多种关系可能更有助于影响力最大化的研究。

异质信息网络（Heterogeneous Information Network，HIN）包含多种对象类型和多种关系类型，能够更加精确合理地描述真实的社会网络，刻画不同类型对象之间的微妙关系，表达更丰富的语义信息。例如图1 是异质信息网络DBLP（DataBase systems and Logic Programming）的网络模式，其包含四种节点类型：作者（Author，A）、论文（Paper，P）、会议（Conference，C）、术语（Term，T）；六种关系类型：撰写∕被撰写、发表∕被发表、包含∕被包含。

图1 DBLP网络模式示意图Fig.1 Schematic diagram of DBLP network mode

图2 是DBLP 异质信息网络，异质信息网络中不同类型对象之间的异质连接负载着不同的语义信息，在信息扩散中起不同的作用，并且相互关联、相互影响。例如A1P1C1表示作者A1撰写的论文P1发表在会议C1上，若C1是影响力较高的会议，作者A1可能会因为在会议C1上发表了论文而提升个人的影响力，同样若作者A1是学术界的知名人物，会议C1可能会因为作者A1在会议C1上发表了论文而提高会议的影响力。异质信息网络中同种类型对象之间可能通过不同的路径产生不同程度的影响，例如作者A1与A3可以通过路径A1P2A3连接，表示A1与A3合著一篇论文P2，同时也可以通过路径A1P1T1P4A3连接，表示A1与A3发表的论文包含同一种术语T1，作者A1与A3通过蕴含着不同语义信息的路径产生不同方面的影响。因此，异质信息网络中丰富的语义信息更有助于影响力最大化的研究。然而，由于异质信息网络具有复杂的网络结构和丰富的语义信息，有效地利用异质信息和探索丰富的语义是异质信息网络分析的难点。

图2 DBLP异质信息网络Fig.2 DBLP HIN

有向无环图（Directed Acyclic Graph，DAG）是一个无回路的有向图，具有信息量大、表达力强的特点。首先，由于DAG 结构是有向的，与异质信息网络结构的有向性一致，并且DAG 是一种图结构，表达能力优于元路径，因此，其可以更好地描述不同对象之间的复杂关系，保留丰富的异质信息；其次，DAG 结构是无环的，有利于表达影响扩散过程中一个节点对另一个节点的线性影响，避免了环形结构导致的路径冗余，从而使得影响力度量结果小于真实值；最后，由于一个节点的影响范围有限，因此将节点的影响限制在一个局部的DAG 中是可行的。一个小规模的DAG 易于快速处理，从而有利于实现在线性时间内计算DAG 中的影响力。

本文提出了一种在异质信息网络中基于DAG 的影响力最大化算法（DAG-based Influence Maximization algorithm in heterogeneous information networks，DAGIM）。DAGIM 首先为节点构建DAG 结构，然后基于构建的DAG 度量节点的影响力并且动态地选取最具影响力的节点，实现影响力最大化。DAG 结构不仅可以描述不同类型对象之间的复杂关系，保留丰富的异质信息，而且有利于降低异质信息网络结构的复杂性，从而更好地实现影响力最大化。

本文的主要贡献如下：

1）提出了一种构建DAG 的方法，为每个节点构建一个DAG 结构，该DAG 包含了节点对不同类型节点的主要影响力。

2）提出了基于DAG 结构度量节点影响力的方法，分别考虑对不同类型节点的影响来度量节点的总影响力。

3）提出了DAGIM，DAGIM 根据不同的扩散任务，采用边际增益策略有针对性地选择种子节点。

在3 个真实数据集上通过实验验证了DAGIM 的有效性和效率，探索了参数对算法性能的影响，并验证了影响力度量的准确性，最后验证了边权重对信息扩散效果的影响。

1 相关工作

影响力最大化在2003 年首次被Kempe 等［1］建模为一个算法问题，该算法具有高精度的近似结果，但同时具有较高的时间复杂度，不能扩展到规模较大的网络上。为了克服传统贪心算法的低效性，一系列启发式算法被提出以解决这个问 题［2-12］：Leskovec 等［2］提出的CELF（Cost-Effective Lazy Forward selection）算法利用子模特性大幅提高了传统贪心算法的时间效率，但是，由于该算法通过大量的蒙特卡罗仿真得到近似的目标函数，因此不适合在大规模网络中应用；Chen 等［4］对传统的贪心算法进行改进，提出NewGreedy 算法，进一步减少其运行时间；Kim 等［6］提出了一种基于影响路径的算法，考虑了多个影响路径并假设它们相互独立地传播；Shang 等［9］利用社区结构，通过考虑了节点的多邻居势来度量节点在社区中的影响力；Chen 等［11］证明了利用有向无环图（DAG）计算影响在时间上与图的大小成线性关系，并提出了一个针对线性阈值模型的可伸缩影响最大化算法；Qiu等［13］提出了一种有效的两阶段选择的影响力最大化算法，并提出了折扣度下降技术和延迟前向技术选择一定数量的候选节点；Qiu 等［14］提出了一种基于局部影响的全局选择算法，提出了一种候选节点的两阶段过滤策略，大幅降低了运行时间，并提出了一种新的目标函数来估计节点集的影响扩散。尽管目前存在的影响力最大化算法都取得了可喜的结果，但这些算法大多数是针对同质信息网络设计的［15］，不能应用于复杂的异质信息网络。

随着在线社交媒体的快速发展，大量涌现的多功能社交媒体网站包含许多不同类型的对象和对象之间复杂的交互，传统的同质信息网络的建模方法不再适用，因此，越来越多的研究人员开始将这些互连的多类型数据建模为异质信息网络，利用网络中丰富的语义信息来设计网络分析方法，并且应用于很多数据挖掘任务［16］，目前关于异质信息网络的研究主要集中在聚类［17-18］、分类［19-20］、相似性搜索［21-22］和链路预测［23］等。与同质信息网络相比，异质信息网络包含了更丰富的语义信息和全面的结构信息，为数据挖掘提供了新的机遇与挑战。如何有效利用异质信息和探索丰富语义是异质信息网络分析的主要难点。作为有效利用异质信息和探索语义的工具，元路径被广泛应用于异质信息网络分析。很多基于元路径的异质信息网络数据挖掘问题已经被广泛研究。例如，Sun 等［17］基于元路径选择提出了一种聚类算法，并提出了一种有效的迭代算法PathSelClus 来学习聚类质量和元路径权值相互增强的模型。Kong 等［19］研究了异构网络中同类对象之间的集合分类问题，开发了一种基于元路径的异构集体分类方法，有效地将标签分配给通过不同元路径相互连接的一组实例；Sun 等［21］提出了PathSim 算法，用于在异质信息网络中基于元路径的Top-K 相似度搜索；Chen 等［24］提出了一种基于半监督元路径的社区检测算法，利用谱方法分析异构信息网络的拓扑结构，并利用非负矩阵分解进行社区检测。大量的研究成果证明元路径能够有效提取异质信息网络中的异质信息，但是，基于元路径的分析方法还存在一些缺点：首先这些元路径要么需要领域专家的先验知识进行选择，要么需要扩展计算来合并所有小于预先确定长度的元路径；其次路径只是简单的线性序列，对复杂网络的表达能力有限。Liu 等［22］提出一种信息网络中基于距离感知DAG的邻近搜索算法，不仅能降低图的复杂性，而且能够保留丰富的信息。

尽管异质信息网络深受广大研究者的青睐，但是关于异质信息网络中信息扩散的研究相对较少，并且主要集中在预测任务中。例如Molaei 等［25］提出了一种异构深度扩散模型，利用元路径作为网络中的主要实体，以全局端到端视角，遍历元路径，通过一个连续的潜在表示来学习网络的功能异质结构，然后在生成的特征上使用深度学习架构来预测网络中的扩散过程。Liu 等［26］提出了一个生成图形模型，利用与网络中每个用户相关的异质链接信息和文本内容来挖掘主题级的影响力，研究了影响的传播和聚集机制：保守传播和非保守传播，并且分析了直接影响和间接影响，从而在异质网络中发现一些有趣的影响模式，提高了用户行为预测的准确性等。Li 等［27］提出了一种新的基于符号预测的异质信息网络行为预测模型，同时捕捉了用户的社交链接（包括有标签链接和无标签链接）和用户行为，提高预测的准确性。针对异质信息网络中影响力最大化问题，Li 等［28］考虑了人的个体行为来模拟影响传播，利用人节点对好友的激活具有不同的影响概率，构造基于人的影响图，并提出基于熵的启发式方法来识别影响中的传播者，以使影响传播最大化。Wang等［29］首先阐述了异质网络中影响最大化问题，并提出了一种协同排序框架来同时选择不同类型的种子集。Deng 等［30］提出了一个衡量影响模型来捕获具有异质性的社会影响，分别研究了不同因素的影响，并提出了一种影响最大化贪心算法选择种子节点。目前，异质信息网络中影响力最大化的研究成果相对有限，有较大的研究空间。由于异质信息网络的结构复杂且多样，因此在异质信息网络中研究影响力最大化存在更多的挑战和更高的复杂度。

2 相关概念

定义1异质信息网络［31］。一个异质信息网络定义为一个包含两个映射函数φ和π的有向图G=(V，E，T，R)，其中：V={v1，v2，…，vn}是节点集，E={e1，e2，…，en}是节点之间的边集，T={t1，t2，…，tn}是节点类型集，|T|>1，R={r1，r2，…，rn}是边类型集，|R|>1。φ：V→T是节点到节点类型的映射，π：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)=表示节点v1到节点vm的一条路径，则P(v1，vm) 的路径权重定义 为W(P(v1，vm))=w(v1，v2)×w(v2，v3)× …×w(vm-1，vm)。

证明 边权重wi∈(0，1)表示节点之间的影响概率，由定义3 可知路径权重W(P(v1，vm))随着路径的增长而减小，因此，节点v1对节点vm的影响概率随着路径的增长而减小。

定义4出、入邻居。给定异质信息网络G=(V，E，T，R)，若节点u∈V到节点v∈Vu存在有向边，则节点v称为节点u的出邻居，用Nout(u)表示节点u的出邻居集；若节点v∈Vu到节点u存在有向边，则节点v称为节点u的入邻居，用Nin(u)表示节点u的入邻居集。若v∈Nout(u)，那么节点u对节点v的影响概率表示为w(u，v)；若v∈Nin(u)，那么节点v对节点u的影响概率表示为w(v，u)。

问题定义 给定一个异质信息网络G=(V，E，T，R)，本文的目标是在度量节点影响力时利用异质信息网络中丰富的语义信息，考虑一个节点对不同类型节点的影响，根据不同的扩散任务，有针对性地选择一组最具影响的节点S，在特定的扩散模型下，最大化总激活节点数S*：

解决上述问题的关键是如何度量节点的影响，并选择影响力最大的节点作为种子节点。

由于异质信息网络中包含多种节点类型，不同类型的节点具有不同的性质，并且它们的影响力代表着不同的含义，在信息扩散中起不同的作用。因此，本文在研究异质信息网络中的影响力最大化问题时，将根据不同的目标对象选择不同的种子节点，从而更好地实现影响力最大化。例如，在DBLP 网络中，作者对论文产生影响的同时，通过论文的连接也会对会议、术语和作者产生一定影响，假设信息扩散任务是影响更多的作者，那么本文将会选择对作者影响力最大的节点作为种子节点进行信息扩散。

3 DAGIM

DAGIM 首先为节点构建DAG 结构，然后基于构建的DAG 度量节点的影响力并且动态地选取最具影响力的节点，实现影响力最大化。

3.1 构建DAG

为了度量节点的影响力，本文首先为每个节点u∈V构建一个DAG。构建方法为：将节点u作为DAG 的源节点，查找节点u的出邻居，将出邻居添加到DAG 中，然后再查找出邻居的出邻居，并将它们添加到DAG 中，不断循环此过程。在此过程中，若不加任何约束条件，最终构建的DAG 可能非常大。根据性质1 可知，随着路径的增长，节点u对一些远距离节点的影响非常小，并且构建大规模的DAG 结构非常耗时。因此，本文在构建DAG 的过程中将引入一个参数λ(λ∈[0，1])来约束节点之间的路径权重，从而控制DAG 的大小，使得节点u一定影响范围内的邻居节点添加到DAG中，保证构建的DAG 涵盖节点u对其他节点的主要影响，而忽略节点u的次要影响。图3 所示展示了一个异质信息网络中节点A1的DAG 结构。DGA 结构清晰地描述了A1与其他节点之间的关系，例如A1与A3合著过论文，作者A1在会议C2上发表过论文等，A1与A5之间可以通过6 条路径到达。DAG 结构针对一个节点将异质信息局部化，保留了与其相关的主要信息，相较于整个异质信息网络，节点之间的关系更加明确和清晰。

图3 加权路径的HIN和节点A1的DAG结构Fig.3 HIN with weighting path and DAG structure of A1

在构建Du(X，Y)的过程中，本文将节点u的DAG 表示为Du(X，Y)，其中X表示节点集，Y表示边集。首先将源节点u添加到X中，然后从节点u开始查找它的出邻居v∈Nout(u)，若X中不包含v且节点u到节点v的路径权重W(P(u，v))≥λ，则将v添加到X中，添加X中的节点到节点v的有向边到Y中，然后依次查找Nout(u)的出邻居节点，不断重复上述操作。随着路径长度不断增长，路径权重逐渐减小，当W(P(u，v)) <λ时，循环结束。本文所提的异质信息网络中构建DAG 的方法如算法1 所示。

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

3.2 影响力度量

异质信息网络中包含多种类型的节点，一个节点可能对不同类型的节点产生不同程度的影响。因此，本文将分别考虑对不同类型节点的影响来度量节点的总影响力。由于Du(X，Y)包含了节点u一定影响范围内的邻居节点，所以Du(X，Y)涵盖了节点u对不同类型节点的大部分影响力。本节考虑如何基于Du(X，Y)度量节点u对这些节点的影响力，从而得到节点u的总影响力。

在Du(X，Y)中，若u是激活节点，利用DAG 结构的特点，节点u可以通过蕴含不同语义信息的路径达到Du(X，Y)中的任意一个节点。由于到达不同节点的路径条数、路径长度及路径上边的类型均不相同，因此u对不同节点产生的影响程度不同。对于∀v∈Xu，假设节点u到节点v存在l条路径，节点u到节点v的影响概率记为IPu(v)，则IPu(v)的计算方式如式（2）所示：

算法2 描述了计算节点u对Du(X，Y)中节点的影响概率过程。

算法2 计算节点u对Du(X，Y)中节点的影响概率。

一般而言，Du(X，Y)中包含了多种类型的节点，而节点u对每种类型节点的影响意义不同，因此本文将分别计算对不同类型节点的影响力。节点u对t∈T类型节点的影响力表示为Inft(u)，如式（3）所示：

设Du(X，Y)中包含n种节点类型T={t1，t2，…，tn}，本文将结合对n种类型节点的影响来度量节点u的总影响力，用Inf(u)表示，如式（4）所示：

其中αi等于1 或0，若αi=1，则表示度量节点u的影响力时考虑了对ti类型节点的影响，否则就忽略了对ti类型节点的影响。

例在图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 结构来度量节点的影响力，然后采用边际增益策略选择种子节点，选择一个影响力最大的节点作为种子节点后，去除其他节点与其重叠的影响，重新计算剩余节点的影响力，从中再选择一个影响力最大的节点作为下一个种子节点，重复上述操作，直到选取一定数量的种子节点。

算法3 DAGIM。

输入G(V，E，T，R)，参数λ，种子节点数量k；

输出 种子集S。

算法3 描述了DAGIM 的伪代码，首先运用算法1 构建Du(X，Y)，然后利用算法2 计算节点u对Du(X，Y)中的每个节点的影响概率IPu(v)，利用式（3）、（4）计算节点u的影响力Inf(u)。为了避免影响力重复计算，算法3 采用边际增益策略选择k个种子节点。最后，这些种子节点通过特定的扩散模型在网络中进行扩散，使影响范围达到最大。

算法1 的时间复杂度为O(nd)，算法2 的时间复杂度为O(nml)，因此，DAGIM 的时间复杂度为O(nd+nml+k)，其中n表示异质信息网络中节点的数量n=|V|；d表示节点的平均度；m表示DAG 中节点的平均数量；l表示DAG 中节点的平均路径数量；k表示所选取的种子节点的数量k=|S|。

4 实验评估

4.1 实验准备

数据集 本文使用了3 个真实的异质信息网络数据集（DBLP 数据集、Yelp 数据集和Amazon 数据集）验证DAGIM的性能。DBLP 数据集包含4 种对象类型和三种关系类型，Yelp 数据集包含4 种对象类型和4 种关系类型，Amazon 数据集包含5 种对象和4 种关系类型，3 个数据集的详细描述如表1 所示。

表1 数据集详细信息Tab.1 Dataset detailed information

对比算法 为了验证所提DAGIM 的有效性，本文采用了PageRank［12］、Degree［12］、基于元路径的信息熵（Meta-Pathbased Information Entropy，MPIE）［33］和局部有向无环图（Local Directed Acyclic Graph，LDAG）［11］作为对比算法。PageRank 算法度量每个节点的重要程度，然后选择PageRank值高的节点作为种子节点。Degree 算法是一种基于度中心的影响力度量方法。MPIE 算法是面向异质信息网络的方法，该方法首先通过元路径将异质网络转化为同质网络，然后度量节点的直接影响力和间接影响力，最后结合两种影响力选取种子节点。LDAG 算法是基于局部DAG 的影响力最大化算法。Degree 算法、PageRank 算法和LADG 算法均采用文献中最佳的参数值。由于这些算法只针对一种类型的节点和一种类型的边，所以在实验中运行对比算法时不区分节点和边的类型，但运行DAGIM 和对比实验结果时，需要区分节点和边的类型。

由于异质信息网络中包含多种类型的节点，不同类型的节点具有不同的性质，并且它们的影响力代表着不同的含义，在信息扩散中起不同的作用，因此，将不同类型节点的影响力进行比较是不合理且没有意义的。为了使实验结果有意义，在实验过程中，本文选择了一种节点类型作为研究对象，即DBLP 网络中的作者节点，Yelp 和Amazon 网络中的用户节点。其他类型节点的比较与此类似，不再赘述。

扩散模型 本文采用线性阈值模型（Linear Threshold，LT）作为扩散模型。对于LT 模型，每个非激活节点有一个[0，1]范围的激活阈值，本文将每个节点的入度边的权值归一化，使它们的和为1，若非激活节点的已激活邻居对其的影响力总和超过该阈值，则该节点被激活。

评价指标 影响范围（Influence Spread）［10］是一种广泛使用的评价指标，定义为扩散结束时能够成功激活的节点数，Influence Spread值越大表明算法的性能越好，因此本文使用Influence Spread 作为算法性能的评价指标。为了消除结果的偶然性，通过执行10 000 次蒙特卡罗（Monte Carlo，MC）仿真来估计影响扩散值，并随机设置每个节点的激活阈值。本文采用时间（Time）作为算法效率的评价指标，其数值越小表示算法的运行时间越短，算法的运行效率越高。

4.2 实验结果

4.2.1 有效性验证

对于Degree 算法、PageRank 算法、MPIE 算法和LDAG 算法，实验中将所有边权重设为0.5。DAGIM 区分不同的节点类型和不同的边类型，DBLP 网络中不同类型的边权重分别设为wAP=0.5，wPC=0.3，wPT=0.2，Yelp 网络中不同类型的边权重设为wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2，Amazon 网络中，wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1。在影响力扩散阶段，本文将使用LT 模型作为扩散模型，并将边权值归一化，避免了权值的不同导致结果的差异性。

四种算法在DBLP、Yelp 和Amazon 数据集上针对不同初始种子节点数目K最终激活的作者节点和用户节点数如图4所示。

图4 不同算法影响范围的对比Fig.4 Impact range comparison of different algorithms

从图4 可以看出，在三个数据集上，DAGIM 表现最好，Degree 算法和PageRank 算法表现最差，LDAG 算法优于这两种算法，说明DAG 结构有助于准确地度量节点的影响力，区分节点和边的类型能够提升节点影响力度量的精度。MPIE算法在DBLP 和Yelp 这两个数据集上表现不佳，主要原因可能是MPIE 算法实验表现依赖于元路径的选取，使用多条元路径引入了噪声，同时影响了网络结构的完整性，导致节点影响力的度量不够准确。在Amazon 数据集中，MPIE 算法的性能和DAGIM 接近，是因为选取了比较合适的元路径，对节点影响力的度量较为准确。

4.2.2 效率对比

为了比较评价不同算法的效率，本节将种子节点数量K分别设为{10，20，30，40，50}，对比不同算法选出K个种子节点的运行时间。表2 展示了DBLP、Yelp 以及Amazon 数据集上的运行时间。

表2 不同算法在三个数据集上的运行时间比较Tab.2 Running time comparison of different algorithms on three datasets

从表2 可以看出，PageRank 算法和Degree 算法具有较高的时间效率，但是从图4 可知它们的性能相对较差。MPIE算法的时间复杂度也较高，因为该算法需要从异质网络中提取同质子网，然后进行节点信息熵的计算。DAGIM 和LDAG算法都是基于DAG 结构的算法，构建节点的DAG 需要花费一定的时间，因此，这两种算法效率相对较低；但是DAGIM的效率高于LDAG 算法，这是由于DAGIM 只是针对特定类型的节点构建DAG，而不是对所有类型的节点都构建。此外，从表2 中可以看出，所有算法的运行时间随着K值的增大而增加，但是增加幅度不大。这是因为：Degree 和PageRank 时间复杂度较低，属于高效率算法，受参数K值的影响较小；MPIE 算法的运行时间大部分消耗在了同质网络的提取以及节点熵值的计算，所以受参数K值的影响也较小；DAGIM 和LDAG 算法的运行时间主要消耗在DAG 的构建，选择种子节点消耗的时间相对较少，因此，这两种算法对参数K的变化不敏感。

4.2.3 算法参数的影响

DAGIM 中参数λ控制着DAG 的大小，随着λ值的减小，DAG 涵盖的邻居节点越多，并且DAG 的规模越大且越复杂，这可能有助于更全面地度量节点的影响力。因此，为了探索DAG 结构如何影响DAGIM 性能，本文将算法参数λ为分别设置为{0.1，0.08，0.06，0.04，0.02，0.008，0.005，0.001}进行实验。实验结果如图5 所示，从中可以看出随着λ值的减小，在DBLP 以及Yelp 这两个数据集上Influence Spread 的值逐渐增大，这表明复杂的DAG 结构涵盖了更多的异质信息，有助于更准确地度量节点的影响力，从而提升影响力最大化效果。在Amazon 数据集上实验结果较为特殊，参数λ在取前六个值时，Influence Spread 的变化趋势和其余两个数据集保持一致，但在λ={0.005，0.001}时，Influence Spread 的值出现下降。这是由于Amazon 数据的数据分布比较紧密，随着λ值的减小，DAG 涵盖的节点增多，产生了噪声，导致节点影响力的度量不够准确、Influence Spread值减小的情况发生。同时，构建复杂的DAG 需要花费大量的时间，并且从图中可以看出当λ值减小到一定程度时，Influence Spread值几乎保持不变，这是因为随着路径长度的增长，节点对一些远距离节点的影响微乎其微，不足以激活它们。因此，有必要选择适当的λ来同时兼顾DAGIM 的有效性和效率。

图5 参数λ对影响范围的影响Fig.5 Effect of parameterλ on influence spread

4.2.4 影响力度量的准确性

异质信息网络中包含多种节点类型，一个节点对不同类型的节点产生不同程度的影响。为了评价通过多种类型节点的影响来度量节点影响力是否有助于更准确地度量节点的影响力，将使用DAGIM 在三个数据集上进行测试。

在度量节点影响力时，本文采用了两种度量方式，仅考虑对一种类型节点的影响和考虑对所有类型节点的影响，分别用INFone 和INFmult 表示。实验考虑DBLP 网络中的作者节点、Yelp 和Amazon 网络中的用户节点作为研究对象，因此，对于仅考虑一种类型节点的情况，DBLP 选择作者节点，Yelp 和Amazon 选择用户节点。根据影响力的度量结果，选出K（K={10，20，30，40，50}）个种子节点并比较它们的Influence Spread值。实验结果如图6 所示，从结果中可以看出，INFmult 的Influence Spread值高于INFone，并且两者之间的差距随着K值增大而增大，说明考虑多种类型节点的影响有利于准确地度量节点的影响力。

图6 不同影响力度量方式的对比Fig.6 Comparison of different measures of influence

4.2.5 边权重的影响

异质信息网络中包含多种类型的边，而不同类型的边在信息扩散中起不同的作用，本节将使用DAGIM 在三个异质信息网络中探索不同类型的边在信息扩散任务中的重要程度。本文假设所有类型的边权重和为1：对于DBLP 数据集，wAP+wPC+wPT=1；对 于Yelp 数据集，wUU+wUB+wBCat+wBCit=1；对于Amazon 数据集，wUI+wIB+wIC+wIV=1。本节将设置多组不同的边权重组合进行实验，选出K=50 个种子节点并比较它们的Influence Spread。实验结果如图7所示。

图7 边权重对影响范围的影响Fig.7 Effect of edge weights on influence spread

从图7（a）可以观察到，在DBLP 网络中，当Influence Spread 达到最大值时，边权重wAP是三者中的最大值，这表明作者与论文之间的关系在信息扩散中起关键作用。当Influence Spread 达到最小值时，边权重wPT是三者中的最大值，这表明论文与术语之间的关系在信息扩散中的影响相对较小。当wAP=0.5，wPC=0.3，wPT=0.2 时，Influence Spread值达到最大，因此本文在DBLP 数据集上验证算法的有效性实验中采用了这组参数。从图7（b）中可以观察到，在Yelp网络中，当Influence Spread 达到最大值时，边权重wUB是最大值，这表明用户与商业之间的关系在信息扩散中起关键作用。当Influence Spread值较小时，边权重wBCat或wBCit是最大值，这表明商业与领域之间的关系、商业与城市之间的关系在信息扩散中的影响相对较小。当wUU=0.3，wUB=0.4，wBCat=0.1，wBCit=0.2 时，Influence Spread值达到最大，因此本文在数据集上验证算法的有效性实验中采用了这组参数。在Amazon 网络中，当Influence Spread 达到最大值时，边权重wUI是最大值，这表明用户与商品之间的关系在信息扩散中起关键作用。当Influence Spread值较小时，边权重wIV是最大值，这表明商品与评价之间的关系在信息扩散中的影响相对较小。当wUI=0.4，wIB=0.3，wIC=0.2，wIV=0.1 时，Influence Spread值达到最大，因此本文在Amazon 数据集上验证算法的有效性实验中采用了这组参数。

5 结语

本文提出了一种在异质信息网络中基于DAG 的影响力最大化算法DAGIM，该算法首先为每个节点构建DAG，然后利用DAG 结构度量节点的影响力，根据度量结果动态地选择影响力最大的节点作为种子节点，从而实现影响力最大化。由于DAGIM 中控制DAG 结构大小的最佳参数是通过多次实验得到的，在未来研究中，将考虑根据不同的网络结构自适应地选择最佳参数。此外，针对不同的数据集，本文根据先验知识给不同类型的边赋予不同的权重，在未来研究中，可以考虑通过表征学习得到不同类型边的权重，使得边权重更加真实有效。