【知识工程】异质信息网络中基于网络嵌入的影响力最大化

第16卷第4期 智能系统学报 Vol.16 No.4 2021年7月 CAAI Transactions on Intelligent Systems Jul.2021 D0:10.11992tis.202009047 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20210401.1300.004.html 异质信息网络中基于网络嵌入的影响力最大化 杨宇迪，周丽华2，杜国王'，邹星竹'，海燕 (1.云南大学信息学院，云南昆明650504：2.云南大学滇池学院，云南昆明650228) 摘要：针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型，且不同类 型节点在原始空间无法直接度量的问题，提出了一种异质信息网络中基于网络嵌入的影响力最大化模型( fluence maximization based on network embedding,IMNE),用于选择初始扩散节点实现影响力最大化。该模型不 仅可以在对异质信息网络进行编码的同时表征异质信息网络中潜在的信息，还可以捕获不同类型节点间影响 力的不确定和复杂性。在3个真实数据集上的实验验证了MNE算法的有效性。 关键词：异质信息网络：同质信息网络：影响力最大化：信息扩散：网络嵌入：直接影响力：间接影响力：全局影 响力 中图分类号：TP391 文献标志码：A文章编号：1673-4785(2021)04-0757-09 中文引用格式：杨宇迪，周丽华，杜国王，等.异质信息网络中基于网络嵌入的影响力最大化.智能系统学报，2021,16(4)： 757-765. 英文引用格式：YANG Yudi,ZHOU Lihua,.DU Guowang,etal.Influence maximization based on network embedding in heterogen- eous information networks(J].CAAI transactions on intelligent systems,2021,16(4):757-765. Influence maximization based on network embedding in heterogeneous information networks YANG Yudi',ZHOU Lihua,DU Guowang'ZOU Xingzhu',DING Haiyan' (1.School of Information,Yunnan University,Kunming 650504,China:2.Dianchi College,Yunnan University,Kunming 650228. China) Abstract:Most current influence maximization algorithms ignore the problem that heterogeneous information networks contain multiple node types and relationship types,and different types of nodes cannot be measured in the original work- space.Accordingly,to solve these issues,this paper proposes a novel model for influence maximization based on net- work embedding in heterogeneous information networks,which helps to realize influence maximization by choosing ini- tial diffusion nodes.The model can not only manifest the potential information in heterogeneous information networks while encoding it but also capture the uncertainty and complexity of influence among different types of nodes.Experi- mental results on three real datasets demonstrate the effectiveness of the proposed model. Keywords:heterogeneous information network;homogeneous information network;influence maximization;informa- tion diffusion;network embedding,direct influence;indirect influence;global influence 影响力最大化问题是指在特定的扩散模型 两类：贪心算法和启发式算法，其中贪心算 下，寻找一组初始扩散节点使影响扩散范围最大 法主要用于提高算法的精确度：启发式算法主要 的优化问题。目前，影响力最大化算法主要分为 用于解决实际问题以提高算法效率。Kempe等 收稿日期：2020-09-30.网络出版日期：2021-04-01. 首次形式化定义了影响力最大化问题，并提出了 基金项目：国家自然科学基金项目(61762090,62062066， 61966036):国家社会科学基金项目(18XZZ005):云 一个贪心算法，其近似值约为1-/，但是该算法 南省高等学校科技创新团队项目(RTSTYN):云南 省教育厅科学研究基金项目(2021Y026). 的效率较低。Leskovec等I图提出了CELF算法， 通信作者：周丽华.E-mail:Ihzhou@ynu.edu.cn Goyal等提出了CELF++算法，通过实验发现该

