异质信息网络中基于网络嵌入的影响力最大化

杨宇迪，周丽华,2，杜国王，邹星竹，丁海燕

（1.云南大学 信息学院，云南 昆明 650504;2.云南大学 滇池学院，云南 昆明 650228）

影响力最大化问题是指在特定的扩散模型下，寻找一组初始扩散节点使影响扩散范围最大的优化问题。目前，影响力最大化算法主要分为两类：贪心算法[1-3]和启发式算法[4-6]，其中贪心算法主要用于提高算法的精确度；启发式算法主要用于解决实际问题以提高算法效率。Kempe 等[7]首次形式化定义了影响力最大化问题，并提出了一个贪心算法，其近似值约为 1−/e−ε，但是该算法的效率较低。Leskovec 等[8]提出了CELF 算法，Goyal 等[9]提出了CELF++算法，通过实验发现该算法比CELF 快35%～55%。接着，为了解决贪心算法的效率问题，Tang 等[10]提出一种基于跳的算法，该算法可以在常用的扩散模型(独立级联模型和线性阈值模型)下轻松应用于十亿规模的网络。Peng 等[11]认为个体之间的影响有直接影响和间接影响，社会影响力的强弱取决于个体之间的关系、网络距离、时间、网络和个体的复杂性和不确定性。但这些算法通常仅将社会网络看作同质网络，忽略了社会网络的异质性，即网络中包含不同类型的对象和链接。在异质信息网络(heterogeneous information network，HIN)中，影响力可以通过不同的对象和链接进行扩散，从而获得更广泛的影响范围。

尽管异质信息网络丰富的结构和语义信息有助于实现影响力扩散范围最大化，但也给影响力的分析带来了挑战。目前，HIN 中的数据挖掘任务主要集中于相似性搜索[12-13]、聚类[14-15]、分类[16-17]等，很少有研究者关注HIN 中的社会影响力分析。为了建模HIN 中的社会影响力，Yang 等[18]提出了一种基于元路径的信息熵模型MPIE，利用多条元路径从异质信息网络中提取多个同质信息网络，在每个同质信息网络中基于熵度量直接影响力和间接影响力，然后融合多个同质信息网络中的影响力度量HIN 中的社会影响力。尽管MPIE 取得了一定的效果，但该算法需选择特定类型的节点设定元路径，不能灵活地度量HIN 中不同类型节点间的影响。

HIN 嵌入[19-21]旨在通过基于节点的结构特性保留不同类型节点之间的邻近性来学习各个不同类型的节点的低维表示，而这些低维表示可直接应用于网络分析任务，比如节点分类、聚类以及链路预测等。由于HIN 嵌入将不同类型节点映射于同一向量空间，用同一空间的低维向量来描述不同类型的节点，不仅概括了网络的重要结构特征，而且学习到的嵌入具有同质性，易于使用和集成。最近几年，异质信息网络的表征学习受到了研究者的广泛关注。

因此，本文提出了一种异质网络中基于网络嵌入的影响力最大化模型IMNE。IMNE 首先利用网络嵌入学习HIN 中所有节点在同一向量空间的低维表征，保持不同类型节点在同一度量空间，然后基于HIN 原始的网络拓扑结构，扩展传统的信息熵模型，考虑多种影响因素，度量HIN 中不同类型节点的社会影响力并选择最具影响力的节点作为初始扩散节点，最后，选择特定的信息扩散模型实现HIN 中的影响力最大化。本文工作一方面扩展了HIN 嵌入的应用，另一方面将Peng 等[1]所提的模型扩展到了HIN。

1 相关符号和问题定义

定义1 异质信息网络[22]。异质信息网络通常被定义为一个带有对象类型映射函数ϕ:V→A和边类型映射函数φ:E→R的无向图G=(V,E)，其中每个对象v∈V属于一个特定的对象类型ϕ(v)∈A，每条边e∈E属于一个特定的关系类型φ(e)∈R，且 |A|+|R|>2。

定义2 HIN 中的影响力最大化。给定一个异质信息网络G={V,E}，δ(Vs)是将种子集Vs映射到受种子集影响的对象数量的影响函数，异质信息网络中影响力最大化的目的是选择一组最具影响力的种子集且该种子集可以最大化影响力的扩散范围，即

2 IMNE 模型

