关联影响力传播最大化方法

社会网络中影响力传播最大化是社会网络分析领域所关注的重要问题。针对多个影响力同时进行传播,且影响力间存在传播促进的情况,提出关联影响力传播最大化问题。首先,对经典线性阈值模型进行扩展,提出关联影响力线性阈值模型对关联影响力传播过程进行建模;其次,定义了关联影响力传播最大化问题,证明了该问题是NP-hard的,以及问题目标函数满足子模性;再次,针对该问题提出基于结点激活贡献估计的求解算法;然后,利用结点激活贡献估计存在相互独立性,进一步提出了并行化求解算法,并在Spark GraphX并行图计算框架上实现了该算法;最后,在真实的社会网络数据集上,通过实验测试验证了所提出方法的有效性。

独立级联传播模型下的连续影响力最大化

影响力最大化是在社交网络中寻求一组最具有影响力的用户作为种子节点,通过种子节点向网络中传播信息,使得传播的范围最大化。现有的对影响力最大化的研究大多是针对每个节点,考虑是否将其作为种子节点。而在实际应用中,需要根据用户的影响力来赋予他成为种子的概率,使得根据这个概率分布得到的种子集合的影响力传播范围的期望值最大化,这就是连续影响力最大化问题。文中提出了一种独立级联传播模型下连续影响力最大化算法。该算法首先将上述问题抽象成一个约束优化问题,然后抽样若干个可能的种子集,并对每个可能的种子集估计影响的传播范围;使用梯度下降法,在每轮迭代中根据估计的传播范围计算各个方向的增量值,取最大增量的方向作为梯度进行目标函数值的迭代更新,从而得到目标函数值的最优解。在真实和虚拟网络上进行实验,结果表明,该算法在影响范围的期望值上优于Random,Degree,UD和CD等算法。

基于Transformer模型的社交网络影响力最大化算法

基于网络拓扑结构的社交网络影响力最大化算法受网络结构影响大,导致在不同规模、不同拓扑结构的社交网络上的性能不稳定。针对此问题,提出一种基于改进Transformer模型的社交网络影响力最大化算法。首先,基于K-shell分解法筛选社交网络中影响力高的节点;然后,运用随机游走策略发现候选节点的拓扑结构信息和连接框架信息;最终,对Transformer模型进行改进,使其支持可扩展的节点特征序列,利用改进Transformer模型预测社交网络中的种子节点。在6个不同规模的真实社交网络上完成了验证实验。结果表明,所提算法在不同规模、不同拓扑结构的社交网络上均实现了较好的影响力最大化性能,且大幅提高了种子节点识别的时间效率。

基于影响力最大化策略的抑制虚假消息传播的方法

随着各种社交媒体不断兴起,社交网络中消息传播所带来的安全问题显得愈发突出。其中,虚假消息的传播给网络空间的安全带来了极大威胁。为了在尽可能小地改变网络拓扑结构的前提下抑制虚假消息在网络空间的肆意传播,提出了一种基于影响力最大化的抑制虚假消息传播的方法。首先基于信息级联预测模型对消息传播进行预测,提出基于节点影响力最大化思想的两种算法Louvain Clustered Local Degree Centrality(LCLD)和Random Maximum Degree(RMD),得到影响力最大的节点集合;然后利用TextCNN对虚假消息进行分类识别,过滤掉节点集合中的少量关键节点。修改后的传播网络重新通过预测模型进行消息传播预测,结果虚假消息的传播相比于网络修改前得到了明显抑制。最后在真实数据集BuzzFeedNews上展开验证,首先通过实验验证基于信息级联的预测模型可以较准确地拟合实际传播;再将修改后的网络输入预测模型进行预测,结果显示虚假消息传播可得到抑制,表明采用影响力最大化算法删减少量包含虚假消息的节点可有效抑制虚假消息的传播,从而验证了所提方法的有效性。

基于局部传播中心性的影响力最大化算法

针对度中心性等方法选择种子节点时未考虑节点间传播概率及邻居拓扑连接的影响,提出局部传播中心性LPC(Local Propagation Centrality)的概念。为减少贪心算法时间复杂度高且不可扩展的问题,提出一种新的启发式算法IMLPC(Influence Maximization Algorithm based on LPC)。该算法通过计算每个节点的LPC,依次选择影响力最大的节点。实验结果表明,IMLPC的影响范围和运行时间较现有启发式算法相比有显著提升。在不同数据集下,IMLPC影响范围稳定、可扩展性好。

基于用户聚类的社交网络影响力最大化传播模型

