基于反向可达集的影响力最大化算法

现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。     

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.     

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

首先研究了目前影响力最大化问题的解决方案,并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现,弱连接可以有效地打通社交网络中不同社团之间的信息壁垒,使得信息在不同社区间流通.利用弱连接的这一作用,同时基于贪心思想,提出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算法.     

异质信息网络中基于有向无环图的影响力最大化算法

针对异质信息网络中的影响力最大化(IM)问题,提出了一种基于有向无环图(DAG)的影响力最大化算法(DAGIM).首先基于DAG结构度量节点的影响力,然后采用边际增益策略选择影响力最大的节点.DAG结构表达力强,不仅描述了不同类型节点之间的显性关系,也刻画了节点之间的隐性关系,较完整地保留了网络的异质信息.在三个真实数...     

边缘覆盖去重的社交网络影响力最大化算法

影响力最大化问题是在社交网络中寻找具有最大影响范围的节点集。针对启发式算法准确度相对较差的问题,现有的研究考虑了影响范围重合,但忽略了边缘贡献导致的节点影响力过量评估。重点研究了在考虑边缘贡献的情况下,如何选取影响范围最大的节点集合。采用启发式算法的思想,首先计算节点全局和邻近影响力来评估节点信息传播影响力,通过去除已选节点影响范围并更新网络的方式,消除边缘贡献对节点影响力评估的干扰,在独立级联模型基础上提出了基于边缘去重的节点影响力最大化算法。仿真结果表明所提出算法相比其他算法,能够有效增大节点信息传播影响范围。     

基于跳步的增量式影响力最大化算法

对动态在线社交网络中的影响力最大化问题进行研究,提出一种基于跳步的增量式算法,快速跟踪动态网络最具有影响力的用户集。为应对网络结构变化,基于跳步,一方面评估变化用户影响力上限值,快速识别和保留无需变动的影响力用户;另一方面增量式地计算有潜力用户的实际影响力,替换不再属于最具影响力的用户。在真实数据集上进行实验和分析,其结果表明,相比其它最新同类算法,所提算法能以更快速度在动态网络中维护最具影响力用户集。     

用户互动表示下的影响力最大化算法

影响力最大化问题旨在社交网络中选取一组有效的种子用户,使信息通过这些用户能够达到最大范围的传播.传统影响力最大化问题的研究依赖于特定的网络结构和扩散模型,而经过人工处理的简化网络和建立在假设之上的扩散模型在评估用户真实影响力时存在较大局限.为解决该问题,提出一种基于用户互动表示的影响力最大化算法(IMUIR).首先,根据用户互动痕迹进行随机采样,构造用户上下文对,并经过SkipGram模型训练得到用户的向量表示;然后,利用贪婪策略,根据源用户自身的活跃度和这些用户与其他用户的交互联系度选择最佳种子集.为验证IMUIR的有效性,将其与Random、AC、Kcore和Imfector在2个拥有真实互动信息的社交网络上进行对比实验.结果表明,利用IMUIR选出的种子集质量更高,产生的影响传播范围较广,且在2个数据集上表现稳定.     

用户互动表示下的影响力最大化算法

影响力最大化问题旨在社交网络中选取一组有效的种子用户,使信息通过这些用户能够达到最大范围的传播.传统影响力最大化问题的研究依赖于特定的网络结构和扩散模型,而经过人工处理的简化网络和建立在假设之上的扩散模型在评估用户真实影响力时存在较大局限.为解决该问题,提出一种基于用户互动表示的影响力最大化算法(IMUIR).首先,根据用户互动痕迹进行随机采样,构造用户上下文对,并经过SkipGram模型训练得到用户的向量表示;然后,利用贪婪策略,根据源用户自身的活跃度和这些用户与其他用户的交互联系度选择最佳种子集.为验证IMUIR的有效性,将其与Random、AC、Kcore和Imfector在2个拥有真实互动信息的社交网络上进行对比实验.结果表明,利用IMUIR选出的种子集质量更高,产生的影响传播范围较广,且在2个数据集上表现稳定.     

基于结构洞和度折扣的影响力最大化算法

在社会网络影响力最大化（IM）算法中,针对目前仅选取局部最优节点造成的影响范围较小的问题,综合考虑核心节点和结构洞节点的传播优势,提出了一种基于结构洞和度折扣的最大化算法（SHDD）。首先,该算法将结构洞思想和中心度思想互相融合应用到影响力最大化问题中,并找出能将结构洞节点和核心节点综合发挥最大传播作用的α因子,使得信息更大范围地扩散从而扩大整个网络的影响范围。其次,为突出两个思想融合的优势,将二度邻居的影响添加到结构洞评价标准中来选取结构洞节点。在不同规模的数据集上实验结果表明,与DegreeDiscount算法相比,SHDD在没有增加过多时间开销的同时扩大了影响范围;与基于结构的贪心（SG）算法相比,在聚类系数较大的网络中SHDD扩大了影响范围并降低了时间开销。SHDD在α因子取0.6时能最大限度地发挥结构洞节点和核心节点融合的作用并且在聚类系数较大的社交网络中能更加稳定地扩大影响范围。     

基于渗流模型的影响力最大化算法

多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优,忽略网络自身传播影响力的固有能力。本文对网络进行渗流模拟,计算渗流后网络的主连通分量随着传播概率改变的趋势,并且求得主连通分量大小增加开始变快的相变点,从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算,求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。在kareteclub、football、highschool和socdolphins社交网络数据集上进行实验,验证了该方法的有效性。     

话题感知下的跨社交网络影响力最大化分析

随着各种社交网站的不断涌现,在多社交网络上找到影响传播范围最大的一组用户,对产品推荐或产品推广具有重要作用。为提高产品推荐或推广的广度和精准性,提出了一种跨社交网络基于话题感知的影响力最大化处理方法M-TLTGreedy。首先,根据跨社交网络中的文本语义信息和用户间的社会关系来评价多社交网络中用户间关系,以此构建一个基于话题的跨社交网络图;然后,在线性阈值模型的基础上,设计了一个基于话题感知的跨社交网络影响力最大化模型M-TLT(multiple-topic linear threshold);接着,基于M-TLT模型,利用改进的启发式算法,进行初始用户集的选取;最后,基于大量数据集的实验,证明了该算法无论在影响范围和时间效率上均表现良好。