本节将详细介绍异质网络中基于网络嵌入的影响力最大化模型IMNE。

首先以图1 为例说明本文动机。如果将学术网络视为同质网络，该网络中仅Lily 和Bob、Ada 和Tom 间存在边，此时，若将Ada 作为初始扩散节点，其将仅影响Tom 一个节点，即影响范围为1。然而，若将学术网络视为HIN，如图2 所示，该网络中包含3 种类型的节点，论文和会议之间存在发表/被发表关系，论文和论文之间存在引用/被引用关系，作者和论文之间存在撰写/被撰写关系，考虑不同类型节点通过不同关系互相影响，令Ada 作为初始扩散节点，则P2 和P6 两篇论文会受到Ada 的直接影响，其次，由于Ada 和Tom 之间通过路径“Tom-P2-Ada(合作)”相关联，Ada 和Mary 通过“Ada-P6-C1-P5-Mary(共同参加会议)”相关联，所以Ada 也可间接影响Tom 和Mary。相比同质网络，Ada 的影响范围更广。

图1 同质网络示例Fig.1 Example of a homogeneous network

图2 异质网络示例Fig.2 Example of a HIN

IMNE 模型的整体框架如图3 所示。首先，IMNE 从HIN(图3(a))中学习各种类型节点的嵌入(图3(b))，然后，扩展信息熵模型度量社会影响力，并选取最具影响力的节点作为种子集(图3(c))；最后在特定扩散模型下实现影响力最大化(图3(d))。

图3 IMNE 模型的具体框架Fig.3 The specific framework of the IMNE model

2.1 HIN 嵌入

本文使用HIN2Vec 模型[23]实现HIN 嵌入。HIN2Vec 模型旨在通过最大程度地联合预测节点之间关系的可能性来学习节点向量和关系向量。模型采用一对节点x和y，以及某种关系r∈R的one-hot 向量x、y和r作为输入，通过神经网络将x、y和r转化为隐藏层中的潜向量中关系和节点的语义含义不同，所以关系向量r通过正则化转化为限制r的值在0 到1 之间)，在输出层通过Sigmoid实现逻辑分类(⊙ 表示逐元素相乘)。通过HIN2Vec，HIN 中的每个节点转换为同一向量空间的低维度潜在表示，在捕获和表示HIN 中的丰富信息的同时，有效避免了HIN 中不同类型节点和关系的不兼容性，便于度量不同类型节点的社会影响力以选取初始扩散种子集。

2.2 影响力度量

HIN 中，一个对象的社会影响力通常不仅体现于紧密的直接联系，还体现在节点的间接联系。HIN 中社会影响的相关定义如下：

定义3 直接/间接影响力。给定异质信息网络G中的对象u、v，若对象u和v之间有边相连，即euv=1，则Deu(v)表示对象u和对象v间的直接影响力；若对象u和v之间没有边直接相连，即euv=0，则IIu(v)表示对象u和对象v间的间接影响力。

定义4 全局影响力。给定异质信息网络G中的节点u，若节点u在整个网络中具有影响力，那么Iu被定义为节点u在G上的全局影响力。

全局影响力与直接/间接影响力有着密切关系。如果对象具有很强的直接和间接影响力，则该对象通常在社会网络中具有较强的全局影响力。IMNE 算法考虑了不同类型对象之间的影响(如作者对论文的影响或论文对作者的影响)，通常具有影响力的对象其相关行为也具有影响力。例如，在数据挖掘领域具有较强影响力的研究人员，他发表的论文在数据挖掘领域通常也具有较高的影响力。

2.2.1 直接影响力度量

在社交网络中，影响力与许多潜在因素相互作用，如相似性和相关性，相似对象之间的相互影响往往更强，例如，在学术网络中，作者i与作者j、作者m均有合作，若作者i与作者j的研究领域更相似，那么作者i和j间的相互影响往往更强。同时，度中心性作为图论中度量节点相对重要性的评价指标，也是社会影响力的潜在影响因素。

根据HIN 嵌入得到的各类型节点的嵌入信息，可获得HIN 中各类型节点的相似度 Simij，即：

式中：ei和ej分别对应对象i和j的潜在表征向量；(·) 表示向量的点积；∥e∥ 表示向量的长度。

