影响力最大化问题是指在特定的扩散模型下，寻找一组初始扩散节点使影响扩散范围最大的优化问题。目前，影响力最大化算法主要分为两类：贪心算法^[1-3]和启发式算法^[4-6]，其中贪心算法主要用于提高算法的精确度；启发式算法主要用于解决实际问题以提高算法效率。Kempe等^[7]首次形式化定义了影响力最大化问题，并提出了一个贪心算法，其近似值约为 $1 - /{{\rm{e}}^{ - \varepsilon }}$ ，但是该算法的效率较低。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]。异质信息网络通常被定义为一个带有对象类型映射函数 $\phi :V \to A$ 和边类型映射函数 $\varphi :E \to R$ 的无向图 $G = (V,E)$ ，其中每个对象 $v \in V$ 属于一个特定的对象类型 $\phi (v) \in A$ ，每条边 $e \in E$ 属于一个特定的关系类型 $\varphi (e) \in R$ ，且 $\left| A \right| + \left| R \right| > 2$ 。

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

$V_s^* = \mathop {\arg \max }\limits_{{V_s} \subset V,\left| {{V_s}} \right| = k} \delta ({V_s})$

(1)

式中：种子集 $V_s^*$ 可包含HIN中各类型的节点。

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的影响范围更广。

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

2.1 HIN嵌入

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

2.2 影响力度量

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

定义3　直接/间接影响力。给定异质信息网络 $G$ 中的对象 $u$ 、 $v$ ，若对象 $u$ 和 $v$ 之间有边相连，即 ${e_{uv}} = 1$ ，则 $D{e_u}(v)$ 表示对象 $u$ 和对象 $v$ 间的直接影响力；若对象 $u$ 和 $v$ 之间没有边直接相连，即 ${e_{uv}} = 0$ ，则 $I{I_u}(v)$ 表示对象 $u$ 和对象 $v$ 间的间接影响力。

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

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

2.2.1 直接影响力度量

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

根据HIN嵌入得到的各类型节点的嵌入信息，可获得HIN中各类型节点的相似度 ${{\rm{Sim}}_{ij}}$ ，即：

${{\rm{Sim}}_{ij}} = \frac{{{{\boldsymbol{e}}_i} \cdot {{\boldsymbol{e}}_j}}}{{\left\| {{{\boldsymbol{e}}_i}} \right\|\left\| {{{\boldsymbol{e}}_i}} \right\|}}$

(2)

式中： ${{\boldsymbol{e}}_i}$ 和 ${{\boldsymbol{e}}_j}$ 分别对应对象 $i$ 和 $j$ 的潜在表征向量； $(\cdot )$ 表示向量的点积； $\left\| {\boldsymbol{e}} \right\|$ 表示向量的长度。

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

${{\rm{De}}_i} =\!-\! \displaystyle\sum_{i = 1,j \in V}^{{N_i}} {\left(\frac{1}{{{N_i}}}{\lg }\frac{1}{{{N_i}}} + \frac{{{{\rm{Sim}}_{ij}}}}{{\displaystyle\sum_{k = 1}^{{N_i}} {{{\rm{Sim}}_{ik}}} }}{{\lg }}\frac{{{{\rm{Sim}}_{ij}}}}{{\displaystyle\sum_{k = 1}^{{N_i}} {{{\rm{Sim}}_{ik}}} }}\right)} $

(3)

其中 $i \ne j$ 且 $i \ne k$ 。

2.2.2 间接影响力度量

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

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

$I{I_i}(k) = \sum_{k = 1}^{{N_{ik}}} {{{\rm{De}}_i} \times {{\rm{De}}_k}/{N_{ik}}} $

(4)

令 ${M_i}$ 表示对象 $i$ 的多跳连接对象的数量，对象 $i$ 的间接影响力 $I{I_i}$ 的定义如式(5)所示。

$I{I_i} = \frac{{\displaystyle\sum_{k = 1}^{{M_i}} {I{I_{ik}}} }}{{{M_i}}}$

(5)

2.2.3 全局影响力度量

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

${I_i} = \alpha {{\rm{De}}_i} + \beta I{I_i}$

(6)

式中： $\alpha $ 和 $\beta $ 分别表示直接影响力 ${{\rm{De}}_i}$ 和间接影响力 $I{I_i}$ 的权重，且 $\alpha + \beta = 1$ 。

2.3 IMNE算法描述

算法1　IMNE算法

输入　异质信息网络 $G = \{ V,E\} $ ；参数 $\alpha $ 和 $\beta $

输出　种子集 $S$

1)初始化 $S = {\rm{null}}$ ；

2)基于异质信息网络嵌入学习 $G$ 中节点的表征向量；

3) For $i = 1$ to $k$ ：

4) For each $v \in V$ do：

5)利用公式(3)计算直接影响力 ${{\rm{De}}_v}$ ；

6)利用公式(5)计算间接影响力 $I{I_v}$ ；

7)利用公式(6)计算全局影响力 ${I_v}$ ；

8) End For

9) $ u = {\max _v}{I_v}$ ；

10) $ S \leftarrow S \cup \{ u\}$ ；

11) End For

12) Return $ S$

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

3 实验评估 3.1 实验准备 3.1.1 数据集

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

3.1.2 扩散模型

影响力最大化旨在正确识别一组种子集以使它们在特定扩散模型下影响力的扩散范围最大化。本文选择SIR模型^[25]和线性阈值模型共两种模型作为扩散模型，在SIR模型实验中，感染概率 $\gamma $ 设为0.8，恢复概率 $\theta $ 设为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扩散模型下使得影响力扩散范围在较短时间内达到最大。令 ${\rm{NI}}$ 表示在影响力扩散过程中从易感染状态转变为感染状态的节点数量， $\left| V \right|$ 表示整个HIN包含的节点数量，则感染率定义为

${\rm{infection \;rate}} = \frac{{{\rm{NI}}}}{{\left| V \right|}}$

(7)

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

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

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

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

1)最大感染率。

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

首先，从图4可以看出，IMNE算法得到的感染率优于基线算法(DC、PageRank和Entropy-based)，这表明不同类型节点之间具有影响且这些异质信息有益于影响力最大化。其次，由于不同数据集数据的分布情况不同，相同的方法在不同的数据集上具有不同的感染率。特别地，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时，尽管IMNE-D感染时间小于IMNE，但此时从图4可以发现IMNE算法的感染率大于IMNE-D。

综上所述，通过分析最大感染率和达到最大感染率所需时间，可以发现，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中节点的社会影响力。

3.4 计算效率

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

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

其次，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。

2)感染概率 $\gamma $ 的影响。

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

从图8可以看出，随着感染概率 $\gamma $ 的增加，感染节点的比例也增加，这与事实相符。但是，从图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算法相较于其他基准算法能在更短的时间内实现影响范围最大。