·758· 智能系统学报 第16卷 算法比CELF快35%~55%。接着，为了解决贪心 的信息扩散模型实现HN中的影响力最大化。 算法的效率问题，Tang等o提出一种基于跳的算 本文工作一方面扩展了HN嵌入的应用，另一方 法，该算法可以在常用的扩散模型（独立级联模 面将Peng等W所提的模型扩展到了HN。 型和线性阈值模型)下轻松应用于十亿规模的网 络。Peng等u认为个体之间的影响有直接影响 1相关符号和问题定义 和间接影响，社会影响力的强弱取决于个体之间 定义1异质信息网络2。异质信息网络通 的关系、网络距离、时间、网络和个体的复杂性和 常被定义为一个带有对象类型映射函数中：V→A 不确定性。但这些算法通常仅将社会网络看作同 和边类型映射函数P:E→R的无向图G=(VE), 质网络，忽略了社会网络的异质性，即网络中包 其中每个对象v∈V属于一个特定的对象类型 含不同类型的对象和链接。在异质信息网络(het- (v)∈A,每条边e∈E属于一个特定的关系类型 erogeneous information network,.HN)中，影响力可 g(e)∈R,且Al+R>2。 以通过不同的对象和链接进行扩散，从而获得更 定义2HN中的影响力最大化。给定一个 广泛的影响范围。 异质信息网络G={V,E,V,)是将种子集V,映射 尽管异质信息网络丰富的结构和语义信息有 到受种子集影响的对象数量的影响函数，异质信 助于实现影响力扩散范围最大化，但也给影响力的 息网络中影响力最大化的目的是选择一组最具影 分析带来了挑战。目前，HN中的数据挖掘任务 响力的种子集：=k),且该种子集可以最大 主要集中于相似性搜索2)、聚类11、分类6-1刀 化影响力的扩散范围，即 等，很少有研究者关注HN中的社会影响力分 V:=arg max6(V,） (1) 析。为了建模HN中的社会影响力，Yang等u V,CVIVk 提出了一种基于元路径的信息嫡模型MPIE,利用 式中：种子集：可包含HN中各类型的节点。 多条元路径从异质信息网络中提取多个同质信息 2IMNE模型 网络，在每个同质信息网络中基于嫡度量直接影 响力和间接影响力，然后融合多个同质信息网络 本节将详细介绍异质网络中基于网络嵌入的 中的影响力度量HIN中的社会影响力。尽管 影响力最大化模型MNE。 MPIE取得了一定的效果，但该算法需选择特定 首先以图1为例说明本文动机。如果将学术 类型的节点设定元路径，不能灵活地度量HN中 网络视为同质网络，该网络中仅Lily和Bob、 不同类型节点间的影响。 Ada和Tom间存在边，此时，若将Ada作为初始 HN嵌入2旨在通过基于节点的结构特性 扩散节点，其将仅影响Tom一个节点，即影响范 保留不同类型节点之间的邻近性来学习各个不同 围为1。然而，若将学术网络视为HN,如图2所 类型的节点的低维表示，而这些低维表示可直接 示，该网络中包含3种类型的节点，论文和会议之 应用于网络分析任务，比如节点分类、聚类以及 间存在发表/被发表关系，论文和论文之间存在引 链路预测等。由于HN嵌入将不同类型节点映 用/被引用关系，作者和论文之间存在撰写/被撰 射于同一向量空间，用同一空间的低维向量来描 写关系，考虑不同类型节点通过不同关系互相影 述不同类型的节点，不仅概括了网铬的重要结构 响，令Ada作为初始扩散节点，则P2和P6两篇论 特征，而且学习到的嵌入具有同质性，易于使用 文会受到Ada的直接影响，其次，由于Ada和 和集成。最近几年，异质信息网络的表征学习受 Tom之间通过路径“Tom-P2-Ada(合作)”相关联， 到了研究者的广泛关注。 Ada和Mary通过“Ada-P6-C1-P5-Mary(共同参加 因此，本文提出了一种异质网络中基于网络 会议)”相关联，所以Ada也可间接影响Tom和 嵌入的影响力最大化模型IMNE。IMNE首先利 May。相比同质网络，Ada的影响范围更广。 用网络嵌入学习HN中所有节点在同一向量空 IMNE模型的整体框架如图3所示。首先， 间的低维表征，保持不同类型节点在同一度量空 IMNE从HN(图3(a)中学习各种类型节点的嵌 间.然后基于HN原始的网络拓扑结构，扩展传 入（图3(b),然后，扩展信息熵模型度量社会 统的信息熵模型，考虑多种影响因素，度量 影响力，并选取最具影响力的节点作为种子集 HN中不同类型节点的社会影响力并选择最具影 (图3(c):最后在特定扩散模型下实现影响力最大 响力的节点作为初始扩散节点，最后，选择特定 化（图3(d).算法比 CELF 快 35%~55%。接着，为了解决贪心 算法的效率问题，Tang 等 [10] 提出一种基于跳的算 法，该算法可以在常用的扩散模型 (独立级联模 型和线性阈值模型) 下轻松应用于十亿规模的网 络。Peng 等 [11] 认为个体之间的影响有直接影响 和间接影响，社会影响力的强弱取决于个体之间 的关系、网络距离、时间、网络和个体的复杂性和 不确定性。但这些算法通常仅将社会网络看作同 质网络，忽略了社会网络的异质性，即网络中包 含不同类型的对象和链接。在异质信息网络 (het￾erogeneous 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 相关符号和问题定义 ϕ : V → A φ : E → R G = (V,E) v ∈ V ϕ(v) ∈ A e ∈ E φ(e) ∈ R |A|+|R| > 2 定义 1 异质信息网络[22]。异质信息网络通 常被定义为一个带有对象类型映射函数 和边类型映射函数 的无向图 ， 其中每个对象 属于一个特定的对象类型 ，每条边 属于一个特定的关系类型 ，且 。 G = {V,E} δ(Vs) Vs V ∗ s   V ∗ s    = k 定义 2 HIN 中的影响力最大化。给定一个 异质信息网络 ， 是将种子集 映射 到受种子集影响的对象数量的影响函数，异质信 息网络中影响力最大化的目的是选择一组最具影 响力的种子集 ( )，且该种子集可以最大 化影响力的扩散范围，即 V ∗ s = argmax Vs⊂V,|Vs|=k δ(Vs) (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))。 ·758· 智 能 系 统 学 报 第 16 卷