HIN 网络嵌入不仅将不同类型节点映射于同一空间便于度量不同类型节点间的社会影响，还保留HIN 原始结构，故给定异质信息网络G，令Ni表示对象i的度，对象i的直接影响力的定义如下：

其中i≠j且i≠k。

2.2.2 间接影响力度量

除了直接影响力，对象之间往往也具有某种间接影响，例如，在学术网络中，具有影响力的作者可以通过论文或会议影响其他作者。

给定异质信息网络G，令Nik表示对象i和k间公共对象的数量，则对象i和k之间的间接影响力描述如下：

令Mi表示对象i的多跳连接对象的数量，对象i的间接影响力IIi的定义如式(5)所示。

2.2.3 全局影响力度量

根据直接影响力和间接影响力的度量可得，对象i的全局影响力如式(6)所示。

式中：α和 β分别表示直接影响力 Dei和间接影响力IIi的权重，且 α+β=1。

2.3 IMNE 算法描述

算法1 IMNE 算法

该算法中语句3～11 用以选择最具影响力的k个对象作为种子节点集S。IMNE 算法的复杂度为O(m+nd+nlog(k))，其中n表示异质信息网络中对象的数量，n=|V|；k表示最具影响力的对象数量；d表示一跳链接对象的平均数量；m表示异质信息网络中边的总数，m=|E|。

3 实验评估

3.1 实验准备

3.1.1 数据集

本文实验部分共使用了3 个真实的HIN 数据集，来自两种不同领域，其中4-area 数据集来自学术领域，Yelp 数据集和Amazon 数据集来自商业领域。4-area[24]是从DBLP 网站收集的子数据集，涉及数据库、数据挖掘、机器学习和信息检索4 个研究领域，共包含20 场会议、排名前5 000的作者、14 328 篇论文和8 789 个术语，其中作者与论文、论文与会议、论文与术语之间存在联系。Yelp 数据集记录了1 268 条用户对坐落于47 个城市、3 种类型的2 614 条商户的评分情况，其中用户与商户、商户与城市、商户与类型之间存在联系。Amazon 是一种商业网络，该网络记录了6 170 个用户对来自334 个品牌旗下的22 种类别共2 753 项产品的3 857 条评论情况，其中用户与产品、产品与评论、产品与类别、产品与品牌之间存在联系。以上3 个数据集，除了来自不同的领域，还具有不同的稀疏性，其中Yelp 的数据分布最稀疏，Amazon 数据分布最密集。在实验过程中选择HIN2Vec[13]模型嵌入HIN 数据集，使不同类型节点处于同一度量空间。

3.1.2 扩散模型

影响力最大化旨在正确识别一组种子集以使它们在特定扩散模型下影响力的扩散范围最大化。本文选择SIR 模型[25]和线性阈值模型共两种模型作为扩散模型，在SIR 模型实验中，感染概率 γ 设为0.8，恢复概率 θ 设为0.5，种子集大小设为1～100；在线性阈值模型实验中，其阈值设置为0.5，种子集大小设为0～50。

3.1.3 对比算法

采用DC、PageRank、Entropy-based、MPIE 和IMNE-D 算法作为对比算法，验证IMNE 算法实现HIN 中影响力最大化的有效性。其中DC、PageRank 算法是常见的影响力最大化中选择种子集的方法；Entropy-based 算法[11]是同质网络中不仅考虑直接影响和间接影响，还考虑影响力扩散的一种方法，有助于对比异质信息对种子集选择的影响；其次，IMNE 算法除了实现HIN 中的影响力最大化，还可以度量HIN 中节点的社会影响力，而MPIE 算法是基于元路径度量HIN 中节点影响力的方法，因此，本文还选择MPIE 算法[18]作为对比算法，分析IMNE 算法在HIN 中度量节点社会影响力的效果。

在实验中，DC、PageRank 和Entropy-based 方法将忽略HIN 中节点和链接的异质性，直接在整个网络(4-area、Yelp 和Amazon)上运行，实验结果包含各种不同类型的节点。IMNE-D 是IMNE 算法的变体，主要通过计算节点的直接影响力来选择种子集，未考虑非直接相连的节点间的影响，有助于对比间接影响力对影响力最大化的作用。特别地，基准算法中的参数均选择实验结果最优参数。

3.1.4 评估指标

