第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） 摘 要：针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型，且不同类 型节点在原始空间无法直接度量的问题，提出了一种异质信息网络中基于网络嵌入的影响力最大化模型（influence 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 heterogeneous 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 workspace. Accordingly, to solve these issues, this paper proposes a novel model for influence maximization based on network embedding in heterogeneous information networks, which helps to realize influence maximization by choosing initial 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. Experimental results on three real datasets demonstrate the effectiveness of the proposed model. Keywords: heterogeneous information network; homogeneous information network; influence maximization; information 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] 认为个体之间的影响有直接影响 和间接影响，社会影响力的强弱取决于个体之间 的关系、网络距离、时间、网络和个体的复杂性和 不确定性。但这些算法通常仅将社会网络看作同 质网络，忽略了社会网络的异质性，即网络中包 含不同类型的对象和链接。在异质信息网络 (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 相关符号和问题定义 ϕ : 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、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 评估指标 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 和 Entropybased)，这表明不同类型节点之间具有影响且这些 异质信息有益于影响力最大化。其次，由于不同 数据集数据的分布情况不同，相同的方法在不同 的数据集上具有不同的感染率。特别地，DC 和 PageRank 更加依赖于数据的分布情况，例如 4-area 中节点度的差异比 Amazon 和 Yelp 更明显，因 此，在 4-area 中 PageRank 的性能比在 Amazon 和 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·761·
·762· 智能系统学报 第16卷 Yelp更稳定。同时，还可观察到，当k值较小时， 最广，还要求在短时间内达到影响力扩散范围最 在Yelp数据集中，Entropy-based优于IMNE算 广，因此，本实验从感染时间验证MNE算法的性 法，但是随着k值的增加，IMNE算法的感染率逐 能。图5显示了不同模型的top-k影响力节点达 渐优于Entropy-based, 到最大感染率的周期（周期即种子完成一次感染 其次，关于IMNE-D,其与IMNE的主要区别 和恢复所需时间)，可以看出MNE算法在3个数 在于影响力度量组件，IMNE-D仅考虑了直接链 据集上的影响力传播过程中，尤其是Yelp和 接节点之间的影响，忽略了社交网络中朋友的朋 Amazon,IMNE达到最大感染率的时间均小于其 友之间的某种间接影响。根据结果(IMNE> 他基线算法，表示IMNE算法能在较短的时间内 IMNE-D),可以发现间接影响力对改善影响力的 达到较大的感染率，即IMNE算法具有效性。在 传播范围具有重要意义。 4-area数据集中，当k值超过60时，尽管IMNE- 2)达到最大感染率的时间。 D感染时间小于IMNE,但此时从图4可以发现 影响力最大化不仅要求种子节点的影响范围 IMNE算法的感染率大于IMNE-D。 --IMNE-D =3-DC -IMNE -◆-PageRank -◆-Entropy-based 2 -o-DC --DC -◆-PageRank -+-IMNE-D -◆-PageRank --IMNE-D Entropy-based =◆-MNE --Entropy-based -◆-IMNE 20 4060 80100 20 40 60 80100 204060 80100 top-k top-k top-k (a)Yelp (b)4-area (c)Amazon 图5不同算法的top-k影响力节点感染时间比较 Fig.5 Comparison of infection time of different methods with different top-k influential nodes 综上所述，通过分析最大感染率和达到最大 响范围。 感染率所需时间，可以发现，MNE算法相较于其 从图6可看出，MNE算法的影响范围均大 他基准算法能在更短的时间实现影响力最大化。 于同质网络中的方法(DC、Entropy-based和 3.3MNE在线性阈值模型下的性能 PageRank),这表明IMNE算法在LT模型下也能 为了更好地验证IMNE算法的有效性，本实 较好地实现影响力最大化。其次，IMNE算法的 验也验证了IMNE算法在线性阈值模型下的有效 影响范围接近MPIE算法，这表明IMNE算法可 性。图6显示了在4-area和Yelp数据集上不同算 以在不指定特定的元路径的情况下也能较为有效 法的k=(5,10,20,30,40,50)个有影响力作者的影 地度量HN中节点的社会影响力。 300 1500 DC 250 二车 2 1250 PageRank Entropy-based 1000 MPIE IMNE-D 150 IMNE ·DC 750 100 -◆·PageRank pp-aed 500 50 -◆IMNE-D 250 出◆ -◆.MNE 10 20 30 8 10 20 30 40 50 top-k top-k (a)4-area (b)Yelp 图6不同算法的top-k影响力节点影响范围 Fig.6 Comparison of the range of top-k influential nodes of different methods 3.4计算效率 力耗费的时间。 本实验主要从节点社会影响力的计算时间分 首先，从表1可以看出，由于不同数据集的数 析IMNE算法的效率。表1展示了不同算法在4 据分布情况不同，不同算法在不同数据集上的计 area、Yclp和Amazon数据集上计算节点社会影响 算时间不同，IMNE算法和其他基准算法在
k k Yelp 更稳定。同时，还可观察到，当 值较小时， 在 Yelp 数据集中，Entropy-based 优于 IMNE 算 法，但是随着 值的增加，IMNE 算法的感染率逐 渐优于 Entropy-based。 其次，关于 IMNE-D，其与 IMNE 的主要区别 在于影响力度量组件，IMNE-D 仅考虑了直接链 接节点之间的影响，忽略了社交网络中朋友的朋 友之间的某种间接影响。根据结 果 (IMNE> IMNE-D)，可以发现间接影响力对改善影响力的 传播范围具有重要意义。 2) 达到最大感染率的时间。 影响力最大化不仅要求种子节点的影响范围 k 最广，还要求在短时间内达到影响力扩散范围最 广，因此，本实验从感染时间验证 IMNE 算法的性 能。图 5 显示了不同模型的 top-k 影响力节点达 到最大感染率的周期（周期即种子完成一次感染 和恢复所需时间），可以看出 IMNE 算法在 3 个数 据集上的影响力传播过程中，尤其是 Yelp 和 Amazon，IMNE 达到最大感染率的时间均小于其 他基线算法，表示 IMNE 算法能在较短的时间内 达到较大的感染率,即 IMNE 算法具有效性。在 4-area 数据集中，当 值超过 60 时，尽管 IMNED 感染时间小于 IMNE，但此时从图 4 可以发现 IMNE 算法的感染率大于 IMNE-D。 4 3 2 1 0 1 40 60 80 100 20 top-k (a) Yelp 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 5 4 3 2 1 0 1 40 60 80 100 20 top-k (b) 4-area 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 4 3 2 1 0 1 40 60 80 100 20 top-k (c) Amazon 感染时间 (周期) DC PageRank Entropy-based IMNE-D IMNE 图 5 不同算法的 top-k 影响力节点感染时间比较 Fig. 5 Comparison of infection time of different methods with different top-k influential nodes 综上所述，通过分析最大感染率和达到最大 感染率所需时间，可以发现，IMNE 算法相较于其 他基准算法能在更短的时间实现影响力最大化。 3.3 IMNE 在线性阈值模型下的性能 k = (5,10,20,30,40,50) 为了更好地验证 IMNE 算法的有效性，本实 验也验证了 IMNE 算法在线性阈值模型下的有效 性。图 6 显示了在 4-area 和 Yelp 数据集上不同算 法的 个有影响力作者的影 响范围。 从图 6 可看出，IMNE 算法的影响范围均大 于同质网络中的方法 (DC、 Entropy-based 和 PageRank)，这表明 IMNE 算法在 LT 模型下也能 较好地实现影响力最大化。其次，IMNE 算法的 影响范围接近 MPIE 算法，这表明 IMNE 算法可 以在不指定特定的元路径的情况下也能较为有效 地度量 HIN 中节点的社会影响力。 300 250 200 150 100 50 0 5 20 30 40 50 10 top-k (a) 4-area 影响力传播 DC PageRank Entropy-based IMNE-D IMNE MPIE 1 500 1 250 1 000 750 500 250 0 5 20 30 40 50 10 top-k (b) Yelp 影响力传播 DC PageRank Entropy-based IMNE-D IMNE MPIE 图 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 可以看出，由于不同数据集的数 据分布情况不同，不同算法在不同数据集上的计 算时间不同， IMN E 算法和其他基准算法 在 ·762· 智 能 系 统 学 报 第 16 卷
第4期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·763· Yelp数据集上的计算时间最少，4-area数据集上 的计算时间最多。 表1不同算法的计算时间比较 Table 1 Comparison of computation time of different algorithm s 数据集 DC PageRank Entropy-based MPIE IMNE 4-area 3.6055 11.2153 652.6717 10194.2154 6560.0586 Amazon 2.0362 9.7238 329.6371 9652.9749 1149.1622 Yelp 0.7461 4.8529 283.2934 750.2954 340.1706 其次，IMNE算法花费的计算时间高于同质 网络中的方法(DC、PageRank和Entropy-based), 75 这是因为IMNE算法既考虑了HN中节点的异质 性又度量了节点的直接影响力和间接影响力，而 70 DC、PageRank和Entropy-based忽略了HN中节 =+-a=0.6,=0.4 点类型和边类型，仅做简单的计算；MNE算法的 65 ◆-a=0.3,=0.7 -●-a=0.7,=03 计算时间少于MPIE算法，这是因为MPIE算法需 a=0.4,P=0.6 -◆a-0.8B=0.2 -4-a=0.5=0.5 -◆-a=0.9,-0.1 要迭代计算不同元路径下节点的社会影响力进行 60 20 40 60 80100 融合，而MNE算法通过网络嵌人已将HN映射 top-k 于同一向量空间，节省了社会影响力的计算时间。 (b)4-area 通过分析IMNE算法的计算效率和有效性可 50 -◆-a=0.6,=0.4 以发现，IMNE算法不仅相较于其他基准算法能 -◆-=0.3，-0.7 -◆-=0.7，-0.3 -+-a=0.4,-0.6 45 在更短的时间内实现影响力最大化，而且在社会 -◆-=0.8，=0.2 -g-=0.5,=0.5 -。-a=0.9,=0.1 影响力的计算效率上，也具有一定的优势。 40 3.5参数分析 1)权重的影响。 35 图7展示了MNE算法中直接影响力和间接 20 影响力的各种线性组合对影响力最大化的影响。 40 60 80100 top-k 从图T(a)、(b)可以看出直接影响力和间接影响力 (c)Amazon 的权重分别为0.6和0.4时，感染率优于其他组 图7不同的权重对IMNE算法的影响 合。这表明区分直接影响力和间接影响力对影响 Fig.7 Comparison of IMNE with different weight of dir- 力最大化具有重要意义。此外，在Amazon数据 ect and indirect influence on three datasets. 集下，不同直接影响力和间接影响力权重组合， 2)感染概率y的影响。 其感染率变化不明显，这是因为Amazon是一个 SIR模型主要包含感染概率y和恢复概率O 密集数据集，在密集数据集中，具有较高直接影 两个参数，本节实验测试了感染概率y=(0.4,0.5,0.6, 响力的节点其也具有较高的间接影响力。因此， 0.7,0.8,0.9)对MNE算法的影响，测试结果如图8 本文将直接影响力和间接影响力的权重分别设置 为0.6和0.4。 所示。 90 70 75 65 5 60 =◆-a=0.6,=0.4 -◆-a=0.3,=0.7 -。-a=0.7,=0.3 30 -0-=0.4 ==-1=0.7 --a=0.4,=0.6 -◆-a=0.8.=02 -◆-7=0.5 --=0.8 a=0.5,=0.5 -◆-=0.9，=0.1 -◆-=0.6 -。-=0.9 50 20 40 60 80 100 20 0 60 80 100 top-k top-k (a)Yelp (a)Yelp
Yelp 数据集上的计算时间最少，4-area 数据集上 的计算时间最多。 表 1 不同算法的计算时间比较 Table 1 Comparison of computation time of different algorithm s 数据集 DC PageRank Entropy-based MPIE IMNE 4-area 3.605 5 11.2153 652.671 7 10 194.2154 6 560.0586 Amazon 2.036 2 9.7238 329.637 1 9 652.9749 1 149.1622 Yelp 0.746 1 4.8529 283.293 4 750.2954 340.170 6 其次，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) 感染概率 γ 的影响。 γ θ γ = (0.4,0.5,0.6, 0.7,0.8,0.9) SIR 模型主要包含感染概率 和恢复概率 两个参数，本节实验测试了感染概率 对 IMNE 算法的影响，测试结果如图 8 所示。 75 70 65 60 1 20 1 40 60 80 100 top-k (b) 4-area 感染率/% α=0.3, β=0.7 α=0.4, β=0.6 α=0.5, β=0.5 α=0.6, β=0.4 α=0.7, β=0.3 α=0.8, β=0.2 α=0.9, β=0.1 50 45 35 40 30 20 40 60 80 100 top-k (c) Amazon 感染率/% α=0.6, β=0.4 α=0.7, β=0.3 α=0.8, β=0.2 α=0.3, β=0.7 α=0.4, β=0.6 α=0.5, β=0.5 α=0.9, β=0.1 图 7 不同的权重对 IMNE 算法的影响 Fig. 7 Comparison of IMNE with different weight of direct and indirect influence on three datasets. 75 70 65 60 50 55 1 40 60 80 100 20 top-k (a) Yelp 感染率/% α=0.3, β=0.7 α=0.4, β=0.6 α=0.5, β=0.5 α=0.6, β=0.4 α=0.7, β=0.3 α=0.8, β=0.2 α=0.9, β=0.1 90 75 60 45 30 1 15 20 40 60 80 100 top-k (a) Yelp 感染率/% γ=0.4 γ=0.5 γ=0.6 γ=0.7 γ=0.8 γ=0.9 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·763·
·764· 智能系统学报 第16卷 SO 2)扩展传统的信息熵模型，考虑多种社会影 70 响力的影响因素，度量HN中不同类型节点的直 接影响和间接影响，有效地描述了社会影响力的 50 复杂性和不确定性。 40f- *0-=0.4 --=0.7 3)在3个真实数据集和两个扩散模型上评估 30 ,-◆-=0.5 -=0.8 了IMNE算法的性能，实验结果表明，IMNE算法 -◆-=0.6 =-=0.9 相较于其他基准算法能在更短的时间内实现影响 20 40 60 形 100 top-k 范围最大。 (b)4-area 参考文献： [1]HEIDARI M.ASADPOUR M.FAILI H.SMG:fast scal- 红*总速走这幸遗南密一￥字 able greedy algorithm for influence maximization in social networks[J].Physica a:statistical mechanics and its applic- ations..2015,420:124133. =0-=0.4 =-=0.7 [2]ORIEDI D,DE RUNZ C,GUESSOUM Z,et al.Influence ◆.=0.5 4-7=0.8 -t.=0.6 -。.0.9 maximization through user interaction modeling[C]//Pro- 25 ceedings of the 35th Annual ACM Symposium on Applied 20 40 60 80100 top-k Computing.Brno,Czech Republic,2020:1888-1890. (c)Amazon [3]LIU Wei,CHEN Ling,CHEN Xin,et al.An algorithm for influence maximization in competitive social networks 图8SR中不同的感染概率对MNE算法的影响 Fig.8 Comparison of IMNE with different y on three with unwanted users[J].Applied intelligence,2020,50(2): 417-437. datasets. [4]KIANIAN S,ROSTAMNIA M.An efficient path-based 从图8可以看出，随着感染概率y的增加，感 approach for influence maximization in social networks[J]. 染节点的比例也增加，这与事实相符。但是，从图8a Expert systems with applications,2021,167:114-168. 可以看出，当感染概率分别为0.6和0.7时，感染 [5]SHANG Jiaxing,ZHOU Shangbo,LI Xin,et al.CoFIM:a 率接近，因此本文选择0.8作为感染概率。 community-based framework for influence maximization 4结束语 on large-scale networks[J].Knowledge-based systems, 2017,117:88-100. 本文提出了一种HN中基于网络嵌入的影响 [6]胡庆成，张勇，邢春晓.基于有重叠社区划分的社会网络 力最大化算法IMNE,该模型首先基于网络嵌人 影响最大化方法研究.计算机科学，2018,45(6)： 32-35. 方法将不同类型的节点映射于低维向量空间，保 HU Qingcheng,ZHANG Yong,XING Chunxiao,et al.K- 留HN的网络结构以及语义信息，使得不同类型 clique heuristic algorithm for influence maximization in 节点处于同一度量空间，然后通过扩展传统信息 social network[J].Computer science,2018,45(6):32-35. 嫡模型度量HN中不同类型节点的影响力选择 [7]KEMPE D,KLEINBERG J,TARDOS E.Maximizing the 最具影响力的节点作为种子集，实现了HN中的 spread of influence through a social network[Cl//Proceed- 影响力最大化。但本文选择了已知的SR模型和 ings of the Ninth ACM SIGKDD International Conference 线性阈值模型作为影响力扩散模型，未提出新的 on Knowledge Discovery and Data Mining.Washington. 扩散模型，在将来的工作中，将考虑提出基于博 USA,2003:137-146 弈论的扩散模型，不仅考虑网络结构对影响力扩 [8]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-ef- 散的影响，还考虑信息本身对影响力扩散的影响。 fective outbreak detection in networks[Cl//Proceedings of 本文的主要贡献如下： the 13th ACM SIGKDD International Conference on 1)提出了一种HIN中基于网络嵌入的影响 Knowledge Discovery and Data Mining.San Jose,USA. 2007:420-429. 力最大化模型IMNE,该模型利用网络嵌人将 [9]GOYAL A,LU Wei,LAKSHMANAN L V S.CELF: HN中所有节点映射于同一向量空间，不仅揭示 optimizing the greedy algorithm for influence maximiza- 了HN中丰富的语义信息，还保留了更多的上下 tion in social networks[Cl//Proceedings of the 20th Interna- 文信息，同时还解决了HN中不同类型间的异质 tional Conference Companion on World Wide Web.Hy- 问题，保持不同类型节点处于同一度量空间： derabad.India.2011:47-48
80 70 60 50 40 20 30 1 20 1 40 60 80 100 top-k (b) 4-area 感染率/% γ=0.4 γ=0.5 γ=0.6 γ=0.7 γ=0.8 γ=0.9 45 40 35 30 25 20 40 60 80 100 top-k (c) Amazon 感染率/% γ=0.4 γ=0.5 γ=0.6 γ=0.7 γ=0.8 γ=0.9 图 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 算法 相较于其他基准算法能在更短的时间内实现影响 范围最大。 参考文献： HEIDARI M, ASADPOUR M, FAILI H. SMG: fast scalable greedy algorithm for influence maximization in social networks[J]. Physica a: statistical mechanics and its applications, 2015, 420: 124–133. [1] ORIEDI D, DE RUNZ C, GUESSOUM Z, et al. Influence maximization through user interaction modeling[C]//Proceedings of the 35th Annual ACM Symposium on Applied Computing. Brno, Czech Republic, 2020: 1888−1890. [2] LIU Wei, CHEN Ling, CHEN Xin, et al. An algorithm for influence maximization in competitive social networks with unwanted users[J]. Applied intelligence, 2020, 50(2): 417–437. [3] KIANIAN S, ROSTAMNIA M. An efficient path-based approach for influence maximization in social networks[J]. Expert systems with applications, 2021, 167: 114–168. [4] SHANG Jiaxing, ZHOU Shangbo, LI Xin, et al. CoFIM: a community-based framework for influence maximization on large-scale networks[J]. Knowledge-based systems, 2017, 117: 88–100. [5] 胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络 影响最大化方法研究 [J]. 计算机科学, 2018, 45(6): 32–35. HU Qingcheng, ZHANG Yong, XING Chunxiao, et al. Kclique heuristic algorithm for influence maximization in social network[J]. Computer science, 2018, 45(6): 32–35. [6] KEMPE D, KLEINBERG J, TARDOS É. Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2003: 137−146. [7] LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, USA, 2007: 420−429. [8] GOYAL A, LU Wei, LAKSHMANAN L V S. CELF++ : optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International Conference Companion on World Wide Web. Hyderabad, India, 2011: 47−48. [9] ·764· 智 能 系 统 学 报 第 16 卷
第4期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·765· [10]TANG Jang,TANG Xueyan,YUAN Junsong.An effi- [20]SHI Chuan,HU Binbin,ZHAO W X,et al.Heterogen- cient and effective hop-based approach for influence max- eous information network embedding for recommenda- imization in social networks[J].Social network analysis tion[J].IEEE transactions on knowledge and data engin- and mining,2018,8(1):10. eering,2019,31(2):357-370. [11]PENG Sancheng,YANG Aimin,CAO Lihong,et al.So- [21]SHI Yu,ZHU Qi,GUO Fang,et al.Easing embedding cial influence modeling using information theory in mo- learning by comprehensive transcription of heterogen- bile social networks[J].Information sciences,2017,379: eous information networks[C]//Proceedings of the 24th 146-159 ACM SIGKDD International Conference on Knowledge [12]SHI Chuan,KONG Xiangnan,HUANG Yue,et al. Discovery Data Mining.London,UK,2018: HeteSim:a general framework for relevance measure in 2190-2199. heterogeneous networks[].IEEE transactions on know- [22]LUO Chen,GUAN Renchu,WANG Zhe,et al.Het- ledge and data engineering,2014,26(10):2479-2492. PathMine:a novel transductive classification algorithm on [13]WANG Chenguang,SUN Yizhou,SONG Yanglei,et al. heterogeneous information networks[C]//Proceedings of RelSim:relation similarity search in schema-rich hetero- the 36th European Conference on Information Retrieval. geneous information networks[C]//Proceedings of the Amsterdam,The Netherlands,2014:210-221 2016 SIAM International Conference on Data Mining. [23]FU Taoyang,LEE W C,LEI Zhen.HIN2Vec:explore Philadelphia,USA,2016:621-629. meta-paths in heterogeneous information networks for [14]CHEN Lu,GAO Yunjun,ZHANG Yuanliang,et al.Effi- representation learning[C]//Proceedings of the 2017 ACM cient and incremental clustering algorithms on star- on Conference on Information and Knowledge Manage- schema heterogeneous graphs[Cl//Proceedings of 35th In- ment.Singapore,2017:1797-1806. ternational Conference on Data Engineering.Macao, [24]SUN Yizhou,HAN Jiawei,JING Gao,et al.iTopicMod- China,2019:256-267. el:information network-integrated topic modeling[C]// [15]CHEN Junxiang,DAI Wei,SUN Yizhou,et al.Cluster- Proceedings of the 9th IEEE International Conference on ing and ranking in heterogeneous information networks Data Mining.Miami,USA,2009:493-502. via gamma-Poisson model[C]//Proceedings of the 2015 [25]马知恩，周义仓，王稳地，等.传染病动力学的数学建模 SIAM International Conference on Data Mining.Van- 与研究M.北京：科学出版社，2014. couver,Canada,2015:425-432. 作者简介： [16]BANGCHAROENSAP P.MURATA T.KOBAYASHI 杨宇迪，硕士研究生，主要研究方 H,et al.Transductive classification on heterogeneous in- 向为社会网络分析、数据挖掘。 formation networks with edge betweenness-based normal- ization[C]/Proceedings of the Ninth ACM International Conference on Web Search and Data Mining.San Fran- cisc0,USA,2016:437-446. [17]WAN Mengting,OUYANG Yunbo,KAPLAN L,et al. Graph regularized meta-path based transductive regres- 周丽华，教授，博士生导师，CCF sion in heterogeneous information network[C]//Proceed- 会员，主要研究方向为数据挖掘、多视 ings of the 2015 SIAM International Conference on Data 角学习、异质社交网络分析。主持国 Mining.Vancouver,Canada,2015:918-926. 家自然科学基金项目3项、云南省重 [18]YANG Yudi,ZHOU Lihua,JIN Zhao,et al.Meta path- 点基金项目1项。发表学术论文 based information entropy for modeling social influence 80余篇，出版学术著作2部。 in heterogeneous information networks[C]//Proceedings of the 20th IEEE International Conference on Mobile 杜国王，博土研究生，主要研究方 Data Management.Hong Kong,China,2019:557-562. 向为数据挖掘、多视角聚类。 [19]LIU Zemin,ZHENG V W,ZHAO Zhou,et al.Distance- aware DAG embedding for proximity search on hetero- geneous graphs[C]//Proceedings of 32nd AAAI Confer- ence on Artificial Intelligence (AAAI).New Orleans, USA.2018:2355-2362
TANG Jang, TANG Xueyan, YUAN Junsong. An efficient and effective hop-based approach for influence maximization in social networks[J]. Social network analysis and mining, 2018, 8(1): 10. [10] PENG Sancheng, YANG Aimin, CAO Lihong, et al. Social influence modeling using information theory in mobile social networks[J]. Information sciences, 2017, 379: 146–159. [11] SHI Chuan, KONG Xiangnan, HUANG Yue, et al. HeteSim: a general framework for relevance measure in heterogeneous networks[J]. IEEE transactions on knowledge and data engineering, 2014, 26(10): 2479–2492. [12] WANG Chenguang, SUN Yizhou, SONG Yanglei, et al. RelSim: relation similarity search in schema-rich heterogeneous information networks[C]//Proceedings of the 2016 SIAM International Conference on Data Mining. Philadelphia, USA, 2016: 621−629. [13] CHEN Lu, GAO Yunjun, ZHANG Yuanliang, et al. Efficient and incremental clustering algorithms on starschema heterogeneous graphs[C]//Proceedings of 35th International Conference on Data Engineering. Macao, China, 2019: 256−267. [14] CHEN Junxiang, DAI Wei, SUN Yizhou, et al. Clustering and ranking in heterogeneous information networks via gamma-Poisson model[C]//Proceedings of the 2015 SIAM International Conference on Data Mining. Vancouver, Canada, 2015: 425−432. [15] BANGCHAROENSAP P, MURATA T, KOBAYASHI H, et al. Transductive classification on heterogeneous information networks with edge betweenness-based normalization[C]//Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. San Francisco, USA, 2016: 437−446. [16] WAN Mengting, OUYANG Yunbo, KAPLAN L, et al. Graph regularized meta-path based transductive regression in heterogeneous information network[C]//Proceedings of the 2015 SIAM International Conference on Data Mining. Vancouver, Canada, 2015: 918−926. [17] YANG Yudi, ZHOU Lihua, JIN Zhao, et al. Meta pathbased information entropy for modeling social influence in heterogeneous information networks[C]//Proceedings of the 20th IEEE International Conference on Mobile Data Management. Hong Kong, China, 2019: 557−562. [18] LIU Zemin, ZHENG V W, ZHAO Zhou, et al. Distanceaware DAG embedding for proximity search on heterogeneous graphs[C]//Proceedings of 32nd AAAI Conference on Artificial Intelligence (AAAI). New Orleans, USA, 2018: 2355−2362. [19] SHI Chuan, HU Binbin, ZHAO W X, et al. Heterogeneous information network embedding for recommendation[J]. IEEE transactions on knowledge and data engineering, 2019, 31(2): 357–370. [20] SHI Yu, ZHU Qi, GUO Fang, et al. Easing embedding learning by comprehensive transcription of heterogeneous information networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London, UK, 2018: 2190−2199. [21] LUO Chen, GUAN Renchu, WANG Zhe, et al. HetPathMine: a novel transductive classification algorithm on heterogeneous information networks[C]//Proceedings of the 36th European Conference on Information Retrieval. Amsterdam, The Netherlands, 2014: 210−221. [22] FU Taoyang, LEE W C, LEI Zhen. HIN2Vec: explore meta-paths in heterogeneous information networks for representation learning[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. Singapore, 2017: 1797−1806. [23] SUN Yizhou, HAN Jiawei, JING Gao, et al. iTopicModel: information network-integrated topic modeling[C]// Proceedings of the 9th IEEE International Conference on Data Mining. Miami, USA, 2009: 493−502. [24] 马知恩, 周义仓, 王稳地, 等. 传染病动力学的数学建模 与研究 [M]. 北京: 科学出版社, 2014. [25] 作者简介： 杨宇迪，硕士研究生，主要研究方 向为社会网络分析、数据挖掘。 周丽华，教授，博士生导师，CCF 会员，主要研究方向为数据挖掘、多视 角学习、异质社交网络分析。主持国 家自然科学基金项目 3 项、云南省重 点基金项 目 1 项。发表学术论 文 80 余篇，出版学术著作 2 部。 杜国王，博士研究生，主要研究方 向为数据挖掘、多视角聚类。 第 4 期 杨宇迪，等：异质信息网络中基于网络嵌入的影响力最大化 ·765·