DOI: 10.11992/tis.202009047 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20210401.1300.004.html 异质信息网络中基于网络嵌入的影响力最大化 杨宇迪1 ，周丽华1,2，杜国王1 ，邹星竹1 ，丁海燕1 （1. 云南大学 信息学院，云南 昆明 650504; 2. 云南大学 滇池学院，云南 昆明 650228） 摘 要：针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型，且不同类 型节点在原始空间无法直接度量的问题，提出了一种异质信息网络中基于网络嵌入的影响力最大化模型（in￾fluence maximization based on network embedding，IMNE），用于选择初始扩散节点实现影响力最大化。该模型不 仅可以在对异质信息网络进行编码的同时表征异质信息网络中潜在的信息，还可以捕获不同类型节点间影响 力的不确定和复杂性。在 3 个真实数据集上的实验验证了 IMNE 算法的有效性。 关键词：异质信息网络；同质信息网络；影响力最大化；信息扩散；网络嵌入；直接影响力；间接影响力；全局影 响力 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2021)04−0757−09 中文引用格式：杨宇迪, 周丽华, 杜国王, 等. 异质信息网络中基于网络嵌入的影响力最大化 [J]. 智能系统学报, 2021, 16(4): 757–765. 英文引用格式：YANG Yudi, ZHOU Lihua, DU Guowang, et al. Influence maximization based on network embedding in heterogen￾eous information networks[J]. CAAI transactions on intelligent systems, 2021, 16(4): 757–765. Influence maximization based on network embedding in heterogeneous information networks YANG Yudi1 ，ZHOU Lihua1,2 ，DU Guowang1 ，ZOU Xingzhu1 ，DING Haiyan1 (1. School of Information, Yunnan University, Kunming 650504, China; 2. Dianchi College, Yunnan University, Kunming 650228, China) Abstract: Most current influence maximization algorithms ignore the problem that heterogeneous information networks contain multiple node types and relationship types, and different types of nodes cannot be measured in the original work￾space. Accordingly, to solve these issues, this paper proposes a novel model for influence maximization based on net￾work embedding in heterogeneous information networks, which helps to realize influence maximization by choosing ini￾tial diffusion nodes. The model can not only manifest the potential information in heterogeneous information networks while encoding it but also capture the uncertainty and complexity of influence among different types of nodes. Experi￾mental results on three real datasets demonstrate the effectiveness of the proposed model. Keywords: heterogeneous information network; homogeneous information network; influence maximization; informa￾tion diffusion; network embedding; direct influence; indirect influence; global influence 影响力最大化问题是指在特定的扩散模型 下，寻找一组初始扩散节点使影响扩散范围最大 的优化问题。目前，影响力最大化算法主要分为 1−/e −ε 两类：贪心算法[1-3] 和启发式算法[4-6] ，其中贪心算 法主要用于提高算法的精确度；启发式算法主要 用于解决实际问题以提高算法效率。Kempe 等 [7] 首次形式化定义了影响力最大化问题，并提出了 一个贪心算法，其近似值约为 ，但是该算法 的效率较低。Leskovec 等 [8] 提出了 CELF 算法， Goyal 等 [9] 提出了 CELF++算法，通过实验发现该 收稿日期：2020−09−30. 网络出版日期：2021−04−01. 基金项目：国家自然科学基金项 目 (61762090， 62062066， 61966036)；国家社会科学基金项目 (18XZZ005)；云 南省高等学校科技创新团队项目 (IRTSTYN)；云南 省教育厅科学研究基金项目 (2021Y026). 通信作者：周丽华. E-mail：lhzhou@ynu.edu.cn. 第 16 卷第 4 期 智 能 系 统 学 报 Vol.16 No.4 2021 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2021

·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 卷

