基于局部域的影响力最大化算法

用户影响力度量是影响力最大化问题的核心,与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标,其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高,局部性指标通常忽略或弱化了网络中的自环和多边现象,导致对节点影响力的度量不全面,限制信息最终传播范围。结合三度分隔原理,提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象,根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域,使用节点在局部域内的影响力近似其在全局范围内的影响力,并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子,根据重叠比因子决定是否将此候选种子节点选作种子节点,控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明,与MaxDegree、PageRank等算法相比,该算法能有效识别高影响力节点群体,扩大信息传播范围,且具有较低的时间复杂度。     

基于微博网络的影响力最大化算法

由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中Top-K节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用于用户影响力度量的WIR算法;根据得到的WIR值提出了符合微博特性的影响力传播模型,运用贪婪算法挖掘出微博网络中的Top-K节点。以爬取到的新浪微博数据进行了模拟验证,结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想,GABE较好地解决了微博网络中的影响力最大化问题。     

基于领域划分的微博用户影响力分析

近年来微博作为一种新兴的社交网络逐渐被广大用户使用.微博信息简短、更新迅速、包含信息量大,给微博用户获取信息带来了诸多不便,因此,利用影响力分析的手段找到具有较大影响力的微博用户具有重大意义.微博内容较传统的媒体信息具有较强的时效性和权威性,同时微博用语也极其不规范,这给微博用户影响力的分析带来了极大的困难.首先对获取的微博用户信息进行领域的划分,采用基于微博内容和用户关注的方式将用户归类到其所属的领域.其中,采用新词发现以及特征扩展的方法来提高划分结果的准确性.然后,对各个领域的用户进行影响力分析,提出3种影响力传播模型,用户最终的影响力大小根据3种模型的结果进行加权计算.最后对实验结果进行分析、比较,证明了计算用户影响力的方法能取得较优的结果.     

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

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

异质信息网络中基于网络嵌入的影响力最大化

针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型,且不同类型节点在原始空间无法直接度量的问题,提出了一种异质信息网络中基于网络嵌入的影响力最大化模型（influence maximization based on network embedding,IMNE）,用于选择初始扩散节点实现影响力最大化。该模型不仅可以在对异质信息网络进行编码的同时表征异质信息网络中潜在的信息,还可以捕获不同类型节点间影响力的不确定和复杂性。在3个真实数据集上的实验验证了IMNE算法的有效性。     

社会网络中基于主题的影响力最大化算法

为了解决现有的影响力最大化研究没有充分考虑主题对影响力节点挖掘的影响而导致特定主题下节点集合的影响范围不大这一问题,本文提出了一种社会网络中基于主题的影响力最大化算法TIM。该算法首先根据主题敏感阈值对初始节点集进行预处理,剔除干扰节点,再在新的节点集合上分两个阶段进行节点挖掘。第一阶段挖掘主题权威性大的节点,第二阶段挖掘主题影响增量最大的节点,最后综合两个阶段的节点作为结果集并进行实验验证。实验结果表明,相比其他算法,TIM算法挖掘的节点集合在特定主题下的影响范围更大,时间复杂度更低。     

基于社交网络弱连接属性的影响力最大化算法

首先研究了目前影响力最大化问题的解决方案,并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现,弱连接可以有效地打通社交网络中不同社团之间的信息壁垒,使得信息在不同社区间流通.利用弱连接的这一作用,同时基于贪心思想,提出BWTG（base-on weak tie greedy)算法来解决影响力最大化问题,并根据解空间的不同,把BWTG算法分为BCWTG（base-on complete weak tie greedy)和BNCWTG（base-on not complete weak tie greedy)两种算法.影响力最大化问题的传统评价指标有两种：时间复杂度和最终激活节点数,但考虑到实际情况,定义了ANNI（actived nodes/node influence)这一新的评价指标,用于衡量回报与付出之比.为了验证BCWTG和BNCWTG算法的性能,在不同类型、不同规模的真实数据集中对算法进行实验验证,在时间复杂度、最终激活节点数和ANNI这3个方面与经典的Greedy算法进行对比,实验结果表明,BCWTG算法和BNCWTG算法在运算时间和ANNI方面有所提高,最终激活节点数方面却弱于Greedy算法,但当满足一定条件时,BCWTG和BNCWTG算法在最终激活节点数方面也能接近Greedy算法.     