本文针对的是社交网络中的影响力最大化问题。在经典线性阈值传播模型基础上,对社交网络中的用户进行聚类分析,并在此基础上提出改善的K-LT传播模型。在K-LT传播模型基础上,进一步提出K-KK影响力最大化算法。通过采集真实社交网络数据,进行试验仿真。试验结果表明,改进的K-KK影响力最大化算法与未改进时相比,算法性能有较好提升。

多社交网络的影响力最大化分析

影响力最大化旨在从网络中识别k个节点,使得通过这k个节点产生的影响传播范围最大.该问题在病毒营销领域具有重要的应用背景,它已经引起了学术界和工业界的广泛研究.该文作者观察到已有的研究工作大多数只是针对单一网络,即在给定的一个网络上识别k个节点使得其在该网络上产生最大的影响范围;然而,随着社交网络的普及,丰富多样的社交平台不断涌现,以满足不同的社交需求,这使得社交人群不被局限在一个网络内,而是分布在不同的社交网络上.这种变化的一个直接影响是使得基于病毒式营销的应用,例如单一网络上的产品推广愈加不能满足推广的广度需求,很可能是单一网络上的用户量不能达到推广的目标人群数量,又或者广告商期望在多个网络平台上找到k个用户以最大化影响传播范围.为此,在文中,作者研究多社交网络上的影响力最大化问题.该文首先仔细地研究了影响力最大化问题在单一网络和多社交网络上的不同,并提出了实体的自传播特性以在多个网络之间建立联系.之后,作者提出了多社交网络上的影响计算模型来建模节点间的影响力,然后扩展了基于树的算法模型以适应多社交网络上的影响力最大化问题.基于所提出的影响计算模型和扩展的基于树的算法模型,作者提出了多种策略的优化算法.例如通过深层次挖掘自模特性来避免冗余计算,通过使用影响增益上界近似准确的增益来加速种子选取过程等,最后通过真实数据集上的实验表明文中所提方法在性能和影响范围上都优于已有的算法.

一种新的复杂网络影响力最大化发现方法

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一,其研究在理论和现实应用中都有重大的意义.在给定s值的前提下,如何寻找发现s个最大影响范围的节点集,这是个组合优化问题,Kempe等已经证明该问题是NP-hard问题.目前已有的随机算法时间复杂度低,但是结果最差;其他贪心算法时间复杂度很高,不能适用于大型社会网络中,并且这些典型贪心算法必须以了解网络的全局信息为前提,而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的.我们提出了一种新的影响力最大化算法模型RMDN,及改进的模型算法RMDN++,模型只需要知道随机选择的节点以及其邻居节点信息,从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题,算法的时间复杂度仅为O(s log(n));然后,我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示,RMDN,RMDN++算法有着和现有典型算法相近的影响力传播效果,且有时还略优,同时在运行时间上则有显著的提高;我们从理论上推导证明了方法的可行性.本文所提出的模型算法适用性更广,可操作性更强,为这项具有挑战性研究提供了新的思路和方法.

基于LT^+模型的社交网络影响力最大化研究

影响力最大化问题的目标是寻找社交网络中一组种子结点集合,在给定的传播模型下,使得这些结点最终传播的影响范围最大。Kempe和Kleinberg提出的贪心算法可以获得很好的影响范围,但是因复杂度太高而并不适用于大型社交网络。Chen和Yuan等人基于线性阈值(LT)模型提出了构造局部有向无环图的启发式算法,但是LT模型只考虑了邻居结点的直接影响力,忽略了结点之间存在的间接影响力。因此,在LT模型的基础上,结合网络中结点之间存在的间接影响力,提出了LT+影响力模型,并利用构造局部有向无环图的启发式算法求解LT+模型的影响力最大化,称为LT+DAG算法。真实数据集上的对比实验表明,LT+DAG算法具有更好的影响范围以及较好的可扩展性。

国际中文教育促进中华文明传播力影响力提升策略研究

国际中文教育是增强中华文明传播力影响力的重要载体,增强中华文明传播力影响力为国际中文教育创新发展提供价值导向。文章首先诠释了国际中文教育和增强中华文明传播力影响力的内涵意蕴。其次,从逻辑关联和相互作用两个方面阐释二者之间的关系,逻辑关联表现为国际中文教育通过提升中文国际地位、促进文明交流互鉴、助力中外贸易畅通、促进中外民心相通等方式促进中华文明传播力影响力提升;相互作用表现为国际中文教育与增强中华文明传播力影响力互相影响,并在多元主体长期、稳定地支持下共同进步。最后,提出国际中文教育促进中华文明传播力影响力提升的路径:完善国际中文教育体系、提高国际中文教学质量、建强国际中文人才队伍、丰富国际中文产品服务以及强化现代科学技术赋能等。