第4期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·759· HIN2Vec模型旨在通过最大程度地联合预测 Mary 节点之间关系的可能性来学习节点向量和关系向 量。模型采用一对节点x和y,以及某种关系 reR的one-hot向量x、y和r作为输入，通过神经 Bob 网络将x、y和r转化为隐藏层中的潜向量Wx Wy和6(Wgr)(HN中关系和节点的语义含义不 同，所以关系向量r通过正则化转化为fo(Wr), Lily 限制r的值在0到1之间)，在输出层通过Sigmoid (∑Wx⊙VTyO for(Wr)实现逻辑分类（⊙表示逐 图1同质网络示例 Fig.1 Example of a homogeneous network 元素相乘)。通过HN2Vec,HN中的每个节点转 换为同一向量空间的低维度潜在表示，在捕获和 表示HIN中的丰富信息的同时，有效避免了 HN中不同类型节点和关系的不兼容性，便于度 量不同类型节点的社会影响力以选取初始扩散种 子集。 Bob P4 2.2影响力度量 Ada HN中，一个对象的社会影响力通常不仅体 Tom Lily 现于紧密的直接联系，还体现在节点的间接联 系。HN中社会影响的相关定义如下： 目 定义3直接间接影响力。给定异质信息网 作者 会议 论文 络G中的对象4、v,若对象u和v之间有边相连， 图2异质网络示例 即en=1,则De)表示对象u和对象v间的直接 Fig.2 Example of a HIN 影响力：若对象“和v之间没有边直接相连，即 2.1HN嵌入 em=0,则II()表示对象u和对象v间的间接影 本文使用HN2Vec模型2实现HIN嵌入。 响力。 8图 &盟D John Tom PI 6 岛羽 JIm Mike P2 ●论文O会议●作者 ◆醒 ◆2 厨 C2 P3 嵌人 度量 最大化 0 Mike 组合 JimP2 C2 Tom 春4刀 日046 Mike John P3 会议论文 作者 会议论文 作者 404▣ 6 Tom Mike ◇中 自纳 PI (a)异质信息网络的例子 (b)异质信息网络嵌入 (©)社会影响力度量 (d)影响力最大化 图3MNE模型的具体框架 Fig.3 The specific framework of the IMNE model 定义4全局影响力。给定异质信息网络G力。NE算法考虑了不同类型对象之间的影响 中的节点山，若节点“在整个网络中具有影响力，（如作者对论文的影响或论文对作者的影响），通 那么I被定义为节点“在G上的全局影响力。 常具有影响力的对象其相关行为也具有影响力。 全局影响力与直接间接影响力有着密切关 例如，在数据挖掘领域具有较强影响力的研究人 系。如果对象具有很强的直接和间接影响力，则 员，他发表的论文在数据挖掘领域通常也具有较 该对象通常在社会网络中具有较强的全局影响 高的影响力

Mary Bob Lily Ada Tom 图 1 同质网络示例 Fig. 1 Example of a homogeneous network P1 P4 P3 P6 Mary Bob Lily Ada Tom P5 C1 作者 会议 论文 P2 P7 图 2 异质网络示例 Fig. 2 Example of a HIN 2.1 HIN 嵌入 本文使用 HIN2Vec 模型[23] 实现 HIN 嵌入。 x y r ∈ R x y r x y r WT X x WT Y y f01(WT R r) r f01(WT R r) r Sigmoid ( ∑ WT X x⊙WT Y y⊙ f01(WT R r)) ⊙ HIN2Vec 模型旨在通过最大程度地联合预测 节点之间关系的可能性来学习节点向量和关系向 量。模型采用一对节点 和 ，以及某种关系 的 one-hot 向量 、 和 作为输入，通过神经 网络将 、 和 转化为隐藏层中的潜向量 、 和 (HIN 中关系和节点的语义含义不 同，所以关系向量 通过正则化转化为 ， 限制 的值在 0 到 1 之间)，在输出层通过 实现逻辑分类 ( 表示逐 元素相乘)。通过 HIN2Vec，HIN 中的每个节点转 换为同一向量空间的低维度潜在表示，在捕获和 表 示 H IN 中的丰富信息的同时，有效避免 了 HIN 中不同类型节点和关系的不兼容性，便于度 量不同类型节点的社会影响力以选取初始扩散种 子集。 2.2 影响力度量 HIN 中，一个对象的社会影响力通常不仅体 现于紧密的直接联系，还体现在节点的间接联 系。HIN 中社会影响的相关定义如下： G u v u v euv = 1 Deu(v) u v u v euv = 0 IIu(v) u v 定义 3 直接/间接影响力。给定异质信息网 络 中的对象 、 ，若对象 和 之间有边相连， 即 ，则 表示对象 和对象 间的直接 影响力；若对象 和 之间没有边直接相连，即 ，则 表示对象 和对象 间的间接影 响力。 嵌入 度量 最大化 Jim Tom John P1 论文 作者 会议 P2 Mike C1 P3 C2 John Tom Jim Mike P1 P2 C1 P3 C2 会议 论文 作者 John Tom Jim Mike P1 P2 C1 P3 C2 会议 论文 作者 (a) 异质信息网络的例子 (b) 异质信息网络嵌入 (c) 社会影响力度量 (d) 影响力最大化 John JIm 0.5 0.3 0.3 0.7 0.6 0.2 0.5 0.4 Tom 0.3 0.7 Mike 0.6 0.2 C2 0.3 0.7 0.3 0.7 P1 P2 0.5 0.3 P3 John 0.42 0.44 Tom 0.46 C1 0.46 P3 0.42 Mike 0.44 P1 … C1 组合 图 3 IMNE 模型的具体框架 Fig. 3 The specific framework of the IMNE model G u u Iu u G 定义 4 全局影响力。给定异质信息网络 中的节点 ，若节点 在整个网络中具有影响力， 那么 被定义为节点 在 上的全局影响力。 全局影响力与直接/间接影响力有着密切关 系。如果对象具有很强的直接和间接影响力，则 该对象通常在社会网络中具有较强的全局影响 力。IMNE 算法考虑了不同类型对象之间的影响 (如作者对论文的影响或论文对作者的影响)，通 常具有影响力的对象其相关行为也具有影响力。 例如，在数据挖掘领域具有较强影响力的研究人 员，他发表的论文在数据挖掘领域通常也具有较 高的影响力。 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·759·