基于反向PageRank的影响力最大化算法

针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题,提出一种混合PageRank和度中心性的启发式算法（MPRD）。首先,基于PageRank,引入一种反向PageRank思想来评估节点影响力;然后,结合局部指标度中心性,设计一种混合的指标来评估节点的最终影响力;最后,通过相似性方法去掉影响力重合严重的节点,选出种子节点集。在6个数据集和两种传播模型上进行实验,实验结果表明,所提的MPRD在传播范围上优于现有的启发式算法,在时间效率上比贪心算法快四、五个数量级,在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。     

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

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

社会网中基于主题兴趣的影响最大化算法

影响最大化问题是在社交网中寻找对传播项最具影响力的种集,使得传播项的传播范围最大.目前的研究只考虑了传播项上主题的分布,而忽略了用户本身的兴趣分布.在传播项的主题分布和用户的兴趣分布都被考虑的条件下,研究如何选取最具影响力的种集.首先提出了基于主题兴趣的独立级联传播模型TI-IC,并利用期望最大化算法求学习TI-IC模型参数;然后在TI-IC模型基础上提出了基于主题兴趣的影响最大化问题TIIM,并提出了求解TIIM问题的启发式算法ACG-TIIM.ACG-TIIM首先构造以每个用户为根的可达路径树,快速粗略预估每个用户的影响范围;然后根据预估的影响范围排序所有结点并选择少量结点作为候选种子;最后使用带有EFLF优化的贪心算法从候选种子中选择最具影响力的种集.多个真实数据集上的实验结果表明：在描述传播规律和预测传播结果方面,TI-IC模型优于经典的IC模型和TIC模型.ACG-TIIM算法可以有效并高效地求解基于主题兴趣的影响最大化问题.     

基于信息偏好的影响最大化算法研究

实证研究表明,社会个体对于不同主题的信息有着不同的偏好,这对于社会网络中的信息传播过程起着非常重要的作用.影响最大化是社会网络信息传播领域中关于影响结点集挖掘的热点课题.它会从社会网络中寻找最具影响力的结点子集,以这些结点为目标进行影响传播时会获得最大的影响范围.以前关于影响最大化算法研究的大部分工作没有考虑社会个体的信息偏好,这大大降低了结果的准确性.为了提高影响最大化算法的效率和种子集的影响范围,提出一种基于信息偏好的2阶段启发式影响结点挖掘策略L_GAUP：第1阶段,基于网络中各结点对于信息主题的偏好程度,得到易感染结点网络;第2阶段,在易感染网络中,基于贪心策略进行影响结点的挖掘.实验中,在数据集douban上实现了L_GAUP,GAUP和CELF算法.实验结果表明,与基准算法GAUP相比,L_GAUP不仅在影响范围指标ISST和IS上有着更好的表现,在效率上也有大幅度的提高.     

基于局部概率解的免疫遗传影响力最大化算法

影响力最大化问题是在复杂社会网络中选择一小部分用户在特定传播模型下最大化影响扩散。基于贪心的蒙特卡洛模拟方法在理论上保证近乎最优的解决方案,但算法运行效率很低。虽然已经开发出许多没有理论保证的启发式方法,但都大大降低了解决方案的质量。为解决该问题,提出局部概率解策略计算节点集的影响力,其性能近似于蒙特卡洛模拟,并且提出基于免疫遗传的影响力最大化算法。在4个真实数据集上的实验表明所提算法在解决影响力最大化问题上的高效性。在影响力传播范围上,和当前表现最好的CELF算法有极其相近的性能,且运行效率比CELF算法快大约5个数量级。     