基于社区划分的影响力最大化算法

影响力最大化问题是社会网络中的重要研究方向,其主要目的是获取社会网络中最有影响力的用户使通过这些用户获得影响传播范围的最大化。随着大数据时代的来临,传统的贪心算法因为复杂度高而不能有效解决大规模社会网络下影响力最大化的时间问题。提出一种基于社区划分的影响力最大化算法,利用影响概率将大规模社会网络分成较小的社区模块,并考虑社区边界节点之间的联系,从而最大程度缩小因社区划分造成的社区间的孤立。为进一步提高算法效率,在每个社区中以影响路径作为影响评估单元,同时对每个社区并行处理以便更高效地获取有影响力的节点。通过仿真实验验证了算法的可行性和高效性,其可以较好地适应大规模社会网络环境。

在影响力最大化问题中寻找种子节点的替补节点

在线社会网络的发展为市场营销提供了新的机遇和挑战.对于广告投放者来说,面临的问题是如何从一个有n个用户的社会网络中,选取k(0<kn)个有影响力的用户,称作种子节点,通过提供报酬、试用品等方式激活他们,让他们为产品做宣传,通过口口相传的方式使尽可能多的用户了解或者购买该产品.这个问题也被称作影响力最大化(Influence Maximization),简称IM问题.IM问题的相关工作往往会默认所选出的k个种子节点均可被激活.而在实际应用中,受各种因素的影响,t(0<tk)个种子节点很有可能无法激活.因此该文的研究问题是如何选取替补节点来代替不能被激活的种子节点,该文称该问题为在影响力最大化中寻找替补种子节点(Substitutes Discovery in Influence Maximization),简称SDIM问题.SDIM问题的提出有利于解决营销中面临的实际问题,帮助广告投放者更顺利地完成营销目标.为此,该文首先给出了SDIM问题的形式化定义,并提出对该问题求解的优化函数.在证明了该问题属于NP难的基础上,说明了基于该文提出的优化函数得到的贪心算法具有精度保证.该文首先利用社会网络的无尺度特性,给出了保留网络中度较大的节点作为初始候选节点集的策略,在此基础上,分别提出了3个求解SDIM问题的算法:(1)找出恰好t个替补节点的全局静态贪心算法GSG;(2)在选择种子节点的同时选取t′(t′t)个替补节点的预选式贪心算法GIA,可防止新选的t个替补节点中仍存在不能被激活的节点;(3)可以改善GSG算法执行时间且不影响精度的全静态算法AS.由于GSG运行时间过长,我们对其进行了CELF优化,在实验中我们称其为GSG-CELF.实验结果表明:根据节点度减少候选节点数量的方法不会影响各算法的效果,却可以有效地减少运行时间;GSG-CELF选出的替补节点的影响力很接近原始种子节点集的效果;GIA具有更好的鲁棒性,同时传播效果也十分接近GSG-CELF;AS与GSG-CELF这类有CELF优化的贪心算法相比,运行时间是GSG-CELF的10%~50%,且传播效果不受影响.

社会网络中基于社群衰减的影响力最大化算法

针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化(IMID)算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。

在线影响力最大化研究综述

影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。

社会网络中的影响力最大化问题

影响力最大化问题要求在网络中选取若干节点,使得以它们为初始节点进行信息传播时,在网络中产生的影响能够达到最大。影响力最大化问题是近十年来社会网络中的研究热点之一,其研究不仅具有理论意义,并且还具有应用前景。介绍了影响力最大化问题产生的背景,分析了问题的研究现状、研究用的几种主要传播模型以及解决问题的几种主要算法。最后,讨论了该研究面临的一些问题,对未来可能发展的研究方向进行了展望。

大规模时序图影响力最大化的算法研究