·760· 智能系统学报 第16卷 2.2.1直接影响力度量 1)初始化S=null; 在社交网络中，影响力与许多潜在因素相互作 2)基于异质信息网络嵌入学习G中节点的表 用，如相似性和相关性，相似对象之间的相互影 征向量； 响往往更强，例如，在学术网络中，作者ⅰ与作者 3)For i=1tok: j、作者m均有合作，若作者i与作者j的研究领 4)For eachv∈Vdo: 域更相似，那么作者i和j间的相互影响往往更强。 5)利用公式(3)计算直接影响力De,; 同时，度中心性作为图论中度量节点相对重要性 6)利用公式（⑤）计算间接影响力山，； 的评价指标，也是社会影响力的潜在影响因素。 7)利用公式(6)计算全局影响力1； 根据HN嵌入得到的各类型节点的嵌入信 8)End For 息，可获得HN中各类型节点的相似度Sim,即： 9)u max: eiej Sim=e lle:l (2) 10)S-SU{u: 11)End For 式中：e:和e,分别对应对象i和j的潜在表征向 12)Return S 量；(~表示向量的点积；llell表示向量的长度。 HN网络嵌入不仅将不同类型节点映射于同 该算法中语句3~11用以选择最具影响力的k 一空间便于度量不同类型节点间的社会影响，还 个对象作为种子节点集S。IMNE算法的复杂度 保留HN原始结构，故给定异质信息网络G,令N: 为Om+nd+nlog(k),其中n表示异质信息网络中 表示对象i的度，对象i的直接影响力的定义如下： 对象的数量，n=W:k表示最具影响力的对象数 量；d表示一跳链接对象的平均数量：m表示异质 信息网络中边的总数，m=E。 Sim De;=- (3) i=l.jl Sima 3实验评估 其中i≠j且i≠k。 3.1实验准备 2.2.2间接影响力度量 3.1.1数据集 除了直接影响力，对象之间往往也具有某种 本文实验部分共使用了3个真实的HN数据 间接影响，例如，在学术网络中，具有影响力的作 集，来自两种不同领域，其中4-area数据集来自学 者可以通过论文或会议影响其他作者。 术领域，Yelp数据集和Amazon数据集来自商业 给定异质信息网络G,令Nt表示对象i和k 领域。4-area是从DBLP网站收集的子数据集， 间公共对象的数量，则对象i和k之间的间接影 涉及数据库、数据挖掘、机器学习和信息检索 响力描述如下： 4个研究领域，共包含20场会议、排名前5000 的作者、14328篇论文和8789个术语，其中作者 I(k)= De xDex/N+ (4) 与论文、论文与会议、论文与术语之间存在联系。 Yelp数据集记录了1268条用户对坐落于47个城 令M,表示对象i的多跳连接对象的数量，对 市、3种类型的2614条商户的评分情况，其中用 象i的间接影响力山，的定义如式（⑤）所示。 户与商户、商户与城市、商户与类型之间存在联 系。Amazon是一种商业网络，该网络记录了 I= (5) 6170个用户对来自334个品牌旗下的22种类别共 M, 2753项产品的3857条评论情况，其中用户与产 2.2.3全局影响力度量 品、产品与评论、产品与类别、产品与品牌之间存 根据直接影响力和间接影响力的度量可得， 在联系。以上3个数据集，除了来自不同的领域， 对象i的全局影响力如式(6)所示。 还具有不同的稀疏性，其中Ylp的数据分布最稀 I;=aDe:+BIl (6 疏，Amazon数据分布最密集。在实验过程中选 式中：a和B分别表示直接影响力De,和间接影 择HN2VecI模型嵌入HN数据集，使不同类型 响力IL的权重，且a+B=1。 节点处于同一度量空间。 2.3MNE算法描述 3.1.2扩散模型 算法1IMNE算法 影响力最大化旨在正确识别一组种子集以使 输入异质信息网络G=(V,E;参数a和B 它们在特定扩散模型下影响力的扩散范围最大 输出种子集S 化。本文选择SIR模型21和线性阈值模型共两

2.2.1 直接影响力度量 i j m i j i j 在社交网络中，影响力与许多潜在因素相互作 用，如相似性和相关性，相似对象之间的相互影 响往往更强，例如，在学术网络中，作者 与作者 、作者 均有合作，若作者 与作者 的研究领 域更相似，那么作者 和 间的相互影响往往更强。 同时，度中心性作为图论中度量节点相对重要性 的评价指标，也是社会影响力的潜在影响因素。 Simi j 根据 HIN 嵌入得到的各类型节点的嵌入信 息，可获得 HIN 中各类型节点的相似度 ，即： Simi j = ei · ej ∥ei∥ ∥ei∥ (2) ei ej i j (·) ∥e∥ 式中： 和 分别对应对象 和 的潜在表征向 量； 表示向量的点积； 表示向量的长度。 G Ni i i HIN 网络嵌入不仅将不同类型节点映射于同 一空间便于度量不同类型节点间的社会影响，还 保留 HIN 原始结构，故给定异质信息网络 ，令 表示对象 的度，对象 的直接影响力的定义如下： Dei =− ∑Ni i=1, j∈V   1 Ni lg 1 Ni + Simi j ∑Ni k=1 Simik lg Simi j ∑Ni k=1 Simik   (3) 其中 i , j 且 i , k。 2.2.2 间接影响力度量 除了直接影响力，对象之间往往也具有某种 间接影响，例如，在学术网络中，具有影响力的作 者可以通过论文或会议影响其他作者。 G Nik i k i k 给定异质信息网络 ，令 表示对象 和 间公共对象的数量，则对象 和 之间的间接影 响力描述如下： IIi(k) = ∑Nik k=1 Dei ×Dek/Nik (4) Mi i i IIi 令 表示对象 的多跳连接对象的数量，对 象 的间接影响力 的定义如式 (5) 所示。 IIi = ∑Mi k=1 IIik Mi (5) 2.2.3 全局影响力度量 i 根据直接影响力和间接影响力的度量可得， 对象 的全局影响力如式 (6) 所示。 Ii = αDei +βIIi (6) α β Dei IIi α+β = 1 式中： 和 分别表示直接影响力 和间接影 响力 的权重，且 。 2.3 IMNE 算法描述 算法 1 IMNE 算法 输入 异质信息网络 G = {V,E} ；参数 α 和 β 输出 种子集 S 1) 初始化 S = null ； 2) 基于异质信息网络嵌入学习 G 中节点的表 征向量； 3) For i = 1 to k： 4) For each v ∈ V do： 5) 利用公式 (3) 计算直接影响力 Dev； 6) 利用公式 (5) 计算间接影响力 IIv； 7) 利用公式 (6) 计算全局影响力 Iv； 8) End For 9) u = maxv Iv； 10) S ← S ∪ {u} ； 11) End For 12) Return S k S O(m+nd +nlog(k)) n n = |V| k d m m = |E| 该算法中语句 3~11 用以选择最具影响力的 个对象作为种子节点集 。IMNE 算法的复杂度 为 ，其中 表示异质信息网络中 对象的数量， ； 表示最具影响力的对象数 量； 表示一跳链接对象的平均数量； 表示异质 信息网络中边的总数， 。 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 是一种商业网络，该网络记录了 6170 个用户对来自 334 个品牌旗下的 22 种类别共 2 753 项产品的 3 857 条评论情况，其中用户与产 品、产品与评论、产品与类别、产品与品牌之间存 在联系。以上 3 个数据集，除了来自不同的领域， 还具有不同的稀疏性，其中 Yelp 的数据分布最稀 疏，Amazon 数据分布最密集。在实验过程中选 择 HIN2Vec[13] 模型嵌入 HIN 数据集，使不同类型 节点处于同一度量空间。 3.1.2 扩散模型 影响力最大化旨在正确识别一组种子集以使 它们在特定扩散模型下影响力的扩散范围最大 化。本文选择 SIR 模型[25] 和线性阈值模型共两 ·760· 智 能 系 统 学 报 第 16 卷