基于情感的社会网传播模型及影响最大化算法研究

针对社会网传播领域的影响最大化问题的研究，将节点本身具备的情感对事件传播的影响力进行了忽略，提出了基于情感的社会网传播模型（Emotion Independent Cascade model，E-IC），关于E-IC模型重点强调了情感影响的最大化基本问题（Influence Maximization Problem based on Emotion，IMPE），在传播整个进程中，融合了用户位置的计算值、后置情感的计算值以及交互概率值。论证并确认基于情感的社会网传播模型问题就是NP-hard问题，并给出近似算法EMS-Greedy。在训练集上调整模型参数，使得传播过程更符合传播规律，通过大规模真实数据集上的实验验证了E-IC模型的有效性。与其他模型相比，E-IC模型在传播范围上扩大了7%左右。     

面向微博的情感影响最大化模型

社交网络中影响最大化问题是寻找具有最大影响范围的节点。影响最大化的大部分求解算法仅仅依赖社交网络图。基于微博的转发关系树和微博内容的情感倾向性,以及用户的社交网络图,提出了一个能够刻画用户情感影响的情感影响最大化模型——情感影响分配模型(sentiment influence distribution,SID),证明了SID模型下的情感影响最大化问题是一个NP难问题,给出了一个具有精度保证的贪心算法。在真实的微博数据上的实验结果表明,SID模型能够有效地找出情感影响最大化的节点集,同时具有很高的扩展性。     

基于桥梁用户的多社交网络影响最大化

单社交网络影响最大化问题已经得到了学术界的广泛关注与研究,然而如今多社交网络之间呈现信息互通的趋势.多社交网络中存在的桥梁用户（Bridge User,BU）（即同时拥有多个社交网络账户的用户）,可将信息从一个社交网络分享至另外一个社交网络,信息传播不再局限于单个网络.本文针对多社交网络信息影响最大化进行了相关研究,分析了桥梁用户在多社交网络信息传播中的作用,提出了基于桥梁用户的多社交网络聚合算法,并在得到的聚合图上对多社交网络影响最大化问题进行求解.仿真实验对多社交网络影响最大化问题进行了求解,并证实了桥梁用户在多社交网络信息传播时的作用.     

一种面向团体的影响最大化方法

影响最大化旨在从给定社会网络中寻找出一组影响力最大的子集.现有工作大都在假设实体点（个人或博客等）影响关系已知的情况下,关注于分析单个实体点的影响力.然而在一些实际场景中,人们往往更关注区域或人群等这类团体的组合影响力,如：户外广告,电视营销,疫情防控等.本文研究了影响力团体的选择问题：（1）基于团体的关联发现,我们建立了团体传播模型GIC（Group Independent Cascade）;（2）根据GIC模型,我们给出了贪心算法CGIM（Cascade Group influence maximization）搜索最具影响力的top-k团组合.在人工数据和真实数据上,实验验证了我们方法的效果和效率.     

基于社区与结构熵的异质网络影响力最大化

影响力最大化的目的是在网络中发现能够触发最大数量的剩余节点参与到信息传播过程的一小群节点.目前异质信息网络中影响力最大化的研究通常从网络中抽取同质子图、或基于节点局部结构的元路径进行节点影响力的评估,没有考虑节点的全局特征和网络中高影响力节点间的集群现象给种子集合最终扩散范围造成的影响损失.文中提出了一种基于社区与结构熵的异质信息网络影响力最大化算法,该算法能够有效地从局部和全局两个方面度量节点的影响.首先,通过构建元结构保留节点在网络中的局部结构信息和异质信息度量节点的局部影响;其次,利用节点所属社区在整个网络中的权重占比对节点的全局影响进行度量;最后,综合求出节点的最终影响并选出种子集合.在真实数据集上进行的大量实验结果表明所提算法有较好的有效性和效率.