1) 在SIR 模型实验中，将感染率(Infection rate)和感染时间(Infection time)作为评估指标验证IMNE 算法的性能，其中感染率表示种子集在SIR 模型下感染节点占所有节点的比例；感染时间代表种子集在SIR 模型下达到最大感染率所需时间，验证IMNE 算法是否在SIR 扩散模型下使得影响力扩散范围在较短时间内达到最大。令NI表示在影响力扩散过程中从易感染状态转变为感染状态的节点数量，|V| 表示整个HIN 包含的节点数量，则感染率定义为

通常情况下，感染率越大、感染周期越短，算法性能越强。

2)在线性阈值模型实验中，将使用种子节点激活的其他节点数目来评估不同算法的性能，激活的节点数量越多，表示该影响力最大化算法的性能越强。

3.2 IMNE 算法在SIR 模型下的性能

本节将从感染率和感染时间两个方面分析IMNE 算法在SIR 模型下的有效性。

1)最大感染率。

由于存在随机性，每次实验中被感染节点的数量通常不同，因此本实验将每组种子集在SIR模型上运行50 次，取平均感染率作为该组种子集的感染率。图4 显示了不同算法的top-k个不同类型的影响力节点获得的感染率。

图4 不同算法的top-k 影响力节点的感染率比较Fig.4 Comparison of infection rate of different methods with different top-k influential nodes

首先，从图4 可以看出，IMNE 算法得到的感染率优于基线算法(DC、PageRank 和Entropybased)，这表明不同类型节点之间具有影响且这些异质信息有益于影响力最大化。其次，由于不同数据集数据的分布情况不同，相同的方法在不同的数据集上具有不同的感染率。特别地，DC 和PageRank 更加依赖于数据的分布情况，例如4-area中节点度的差异比Amazon 和Yelp 更明显，因此，在4-area 中PageRank 的性能比在Amazon 和Yelp 更稳定。同时，还可观察到，当k值较小时，在Yelp 数据集中，Entropy-based 优于IMNE 算法，但是随着k值的增加，IMNE 算法的感染率逐渐优于Entropy-based。

其次，关于IMNE-D，其与IMNE 的主要区别在于影响力度量组件，IMNE-D 仅考虑了直接链接节点之间的影响，忽略了社交网络中朋友的朋友之间的某种间接影响。根据结果(IMNE>IMNE-D)，可以发现间接影响力对改善影响力的传播范围具有重要意义。

2)达到最大感染率的时间。

影响力最大化不仅要求种子节点的影响范围最广，还要求在短时间内达到影响力扩散范围最广，因此，本实验从感染时间验证IMNE 算法的性能。图5 显示了不同模型的top-k影响力节点达到最大感染率的周期（周期即种子完成一次感染和恢复所需时间），可以看出IMNE 算法在3 个数据集上的影响力传播过程中，尤其是Yelp 和Amazon，IMNE 达到最大感染率的时间均小于其他基线算法，表示IMNE 算法能在较短的时间内达到较大的感染率,即IMNE 算法具有效性。在4-area 数据集中，当k值超过60 时，尽管IMNED 感染时间小于IMNE，但此时从图4 可以发现IMNE 算法的感染率大于IMNE-D。

图5 不同算法的top-k 影响力节点感染时间比较Fig.5 Comparison of infection time of different methods with different top-k influential nodes

综上所述，通过分析最大感染率和达到最大感染率所需时间，可以发现，IMNE 算法相较于其他基准算法能在更短的时间实现影响力最大化。

3.3 IMNE 在线性阈值模型下的性能

为了更好地验证IMNE 算法的有效性，本实验也验证了IMNE 算法在线性阈值模型下的有效性。图6 显示了在4-area 和Yelp 数据集上不同算法的k=(5,10,20,30,40,50) 个有影响力作者的影响范围。

从图6 可看出，IMNE 算法的影响范围均大于同质网络中的方法(DC、Entropy-based 和PageRank)，这表明IMNE 算法在LT 模型下也能较好地实现影响力最大化。其次，IMNE 算法的影响范围接近MPIE 算法，这表明IMNE 算法可以在不指定特定的元路径的情况下也能较为有效地度量HIN 中节点的社会影响力。

图6 不同算法的top-k 影响力节点影响范围Fig.6 Comparison of the range of top-k influential nodes of different methods

3.4 计算效率

