异质信息网络中基于元结构的影响力最大化_徐智敏.pdf

基金项目:国家自然科学基金项目(61762090，62062066，61966036);国家社会科学基金项目(18XZZ005);云南省高等学校科技创新团队项目(ITSTYN)。云 南 省 教 育 厅 科 学 研 究 基 金 项 目 资 助(2021Y026)。收稿日期:20210406修回日期:20210413第 40 卷第 2 期计算机仿真2023 年 2 月文章编号:10069348(2023)02042005异质信息网络中基于元结构的影响力最大化徐智敏，周丽华(云南大学信息学院，云南昆明 650504)摘要:影响力最大化问题旨在给定的网络中找到固定个数的活跃节点集，基于特定的传播模型，使得最终被激活的节点数目达到最大。目前，异质信息网络的影响力最大化算法大多从网络中提取同质子图进行影响力最大化研究，时间复杂度较高，并且使用同质子图损失了节点原有的结构信息以及节点间潜在的语义关系。提出一种基于元结构的影响力最大化算法(MSIM)，利用为节点构造的元结构描述不同类型节点之间的关系，较完整的保留网络的结构信息和异质信息，同时提出了路径熵与结构熵来度量节点的影响力。在真实数据集上的实验结果表明，MSIM 算法比传统的算法有着更好的影响范围和时间效率。关键词:异质信息网络;影响力度量;信息熵;元结构中图分类号:TP391文献标识码:BMetaStructureBased InfluenceMaximization in HeterogeneousInformation NetworksXU Zhimin，ZHOU Lihua(College of Information，Yunnan University，KunmingYunnan 650504，China)ABSTACT:The purpose of the influence maximization problem is to find a fixed number of active nodes in a givennetwork，and based on a specific propagation model，make the number of nodes that are finally activated reach themaximumThe problem of maximizing influence is to find a fixed number of active nodes in a given network，based ona specific propagation model，to maximize the number of nodes that are finally activated At present，the influencemaximization algorithm of heterogeneous information network mostly extracts homoproton graphs from heterogeneousinformation networks for influence maximization research The time complexity is relatively high，and the use of ho-mogenous graphs loses the original structural information of the node and the underlying semantic relationship betweennodes This paper proposes a metastructurebased influence maximization algorithm(MSIM)，which uses a metastructure that can retain the structural information and heterogeneous information of the network to describe the rela-tionship between different types of nodes At the same time，path entropy and structure entropy are proposed to meas-ure the influence of nodes Experimental results on real data sets show that the MSIM algorithm has a better range ofinfluence and time efficiency than traditional algorithmsKEYWODS:Heterogeneous information network;Influence measure;Information entropy;Meta structure1引言社交网络的发展为信息的全球传播和新闻的有效传播带来了新的潜力，人们可以直接参与这些社交网络，建立自己的友谊网络，并相互分享他们的观点、见解和经验。而确定网络中有影响力的成员被视为这种潜力付诸行动的关键因素，影响力最大化问题由此被提出。Domingos 等人1 首先将影响力最大化问题建模为一个算法问题。Kempe 等人2 首次将影响力最大化问题定义为一个离散最优问题，并证明该问题是一个 NPhard 问题，同时提出了贪心算法得到了该问题的一个近似解。但贪心算法的时间复杂度过高，无法高效解决大规模网络问题。对此024研究者们相继提出了许多启发式算法3，4 或改进贪心算法5，6 以提高运行效率。然而这些方法仅针对同质信息网络进行考虑，即只考虑了一种对象类型和一种关系类型，忽略了对象之间的异质关系和潜在的语义信息。异质信息网络7 是一种包含了多种对象类型和多种关系类型的信息网络，能够更加合理的描述真实的社会网络。因此，在异质信息网络上进行影响力最大化研究更具有现实意义。近些年来，影响力最大化研究的焦点逐渐转向异质信息网络。杨等人8 通过多种元路径提取不同对象之间关系，来度量节点的影响力。Kuhnle 等人9 提出了多重网络上的影响力最大化算法等。但由于异质信息网络具有复杂的网络结构，如何高效的利用异质信息一直是异质信息网络分析的难点问题。本文的目的是在异质信息网络中研究相同类型对象的影响力最大化问题，并提出了基于元结构的影响力最大化算法(MSIM)。异质信息网络中包含了丰富的语义信息，元路径可以有效地捕获源对象和目标对象间的单一关系，但无法捕获到它们之间的复杂关系。而元结构本质上可以看作多条元路径的集合，能够方便的表达对象间复杂的关系。因此，在 MSIM 算法中采用元结构存储目标对象与网络中所有类型对象间的语义关系，并且引入信息熵来度量节点的影响力，提出了路径熵度量不同元路径对源节点的影响贡献，然后整合了元结构中不同元路径的路径熵提出了结构熵度量源节点的最终影响。最后在真实数据集上进行实验，验证了该算法的有效性。本文的贡献主要包含以下三个方面:1)提出了一种基于元结构的信息熵影响力最大化算法(MSIM)，该算法为每个目标类型节点构造一个元结构，存储不同对象之间的异质关系;2)提出了路径熵(PE)和结构熵(SE)来评估一个节点在异质信息网络中的重要性，PE 值反映了单条路径对源节点的影响，SE 值反映了局部结构对节点的影响;3)在两个真实数据集上验证了 MSIM 算法的有效性和效率，并证明 MSIM 算法在效率和性能上有较好的折中。2相关工作影响力最大化问题在 2003 年首次被定义为一个算法问题，Kempe 等人2 证明了该问题是一个 NPhard 问题，并提出了贪心算法，该算法具有高精度的近似结果，但也有着高昂的时间代价，难以拓展到大规模网络问题的应用。为了克服传统的贪心算法的低效性，研究者们对传统的贪心算法进行了一系列的改进，或者提出了新的启发式算法。刘等人10 基于局部节点优化和折扣度构造了节点近似影响值函数来计算局部节点的影响值。曹等人11 提出了基于核数层次特征和影响半径的启发式算法。聂等人12 将信息熵引入复杂网络以计算节点的影响力，使用信息熵度量不同邻居对节点的影响。然而这些方法均为同质信息网络的研究方法，未考虑到不同类型对象之间的连接关系。随着社交媒体的快速发展，异质信息网络已被提议作为真实世界图或网络的一般表示。目前关于异质信息网络的研究主要集中在聚类、分类、相似性搜索链路预测等，而关于异质信息网络的影响力最大化研究相对较少。李等人13 通过限制相同类型节点间的最短路径从异质信息网络中抽取一个同质子图，并根据节点对在异质信息网络中的路径来确定子图中节点间的影响。杨等人8 利用元路径在异质信息网络中提取出多个同质子图进行影响力最大化研究，但使用独立的元路径进行对象之间关系的提取，会忽略一些对象被多条边共享的问题，会导致这些信息的损失。3相关概念本节主要介绍异质信息网络和信息熵中的基本概念，这些概念是本文工作的基础。定义 1异质信息网络7:异质信息网络是具有一个对象类型函数 和一个关系类型函数 的有向图 G=(V，E，T，)。其中 V 是节点集，E 是边集，T 是节点类型集合，|T|1，是关系类型集合，|1，:VT 是节点和节点类型的映射，:E 是边和关系类型的映射。如图 1 描述了异质信息网网络 DBLP 的一个网络实例，它描述了不同类型实体之间的关系，如 Bob 和 Ada 曾合作发表了论文 P2。图 1DBLP 网络实例定义 2异质信息网络模式14:异质信息网络模式记为TG=(T，)，是带有对象映射函数:VT 和关系映射函数:E 的异质信息网络 G=(V，E，T，)的元模板。定义 3元路径7:元路径是定义在异质信息网络上的线性序列，源对象和目标对象的类型位于路径的两端。可表现为:T11T22n1Tn，可缩写为:T1T2Tn。Molaei 等人15 将异质信息网络中的元路径区分为单介质元路径和多介质元路径，仅通过一个中介相连的元路径为单介质元路径，如在 DBLP 网络中，对于元路径 APA(作者，论文，作者)，作者之间仅通过论文节点相连，称之为单介质元路径，反之通过多个介质相连的称为多介质元路径。定义 4元结构16:元结构可以看作由多条具有公共节点组成的有向无环图，形式化地，元结构可以记为 M=(VM，EM)，其中 VM是节点集合，EM是边集合。124定义 5信息熵4:信息熵是一个系统的信息含量的量化指标，常用来作为系统方程优化的目标或参数选择的判据。乔等人4 将信息熵引入复杂网络以计算节点的影响力。对于网络中的任意节点 v 的信息熵可以由式(1)计算EV=uNvHuv=uNv puvlog(puv)(1)其中 puv=dulNvdl，Nv是节点v节点直接邻居的集合，du是u 节点的度，Huv是节点 u 对节点 v 提供的影响传播能力。4基于元结构的影响力最大化建模在这一部分，本文提出了一个基于元结构的影响力最大化算法模型(MSIM)，采用的数学符号及含义见表 1。表 1符号说明数学符号及含义G=(V，E，T，)异质信息网络有向图，V 表示顶点集，E 表示边集，T 表示对象类型集合，表示关系类型集合。W=V1V2Vn表示关系序列为 V1V2Vn的元路径 W。w=v1v2v3表示元路径 W 的一条路径实例。H，p表示传播概率MSv表示节点 v 的元结构PEWv表示元路径 W 对节点 v 的路径熵SEv表示节点 v 的结构熵4.1问题定义本文选择以异质信息网络中的信息传播为例，研究异质信息网络的影响力最大化问题。给定一个异质信息网络 G=(V，E，T，)，本文的目的是在考虑在度量节点的影响力时利用异质信息网络中丰富的语义信息，考虑不同类型节点之间的影响，在特定的扩散模型下，选择出具有最大影响范围的相同节点类型的子集。4.2构造元结构为了度量节点的影响力，本文为每一个目标类型节点 uV 构造一个元结构 MSu，并且将 u 作为元结构中的源节点，根据网络模式不同类型节点之间的关系，查找出节点 u的出邻居加入 MSu，然后根据网络模式中 u 的出邻居所属的节点类型与其它节点类型节点的关系，将出邻居的出邻居添加至 MSu，直至遍历网络模式中 u 与所有类型节点之间的关系。在构造元结构的过程中保留节点本身的度的信息。如图 2 描述了图 1 中作者 Ying 的元结构的构造过程。本文通过网络模式提取出目标节点的元结构能够有效的保留局部结构信息和节点间的异质信息，而本文对节点影响力的度量也将以节点的元结构为基础。4.3路径熵与结构熵元路径可以提取源节点与目标节点的关系，对于以 v1为源节点的元路径 W，路径 w(v1v2vn)是 W 的一条路径实图 2元结构构造示例例，本文由式(2)计算元路径 W 对源节点 v1的路径熵。PEWv1=wWHw=wW pv1v2pvn1vnlog(pv1v2pvn1vn)(2)其中Hw路径实例w的传播概率，puv=dulNvdl，Nv是v节点直接邻居的集合，du是 u 节点的度。社交网络中的三度影响力理论指出信息在网络传播过程中存在衰减，并发现三度之内的节点属强连接关系，而距离三度之外的节点间为弱连接关系，信息在弱连接中基本不产生影响。因此，本文对多介质元路径进行“折半”处理，只计算其前驱的路径熵，如对于元路径 APTPA，只计算元路径APT 对源节点所提供的路径熵。在本文构造的所求影响力最大化的目标类型节点的元结构中能够有效的存储多介质元路径的前驱信息，以及目标节点与其它类型节点间的联系。对于节点 v1的元结构 MSv1，综合由不同元路径 W 的路径熵得出 v1的结构熵，由式(3)计算节点的结构熵。SEv1=WiMSv1iPEWiv1(3)其中 i为元路径 Wi的影响因子。4.4MSIM 算法描述本文提出了在异质信息网络中基于元结构的影响力最大化算法(MSIM)。MSIM 算法构造节点的元结构，并定义节点的结构熵度量源节点的影响力，也考虑了不同类型的元路径对节点影响力的影响。元结构的构建有利于根据不同的扩散任务，有针对性的选择种子节点。如在 DBLP 网络中选择作者节点作为影响力最大化的研究目标，那么 MSIM 通过构造作者节点的元结构来度量作者的影响力。通过元结构中不同的元路径的结合来度量节点的影响，既考虑到了节点的局部影响也考虑到了节点的全局影响。MSIM 算法伪代码如下所示。MSIM 算法伪代码1)输入:G(V，E，T，)，种子集节点数量 k2)输出:种子集合 S3)初始化 S=4)For each uV，5)构造元结构 MSu6)由式(2)(3)计算节点的结构熵 MEu2247)Endfor8)Fori=1 to k do:9)s=max(MEu)10)S=S s11)End for12)eturn S5仿真验证5.1数据集准备本文在真实的异质信息网络数据集 DBLP 数据集和YELP 数据集验证 MSIM 算法的性能。数据集的详细描述如表 2 所示。为了验证所提出的 MSIM 算法的有效性，本文采用同质信息网络中基于信息熵的影响力最大化算法 ME 算法12，以及异质信息网络中基于同质子图的 Entropy 算法13 和 MPIE 算法8 作为对比算法。表 2数据集详细信息DBLPObjectsNumberelationshipNumberAuthor(A)14475PA41794Paper(P)14376PC14376Conference(C)20PT114624Term(T)8920YelpObjectsNumberelationshipNumberUser(U)16239UB198397Business(B)14284UU158590Category(Cat)47BCit14257City(Cit)511BCat400095.2有效性验证为了验证 MSIM 算法的性能，本文在 DBLP 和 YELP 数据集上进行实验。对于同质信息网络中的 ME 算法，实验中不区分节点类型与边类型。分别选取 k 个 DBLP 网络中的作者节点和 YELP 网络中的用户节点作为种子节点，k 分别选取 10，20，30，40，50 个节点。通过 LT 模型进行扩散模拟，采用影响范围(InfluenceSpread)作为评价指标，影响范围定义为成功激活节点的数量。图 3 展示了不同算法对不同 k个影响节点的影响扩散范围，其中横坐标表示种子集合大小，纵坐标表示最终激活节点数量。从图 3 中可以看出，不同算法在不同的数据集上表现出不同的性能，并随着 k 值的增加，最终激活节点的数量也会增加。在这些算法中，所提出的 MSIM 算法优于同质信息网络的 ME 算法，表明考虑节点的异质信息可以提高扩散影响范围。MPIE 算法、Entropy 算法在不同的数据集表现出不同性能，其中 MPIE 算法在 DBLP 数据集中的表现较差，而在YELP 数据集中性能有所提升，这说明在异质信息网络中提取同质子图进行影响力最大化研究依赖数据集的结构特征。而本文依据异质信息网络的网络模式为节点构造的元结构，并且基于元结构提出的 MSIM 算法在两个数据集上都有较好的表现。因此，本文所提出的元结构是有意义的，它能够较好的保留节点的结构信息和不同类型节点间的异质关系，有利于影响的扩散，使传播更加广泛。图 3不同算法的扩散结果5.3效率对比本文在 DBLP 数据集中对比了不同算法之间的时间效率，将种子节点的数量 k 大小分别设为 10，20，30，40，50，对比不同算法选择出 k 个种子节点的运行时间，在表 3 中展示了在 DBLP 和 YELP 数据集上的运行结果。从表 3 中可以看出所有算法的运行时间随着 k 值的增大而增加，但增加幅度较小。ME 算法不需要考虑数据集中节点和边的异质性，有着较低的时间复杂度。Entropy 算法的运行时间主要消耗在构建同质子图以及确定子图中节点的传播影响概率。MPIE算法需要根据不同的元路径构建多个同质子图，且根据不同元路径构造子图的运行时间不同，总体时间复杂度过高，未加入对比。MSIM 算法的运行时间主要花销在构建节点的元结构，较于构造同质子图，有较低的时间复杂度。综合来看MSIM 算法在时间效率和性能上有着较好的折中。324表 3运行时间DBLPYELPMEMSIMEntropyMEMSIMEntropyk=100.0495s1.1610s7.6254s0.2153s23.4194s105.8951sk=200.0587s1.2822s7.8445s0.2276s24.1762s106.1121sk=300.0589s1.2909s7.9841s0.2289s25.0054s106.3454sk=400.0601s1.3772s8.0198s0.2304s25.9811s106.5981sk=500.0623s1.4076s8.1655s0.2321s26.6692s107.0370s图 4参数分析5.4参数影响分析本文设置元结构中不同的元路径的影响因子的和为 1，在 DBLP 数据集和 YELP 数据集中选取了 18 组参数，选出 k=50 个种子节点并比较它们的影响范围，实验结果如图 4 所示，其中 DBLP 横坐标表示元路径 APA，APCPA，APTPA 的影响因子，YELP 横坐标表示元路径 UU，UBU，UBCatBU，UB-CitBU 的影响因子。从图 4 中可以看出不同的影响因子比值会有不同的扩散结果。在 DBLP 网络中当影响范围达到最大值时，元路径 APA 的影响因子是三种元路径中的最大值，这表明具有公共论文作品的作者的关系在扩散过程中起着关键作用，在进行有效性验证实验采用 AP，APCPA，APTPA的影响因子为 0.7，0.2，0.1。在 YELP 网络中当影响范围达到最大值时，元路径 UU 具有最大的影响因子，这表明用户之间的交互在扩散过程中起着关键作用，在进行有效性验证实验时采用 UU，UBU，UBCaBU，UBCiBU 的影响因子为 0.5，0.4，0.09，0.01。6总结与展望本文研究了异质信息网络中的影响力最大化问题，旨在利用异质信息网络中丰富的语义信息度量节点的影响。在此基础上，提出了一种基于元结构的信息熵模型来度量异质信息网络中节点的影响力，即 MSIM。该算法通过为节点构造元结构来捕获异质信息网络中的丰富的语义信息，并通过路径熵与结构熵度量节点的影响。然后在真实世界数据集上进行实验，证明了所提方法的有效性。但在本文中，只考虑了相同类型对像的影响力最大化，因此在未来研究中，可以考虑包含有不同类型对象的节点集的影响力最大化，这有助于在实际系统中提供更准确影响度量。参考文献:1Domingos P M，ichardson M Mining the network value of custom-ersC SIGKDD，2001:5766 2Kempe D，Kleinberg J，Tardos E Maximizing the Spread ofInfluence through a Social NetworkJ Theory of Computing，2003，(4):1371463Aldawish，Kurdi H A Modified Degree Discount Heuristic for In-fluence Maximization in Social NetworksJ Procedia ComputerScience，2020，170:311316 4Qiao T，Shan W，Chang Z How to Identify the Most Powerful Nodein Complex Networks?A Novel Entropy Centrality ApproachJ Entropy，2017，19(11):614 5Chen W，Peng B，Schoenebeck G，et al Adaptive Greedy versusNonAdaptive Greedy for Influence MaximizationJ Proceedingsof the AAAI Conference on Artificial Intelligence，2020，34(1):5905976Tsai C W，Yang Y C，Chiang M C A Genetic NewGreedy Algorithmfor Influence Maximization in Social NetworkC IEEE Interna-tional Conferenceon Systems，2016 7Sun Y，Han J，Yan X，et al PathSim:Meta PathBased TopKSimilarity Search in Heterogeneous Information NetworksJ Pro-ceedings of the Vldb Endowment，2011，4(11):99210038Yang Y，Zhou L，Jin Z，et al Meta PathBased Information EntropyforModelingSocialInfluenceinHeterogeneousInformationNetworksC 2019 20th IEEE International Conference on MobileData Management(MDM)，2019(下转第 433 页)424存活节点较多时，网络工作的时间就越长，即网络生命周期越长，由图 4 可知，在仿真测试的 100s 之前所提算法可保证节点全部存活，100s 之后开始出现节点死亡，存活节点数量减少，但与其 它两种方法相比，所提算法的存活节点数量较多，表明网络生命周期长。4结束语目前网络多路径负载均衡算法存在端到端时延长、网络能量消耗大、分组丢失率高和网络生命周期短的问题，提出基于蚁群优化的网络多路径负载均衡算法，该算法在网络多路径负载均衡过程中引入蚁群优化算法，妥善解决了目前算法中的弊端。参考文献:1徐魏超，王冠凌，陈孟元 无人机协助下基于 SCKF 的无线传感器网络节点定位研究J 智能系统学报，2019，14(3):575581 2刁兴龙，余晓杉，刘勇，等 数据中心 Clos 网络负载均衡方案:问题、进展与展望 J 计算机学报，2020，43(12):22412258 3许红亮，杨桂芹，蒋占军 基于软件定义网络的数据中心自适应多路径负载均衡算法J 计算机应用，2021，41(4):11601164 4吕翊，朱博，吴大鹏 一种负载均衡的 FiWi 网络视频多路径传输机制 J 西安电子科技大学学报，2021，48(3):6370 5李锐，李晓卉，李小钰，等 面向 BLE 健康监护网络的负载均衡算法J 计算机工程与设计，2021，42(5):12011207 6李俊松，王雷，张靳予，等 基于改进 VECMP 的电力通信网络路由优化算法研究 J 电测与仪表，2021，58(7):136142 7郑增乾，王锟，赵涛，等 带宽和时延受限的流媒体服务器集群负载均衡机制J 计算机科学，2021，48(6):261267 8邱亚星，王希栋，边森，等 基于聚类分析和深度学习的多频多模网络负载均衡优化J 电信科学，2020，36(7):156162 9李长安，卢雪琴，吴忠强，等 基于蚁群算法优化反向传播神经网络的港口吞吐量预测J 计量学报，2020，41(11):13981403 10顾秋阳，琚春华，吴功兴 基于子图演化与改进蚁群优化算法的社交网络链路预测方法J 通信学报，2020，41(12):2135 11李伏平，罗周维，任洁，等 基于 AM 和蚁群优化算法的水轮机轴线智能检测系统研究J 中国农村水利水电，2021(8):151155，161 12崔莹 基于改进遗传蚁群算法的低压 PLC 网络路由方法J电力自动化设备，2022，42(3):210217 13应宜辰，吴命利，杨少兵，等 基于支持向量机蚁群算法的电气化铁路牵引负荷参数辨识J 铁道学报，2021，43(9):2431 14王长江，李本新，姜涛，等 基于改进模糊层次分析法的交直流受端电网交流故障筛选与排序J 电网技术，2021，45(10):40474056 15孙延浩，张琦，张芸鹏 基于模糊层次分析法和证据推理的铁路应急预案评价研究J 中国安全生产科学技术，2020，16(1):123129 作者简介苏富林(1975)，男(回族)，甘肃临潭人，硕士，副教授，研究方向:无线网络技术。冯桂莲(1979)，女(藏族)，青海湟源人，硕士，教授，研究方向:网络信息系统、图像处理。(上接第 424 页)9Kuhnle A，Alim M A，Li X，et al Multiplex Influence Maximizationin Online Social Networks with Heterogeneous Diffusion Models J IEEE Transactions on Computational Social Systems，2018:112 10Liu X，Wu S，Liu C，et al Social network node influence maximi-zation method combined with degree discount and local node opti-mizationJ Social Network Analysis and Mining，2021，11(1):31 11曹玖新，董丹，徐顺，等 一种基于 k核的社会网络影响最大化算法 J 计算机学报，2015，38(2):238248 12A T N，A Z G，A K Z，et al Using mapping entropy to identifynode centrality in complex networksJ Physica A:StatisticalMechanics and its Applications，2016，453:290297 13Li CT，Lin SD，Shan MK Influence propagation and maximi-zation for heterogeneous social networks C，2012:559560 14Sun Y，Han J Mining heterogeneous information networks:astructural analysis approachJ SIGKDD Explor，2012，14(2):2028 15Molaei S，Farahbakhsh，Salehi M，et al Identifying InfluentialNodes in Heterogeneous NetworksJ Expert Systems with Appli-cations，2020:113580 16Huang Z，Zheng Y，Cheng，et al Meta Structure:Computingelevance in Large Heterogeneous Information NetworksC，2016:15951604 作者简介徐智敏(1998)，男(汉族)，湖南省岳阳市人，硕士研究生，主要研究领域为社会网络分析，信息扩散。周丽华(1968)，女(汉族)，云南省昆明市人，教授，博士生导师，CCF 会员，主要研究领域为异质社会网络分析，多视角学习，数据挖掘。334