影响力最大化问题在社交网络中有着广泛的应用,一般地可以将社交网络抽象为静态图,影响力最大化问题是指在图中找出k个最有影响力的顶点,使得信息最大化传播.近年来对此问题的研究主要基于静态图,但是在现实中某些特定网络不可简单地被抽象为静态图,如社交网络及路网中节点间只在某些特定时间存在联系,即节点间的联系是具有时序性的.因此,本文研究了时序图影响力最大化问题,即在时序图上寻找k个顶点使得信息在特定的时间段内最大化传播.传播模型的选择和节点间传播概率的计算是影响力最大化问题的基础,由于基于静态图的IC(Independent Cascade model)传播模型无法应用于时序图,因此本文首先对IC模型进行改进,并提出了ICT(Independent Cascade model on Temporal graph)传播模型,使信息可以通过ICT传播模型在时序图上进行传播.而后通过改进PageRank算法来进行计算节点间的传播概率.然后在此基础上将时序图影响力最大化问题分为两步来进行实现.第一步首先研究时序图节点影响力的计算,并提出了用来计算节点影响力的SIC(Single Node Influence Computation)算法,然后通过对时序图中节点联系时序性这一特性的研究提出了一种改进算法ISIC(Improved SIC).第二步是在第一步结果的基础上来寻找k个种子节点,首先提出了一种基本的时序图影响力最大化算法BIMT(Basic Method for IMTG).但BIMT难以高效解决大规模时序图影响力最大化问题,因此通过优化节点边际效应的计算时间,提出了高效的AIMT(Advanced Method for IMTG)算法,然后通过避免某些节点边际效应的重复计算,对AIMT算法进行改进,从而提出了IMIT(Improved Method for IMTG)算法.最后通过大量实验验证了AIMT和IMIT两种算法高效性和扩展性,相比于BIMT算法,AIMT和IMIT可以更加快速地解决大规模时序图影响力最大化问题.

基于社交网络的影响力最大化算法

影响力最大化问题研究在给定传播模型下如何选取社交网络中的一组种子用户,使信息通过这些用户实现最大范围的传播。现有算法主要存在2个问题:一是由于影响范围有限、时间复杂度高,难以适用于大规模社交网络;二是仅局限于特定传播模型,只能解决单一类型社交网络下的影响力最大化问题,当使用在不同类型社交网络上时效果较差。对此,基于2个经典影响力传播模型,结合反向影响采样技术,提出一种高效的影响力最大化(MTIM)算法。为验证MTIM算法的高效性,将其与IMM、TIM和PMC等贪心算法,以及OneHop和Degree Discount等启发式算法在4个真实社交网络上进行对比实验,结果表明MTIM算法能够提供〔1-1/e-ε〕近似保证,显著扩大影响范围,并有效提高运行效率。

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系,但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。

地理社交网络中基于多目标组合优化的空间感知影响力联合最大化

影响力最大化问题旨在从社交网络中寻找若干具有高影响力的用户节点(种子),以触发最大化的信息传播规模.目前绝大多数工作认为社交网络中所有用户都拥有相同的影响力推广价值.然而,在基于位置的营销活动中,影响力推广的主体通常为带有位置标签的空间对象,考虑到用户在物理世界中的移动受限问题,空间对象仅能吸引其邻近范围内的潜在用户.因此,为了最大化市场营销潜力,商家通常需要同时拥有多个营销目标,譬如,连锁店企业对旗下的多家门店进行联合推广.不同的推广内容以及不同的影响力种子选择都将对营销推广的效益产生切实的影响.鉴于此,综合考虑商家在营销过程中对推广门店位置的选择以及在线上部署影响力传播种子的策略,在地理社交网络中研究基于多目标组合优化的空间感知影响力联合推广问题.首先分析了问题的理论难度,阐明了其与传统影响力最大化问题的区别.为支持高效且准确的问题求解,根据用户推广权重的差异,拓展了现有反向影响力采样(reverse influence sampling,RIS)技术,对不同位置和种子组合下的影响力传播收益进行理论保证下的上下界评估,并基于此提出了迭代处理算法框架,在多个轮次下实现高置信度保障的近似最优求解.最后,通过多组真实数据集上的实验,证明了所研究问题能在多目标组合下有效地提升空间感知的影响力推广效果,并验证了所提出算法的良好性能.

基于全局的引文网络影响力最大化算法

从大量的期刊论文中搜寻出最具有影响力的若干篇论文对于学术研究具有重要意义,但现有影响力最大化算法需要结合贪心算法,时间复杂度较高.依据论文引用网络中引用关系的时间单向性和无环特征,提出一种基于节点全局影响力的影响力最大化算法.该算法主要包括:①计算所有节点的全局影响力.结合引文网络的发表时间特性,构造上三角稀疏影响方阵.在线性阈值传播模型的基础上,利用节点间的直接、间接路径影响以及累积计算规则模拟影响力在网络上的传播过程.方阵每进行一次运算,会将全部节点的影响向下传播一跳,得到下一个路径的影响,并统计全部影响,最终得到表示所有节点全局影响力的方阵;②将全部节点按全局影响力排序.选择前n个节点作为候选节点来选取k个种子节点,在选取的过程中避免影响力较大节点的聚集情况.以真实的学术引文网络数据集为实验数据,将提出的算法与两种基准算法从激活范围和运行时间两个方面进行对比.实验结果表明,该算法大大降低了时间复杂度,且激活范围接近于贪心算法.