本实验主要从节点社会影响力的计算时间分析IMNE 算法的效率。表1 展示了不同算法在4-area、Yelp 和Amazon 数据集上计算节点社会影响力耗费的时间。

首先，从表1 可以看出，由于不同数据集的数据分布情况不同，不同算法在不同数据集上的计算时间不同，IMNE 算法和其他基准算法在Yelp 数据集上的计算时间最少，4-area 数据集上的计算时间最多。

表1 不同算法的计算时间比较Table 1 Comparison of computation time of different algorithm s

其次，IMNE 算法花费的计算时间高于同质网络中的方法(DC、PageRank 和Entropy-based)，这是因为IMNE 算法既考虑了HIN 中节点的异质性又度量了节点的直接影响力和间接影响力，而DC、PageRank 和Entropy-based 忽略了HIN 中节点类型和边类型，仅做简单的计算；IMNE 算法的计算时间少于MPIE 算法，这是因为MPIE 算法需要迭代计算不同元路径下节点的社会影响力进行融合，而IMNE 算法通过网络嵌入已将HIN 映射于同一向量空间，节省了社会影响力的计算时间。

通过分析IMNE 算法的计算效率和有效性可以发现，IMNE 算法不仅相较于其他基准算法能在更短的时间内实现影响力最大化，而且在社会影响力的计算效率上，也具有一定的优势。

3.5 参数分析

1)权重的影响。

图7 展示了IMNE 算法中直接影响力和间接影响力的各种线性组合对影响力最大化的影响。从图7(a)、(b)可以看出直接影响力和间接影响力的权重分别为0.6 和0.4 时，感染率优于其他组合。这表明区分直接影响力和间接影响力对影响力最大化具有重要意义。此外，在Amazon 数据集下，不同直接影响力和间接影响力权重组合，其感染率变化不明显，这是因为Amazon 是一个密集数据集，在密集数据集中，具有较高直接影响力的节点其也具有较高的间接影响力。因此，本文将直接影响力和间接影响力的权重分别设置为0.6 和0.4。

图7 不同的权重对IMNE 算法的影响Fig.7 Comparison of IMNE with different weight of direct and indirect influence on three datasets.

2)感染概率 γ 的影响。

SIR 模型主要包含感染概率 γ 和恢复概率θ两个参数，本节实验测试了感染概率γ=(0.4,0.5,0.6,0.7,0.8,0.9)对IMNE 算法的影响，测试结果如图8所示。

图8 SIR 中不同的感染概率对IMNE 算法的影响Fig.8 Comparison of IMNE with different γ on three datasets.

从图8 可以看出，随着感染概率 γ 的增加，感染节点的比例也增加，这与事实相符。但是，从图8(a)可以看出，当感染概率分别为0.6 和0.7 时，感染率接近，因此本文选择0.8 作为感染概率。

4 结束语

本文提出了一种HIN 中基于网络嵌入的影响力最大化算法IMNE，该模型首先基于网络嵌入方法将不同类型的节点映射于低维向量空间，保留HIN 的网络结构以及语义信息，使得不同类型节点处于同一度量空间，然后通过扩展传统信息熵模型度量HIN 中不同类型节点的影响力选择最具影响力的节点作为种子集，实现了HIN 中的影响力最大化。但本文选择了已知的SIR 模型和线性阈值模型作为影响力扩散模型，未提出新的扩散模型，在将来的工作中，将考虑提出基于博弈论的扩散模型，不仅考虑网络结构对影响力扩散的影响，还考虑信息本身对影响力扩散的影响。

本文的主要贡献如下：

1) 提出了一种HIN 中基于网络嵌入的影响力最大化模型IMNE，该模型利用网络嵌入将HIN 中所有节点映射于同一向量空间，不仅揭示了HIN 中丰富的语义信息，还保留了更多的上下文信息，同时还解决了HIN 中不同类型间的异质问题，保持不同类型节点处于同一度量空间；

2)扩展传统的信息熵模型，考虑多种社会影响力的影响因素，度量HIN 中不同类型节点的直接影响和间接影响，有效地描述了社会影响力的复杂性和不确定性。

3)在3 个真实数据集和两个扩散模型上评估了IMNE 算法的性能，实验结果表明，IMNE 算法相较于其他基准算法能在更短的时间内实现影响范围最大。