提出一种基于迭代排序的算法 IMRank,通过同时利用贪心算法和启发式算法,以节点排序的感染影响力边际作为参考,高效地解决了社交网络中的最大影响力问题。经过对大规模真实社交网络的广泛实验,IMRank 总是以极高的准确性实现的同时,计算成本大大降低。
Feb, 2014
本文研究了鲁棒社交网络算法的影响最大化问题,定义了鲁棒影响最大化框架,并提出了一种能够在多种影响模型和参数设置下提供保证的近似算法,该算法的性能在多组真实数据集上得到了验证。
Feb, 2016
本文从博弈的角度研究影响最大化问题,提出了一个协调博弈模型,并在该模型下研究了影响最大化的难度和贪心算法的逼近保证。实验结果表明,优化后的算法比其他启发式算法快三个数量级,并且大大优于原始贪心方法。
Oct, 2018
社交网络已经在广泛应用于人们之间的交流并且与传递意见和想法,其中影响最大化是广告推荐和个性化推荐的重要方式之一。此论文提出了一种基于社区结构的方法,利用 K-Shell 算法来生成种子节点和社区之间的连通性得分,以确保信息在社区内的适当传播,并使用熵来评估该方法在独立级联模型上的表现。作者的方法在八个公开网络上的实验中表现出色,比基线方法在四项评价指标上显著优越。
Nov, 2022
本论文提出一种运行时间最优的算法,解决网络扩散下影响力最大化问题,通过寻找一组初始种子节点,使得预期级联大小最大化。该算法可在多项式时间内获得近乎最优的近似因子,在之前已知的运行时间 Omega (mnk POLY (1/epsilon)) 的算法的基础上,显著提高了算法速度和精度。
Dec, 2012
本文提出一种基于采样的影响力最大化方法,对于给定的节点影响传播日志数据,采用新颖的网络推断方法,可以学习到网络结构和传播参数,避免网络结构和参数假设所带来的误差。相比以往的方法,本方法不需要最大似然估计和凸规划假设,可以在网络参数学习难度较高的情况下保证一个比较小的近似率。
Jun, 2021
网络中传播的感染是一个基本过程,可以使用独立级联或代表性痕迹等概率模型来指定扩散模式,而影响查询和影响极大化是扩散研究中的基本计算问题,此文提出基于草图的影响最大化算法(SKIM),其性能接近精确贪心算法,但速度快了一至两个数量级,尤其是该算法还具有保证近似比,并使用预处理技术生成节点草图,使任何种子集合的影响都可以从草图上快速回答。
Aug, 2014
本文介绍了在社交网络营销环境下,针对影响最大化问题提出了一种在线学习的解决方案,通过多次试验选择种子节点,采用探索 - 利用策略进行影响活动,使用用户反馈信息更新影响概率,相对于传统影响最大化方法在信息不完整情况下效果更佳。
Jun, 2015
该论文考虑了社交网络中的影响最大化问题,提出了一种可快速从数据中学习的新颖参数化框架并开发了 LinUCB 算法来解决问题。
Mar, 2017
本文介绍了一个名为 TIM 的算法用于解决影响力最大化问题,可以处理百万节点的图,并融合了独立级联模型和线性阈值模型以及其他扩散模型,该算法通过新颖的启发式方法显着提高了其经验效率而不影响其渐近性能。
Apr, 2014