第4期 杨宇迪，等：异质信息网络中基于网络嵌人的影响力最大化 ·761· 种模型作为扩散模型，在SR模型实验中，感染概 1)最大感染率。 率y设为0.8，恢复概率0设为0.5，种子集大小设 由于存在随机性，每次实验中被感染节点的 为1~100：在线性阈值模型实验中，其阈值设置为 数量通常不同，因此本实验将每组种子集在SIR 0.5,种子集大小设为050。 模型上运行50次，取平均感染率作为该组种子集 3.1.3对比算法 的感染率。图4显示了不同算法的top-k个不同 采用DC、PageRank、Entropy-based、MPIE和 类型的影响力节点获得的感染率。 MNE-D算法作为对比算法，验证IMNE算法实现 80 HN中影响力最大化的有效性。其中DC、PageR- ank算法是常见的影响力最大化中选择种子集的 70 方法；Entropy-based算法是同质网络中不仅考 虑直接影响和间接影响，还考虑影响力扩散的一 60 种方法，有助于对比异质信息对种子集选择的影 -DC 50 响；其次，IMNE算法除了实现HN中的影响力最 -◆-PageRank -IMNE-D 大化，还可以度量HN中节点的社会影响力，而 -Entropy-based -◆MNE 0 20 40 60 80 100 MPIE算法是基于元路径度量HN中节点影响力 top-k 的方法，因此，本文还选择MPE算法作为对比 (a)Yelp 算法，分析MNE算法在HN中度量节点社会影 80 响力的效果。 在实验中，DC、PageRank和Entropy-.based方 70 法将忽略HN中节点和链接的异质性，直接在整 60 书中十个◆中+、 个网络(4-area、Yelp和Amazon)上运行，实验结 0 果包含各种不同类型的节点。MNED是IMNE算 -o-DC 法的变体，主要通过计算节点的直接影响力来选 0 -◆-PageRank -4-IMNE-D -Entropy-based --IMNE 择种子集，未考虑非直接相连的节点间的影响，有 30 20 40 60 80 100 助于对比间接影响力对影响力最大化的作用。特别 top-k 地，基准算法中的参数均选择实验结果最优参数。 (b)4-area 3.1.4评估指标 1)在SIR模型实验中，将感染率(Infection rate)和感染时间(nfection time)作为评估指标验 40 有◆◆身◆身之文 证MNE算法的性能，其中感染率表示种子集在 -0-00=0 SIR模型下感染节点占所有节点的比例；感染时 30 间代表种子集在SIR模型下达到最大感染率所需 -0-DC -◆-PageRank -IMNE-D 时间，验证IMNE算法是否在SIR扩散模型下使 --Entropy-based -◆-MNE 得影响力扩散范围在较短时间内达到最大。令 20 0 0 60 80100 I表示在影响力扩散过程中从易感染状态转变 top-k (c)Amazon 为感染状态的节点数量，IW表示整个HN包含的 节点数量，则感染率定义为 图4不同算法的topk影响力节点的感染率比较 infection rate-NI Fig.4 Comparison of infection rate of different methods (7) ☑ with different top-k influential nodes 通常情况下，感染率越大、感染周期越短，算 首先，从图4可以看出，IMNE算法得到的感 法性能越强。 染率优于基线算法(DC、PageRank和Entropy- 2)在线性阈值模型实验中，将使用种子节点 based),这表明不同类型节点之间具有影响且这些 激活的其他节点数目来评估不同算法的性能，激 异质信息有益于影响力最大化。其次，由于不同 活的节点数量越多，表示该影响力最大化算法的 数据集数据的分布情况不同，相同的方法在不同 性能越强。 的数据集上具有不同的感染率。特别地，DC和 3.2IMNE算法在SIR模型下的性能 PageRank更加依赖于数据的分布情况，例如4area 本节将从感染率和感染时间两个方面分析 中节点度的差异比Amazon和Yelp更明显，因 IMNE算法在SR模型下的有效性。 此，在4-area中PageRank的性能比在Amazon和

