异质信息网络中基于元结构的影响力最大化_徐智敏.pdf
《异质信息网络中基于元结构的影响力最大化_徐智敏.pdf》由会员分享,可在线阅读,更多相关《异质信息网络中基于元结构的影响力最大化_徐智敏.pdf(6页珍藏版)》请在咨信网上搜索。
1、基金项目:国家自然科学基金项目(61762090,62062066,61966036);国家社会科学基金项目(18XZZ005);云南省高等学校科技创新团队项目(ITSTYN)。云 南 省 教 育 厅 科 学 研 究 基 金 项 目 资 助(2021Y026)。收稿日期:20210406修回日期:20210413第 40 卷第 2 期计算机仿真2023 年 2 月文章编号:10069348(2023)02042005异质信息网络中基于元结构的影响力最大化徐智敏,周丽华(云南大学信息学院,云南昆明 650504)摘要:影响力最大化问题旨在给定的网络中找到固定个数的活跃节点集,基于特定的传播模型,
2、使得最终被激活的节点数目达到最大。目前,异质信息网络的影响力最大化算法大多从网络中提取同质子图进行影响力最大化研究,时间复杂度较高,并且使用同质子图损失了节点原有的结构信息以及节点间潜在的语义关系。提出一种基于元结构的影响力最大化算法(MSIM),利用为节点构造的元结构描述不同类型节点之间的关系,较完整的保留网络的结构信息和异质信息,同时提出了路径熵与结构熵来度量节点的影响力。在真实数据集上的实验结果表明,MSIM 算法比传统的算法有着更好的影响范围和时间效率。关键词:异质信息网络;影响力度量;信息熵;元结构中图分类号:TP391文献标识码:BMetaStructureBased Influe
3、nceMaximization 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
4、,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 a
5、lgorithm 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
6、 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
7、 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;
8、Information entropy;Meta structure1引言社交网络的发展为信息的全球传播和新闻的有效传播带来了新的潜力,人们可以直接参与这些社交网络,建立自己的友谊网络,并相互分享他们的观点、见解和经验。而确定网络中有影响力的成员被视为这种潜力付诸行动的关键因素,影响力最大化问题由此被提出。Domingos 等人1 首先将影响力最大化问题建模为一个算法问题。Kempe 等人2 首次将影响力最大化问题定义为一个离散最优问题,并证明该问题是一个 NPhard 问题,同时提出了贪心算法得到了该问题的一个近似解。但贪心算法的时间复杂度过高,无法高效解决大规模网络问题。对此024研究者们
9、相继提出了许多启发式算法3,4 或改进贪心算法5,6 以提高运行效率。然而这些方法仅针对同质信息网络进行考虑,即只考虑了一种对象类型和一种关系类型,忽略了对象之间的异质关系和潜在的语义信息。异质信息网络7 是一种包含了多种对象类型和多种关系类型的信息网络,能够更加合理的描述真实的社会网络。因此,在异质信息网络上进行影响力最大化研究更具有现实意义。近些年来,影响力最大化研究的焦点逐渐转向异质信息网络。杨等人8 通过多种元路径提取不同对象之间关系,来度量节点的影响力。Kuhnle 等人9 提出了多重网络上的影响力最大化算法等。但由于异质信息网络具有复杂的网络结构,如何高效的利用异质信息一直是异质信
10、息网络分析的难点问题。本文的目的是在异质信息网络中研究相同类型对象的影响力最大化问题,并提出了基于元结构的影响力最大化算法(MSIM)。异质信息网络中包含了丰富的语义信息,元路径可以有效地捕获源对象和目标对象间的单一关系,但无法捕获到它们之间的复杂关系。而元结构本质上可以看作多条元路径的集合,能够方便的表达对象间复杂的关系。因此,在 MSIM 算法中采用元结构存储目标对象与网络中所有类型对象间的语义关系,并且引入信息熵来度量节点的影响力,提出了路径熵度量不同元路径对源节点的影响贡献,然后整合了元结构中不同元路径的路径熵提出了结构熵度量源节点的最终影响。最后在真实数据集上进行实验,验证了该算法的
11、有效性。本文的贡献主要包含以下三个方面:1)提出了一种基于元结构的信息熵影响力最大化算法(MSIM),该算法为每个目标类型节点构造一个元结构,存储不同对象之间的异质关系;2)提出了路径熵(PE)和结构熵(SE)来评估一个节点在异质信息网络中的重要性,PE 值反映了单条路径对源节点的影响,SE 值反映了局部结构对节点的影响;3)在两个真实数据集上验证了 MSIM 算法的有效性和效率,并证明 MSIM 算法在效率和性能上有较好的折中。2相关工作影响力最大化问题在 2003 年首次被定义为一个算法问题,Kempe 等人2 证明了该问题是一个 NPhard 问题,并提出了贪心算法,该算法具有高精度的近
12、似结果,但也有着高昂的时间代价,难以拓展到大规模网络问题的应用。为了克服传统的贪心算法的低效性,研究者们对传统的贪心算法进行了一系列的改进,或者提出了新的启发式算法。刘等人10 基于局部节点优化和折扣度构造了节点近似影响值函数来计算局部节点的影响值。曹等人11 提出了基于核数层次特征和影响半径的启发式算法。聂等人12 将信息熵引入复杂网络以计算节点的影响力,使用信息熵度量不同邻居对节点的影响。然而这些方法均为同质信息网络的研究方法,未考虑到不同类型对象之间的连接关系。随着社交媒体的快速发展,异质信息网络已被提议作为真实世界图或网络的一般表示。目前关于异质信息网络的研究主要集中在聚类、分类、相似
13、性搜索链路预测等,而关于异质信息网络的影响力最大化研究相对较少。李等人13 通过限制相同类型节点间的最短路径从异质信息网络中抽取一个同质子图,并根据节点对在异质信息网络中的路径来确定子图中节点间的影响。杨等人8 利用元路径在异质信息网络中提取出多个同质子图进行影响力最大化研究,但使用独立的元路径进行对象之间关系的提取,会忽略一些对象被多条边共享的问题,会导致这些信息的损失。3相关概念本节主要介绍异质信息网络和信息熵中的基本概念,这些概念是本文工作的基础。定义 1异质信息网络7:异质信息网络是具有一个对象类型函数 和一个关系类型函数 的有向图 G=(V,E,T,)。其中 V 是节点集,E 是边集
14、,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、等人15 将异质信息网络中的元路径区分为单介质元路径和多介质元路径,仅通过一个中介相连的元路径为单介质元路径,如在 DBLP 网络中,对于元路径 APA(作者,论文,作者),作者之间仅通过论文节点相连,称之为单介质元路径,反之通过多个介质相连的称为多介质元路径。定义 4元结构16:元结构可以看作由多条具有公共节点组成的有向无环图,形式化地,元结构可以记为 M=(VM,EM),其中 VM是节点集合,EM是边集合。124定义 5信息熵4:信息熵是一个系统的信息含量的量化指标,常用来作为系统方程优化的目标或参数选择的判据。乔等人4 将信息熵引入复杂网络以计算节点的影响力。对于网络中的任意节点 v 的
16、信息熵可以由式(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表示传
17、播概率MSv表示节点 v 的元结构PEWv表示元路径 W 对节点 v 的路径熵SEv表示节点 v 的结构熵4.1问题定义本文选择以异质信息网络中的信息传播为例,研究异质信息网络的影响力最大化问题。给定一个异质信息网络 G=(V,E,T,),本文的目的是在考虑在度量节点的影响力时利用异质信息网络中丰富的语义信息,考虑不同类型节点之间的影响,在特定的扩散模型下,选择出具有最大影响范围的相同节点类型的子集。4.2构造元结构为了度量节点的影响力,本文为每一个目标类型节点 uV 构造一个元结构 MSu,并且将 u 作为元结构中的源节点,根据网络模式不同类型节点之间的关系,查找出节点 u的出邻居加入 MS
18、u,然后根据网络模式中 u 的出邻居所属的节点类型与其它节点类型节点的关系,将出邻居的出邻居添加至 MSu,直至遍历网络模式中 u 与所有类型节点之间的关系。在构造元结构的过程中保留节点本身的度的信息。如图 2 描述了图 1 中作者 Ying 的元结构的构造过程。本文通过网络模式提取出目标节点的元结构能够有效的保留局部结构信息和节点间的异质信息,而本文对节点影响力的度量也将以节点的元结构为基础。4.3路径熵与结构熵元路径可以提取源节点与目标节点的关系,对于以 v1为源节点的元路径 W,路径 w(v1v2vn)是 W 的一条路径实图 2元结构构造示例例,本文由式(2)计算元路径 W 对源节点 v
19、1的路径熵。PEWv1=wWHw=wW pv1v2pvn1vnlog(pv1v2pvn1vn)(2)其中Hw路径实例w的传播概率,puv=dulNvdl,Nv是v节点直接邻居的集合,du是 u 节点的度。社交网络中的三度影响力理论指出信息在网络传播过程中存在衰减,并发现三度之内的节点属强连接关系,而距离三度之外的节点间为弱连接关系,信息在弱连接中基本不产生影响。因此,本文对多介质元路径进行“折半”处理,只计算其前驱的路径熵,如对于元路径 APTPA,只计算元路径APT 对源节点所提供的路径熵。在本文构造的所求影响力最大化的目标类型节点的元结构中能够有效的存储多介质元路径的前驱信息,以及目标节点
20、与其它类型节点间的联系。对于节点 v1的元结构 MSv1,综合由不同元路径 W 的路径熵得出 v1的结构熵,由式(3)计算节点的结构熵。SEv1=WiMSv1iPEWiv1(3)其中 i为元路径 Wi的影响因子。4.4MSIM 算法描述本文提出了在异质信息网络中基于元结构的影响力最大化算法(MSIM)。MSIM 算法构造节点的元结构,并定义节点的结构熵度量源节点的影响力,也考虑了不同类型的元路径对节点影响力的影响。元结构的构建有利于根据不同的扩散任务,有针对性的选择种子节点。如在 DBLP 网络中选择作者节点作为影响力最大化的研究目标,那么 MSIM 通过构造作者节点的元结构来度量作者的影响力
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息网络 基于 结构 影响力 最大化 徐智敏
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。