第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