γ θ 种模型作为扩散模型，在 SIR 模型实验中，感染概 率 设为 0.8，恢复概率 设为 0.5，种子集大小设 为 1~100；在线性阈值模型实验中，其阈值设置为 0.5，种子集大小设为 0~50。 3.1.3 对比算法 采用 DC、PageRank、Entropy-based、MPIE 和 IMNE-D 算法作为对比算法，验证 IMNE 算法实现 HIN 中影响力最大化的有效性。其中 DC、PageR￾ank 算法是常见的影响力最大化中选择种子集的 方法；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 评估指标 NI |V| 1) 在 SIR 模型实验中，将感染率 (Infection rate) 和感染时间 (Infection time) 作为评估指标验 证 IMNE 算法的性能，其中感染率表示种子集在 SIR 模型下感染节点占所有节点的比例；感染时 间代表种子集在 SIR 模型下达到最大感染率所需 时间，验证 IMNE 算法是否在 SIR 扩散模型下使 得影响力扩散范围在较短时间内达到最大。令 表示在影响力扩散过程中从易感染状态转变 为感染状态的节点数量， 表示整个 HIN 包含的 节点数量，则感染率定义为 infection rate = NI |V| (7) 通常情况下，感染率越大、感染周期越短，算 法性能越强。 2) 在线性阈值模型实验中，将使用种子节点 激活的其他节点数目来评估不同算法的性能，激 活的节点数量越多，表示该影响力最大化算法的 性能越强。 3.2 IMNE 算法在 SIR 模型下的性能 本节将从感染率和感染时间两个方面分析 IMNE 算法在 SIR 模型下的有效性。 1) 最大感染率。 k 由于存在随机性，每次实验中被感染节点的 数量通常不同，因此本实验将每组种子集在 SIR 模型上运行 50 次，取平均感染率作为该组种子集 的感染率。图 4 显示了不同算法的 top- 个不同 类型的影响力节点获得的感染率。 80 70 60 50 40 20 40 60 80 100 top-k (a) Yelp 感染率/% DC PageRank Entropy-based IMNE-D IMNE 80 70 60 50 30 40 1 20 1 1 40 60 80 100 top-k (b) 4-area 感染率/% DC PageRank Entropy-based IMNE-D IMNE 50 40 30 20 20 40 60 80 100 top-k (c) Amazon 感染率/% DC PageRank Entropy-based IMNE-D IMNE 图 4 不同算法的 top-k 影响力节点的感染率比较 Fig. 4 Comparison of infection rate of different methods with different top-k influential nodes 首先，从图 4 可以看出，IMNE 算法得到的感 染率优于基线算法 (DC、PageRank 和 Entropy￾based)，这表明不同类型节点之间具有影响且这些 异质信息有益于影响力最大化。其次，由于不同 数据集数据的分布情况不同，相同的方法在不同 的数据集上具有不同的感染率。特别地，DC 和 PageRank 更加依赖于数据的分布情况，例如 4-area 中节点度的差异比 Amazon 和 Yelp 更明显，因 此，在 4-area 中 PageRank 的性能比在 Amazon 和 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·761·