影响力最大化:近似最优时间复杂度 meets 实际效率
本论文提出一种运行时间最优的算法,解决网络扩散下影响力最大化问题,通过寻找一组初始种子节点,使得预期级联大小最大化。该算法可在多项式时间内获得近乎最优的近似因子,在之前已知的运行时间 Omega (mnk POLY (1/epsilon)) 的算法的基础上,显著提高了算法速度和精度。
Dec, 2012
本文针对在社交网络中的时间关键影响最大化问题,扩展了独立级联模型和线性阈值模型,设计了两种启发式算法解决了在规定期限内达到最大影响力传播的问题。
Apr, 2012
本文从博弈的角度研究影响最大化问题,提出了一个协调博弈模型,并在该模型下研究了影响最大化的难度和贪心算法的逼近保证。实验结果表明,优化后的算法比其他启发式算法快三个数量级,并且大大优于原始贪心方法。
Oct, 2018
本文研究了鲁棒社交网络算法的影响最大化问题,定义了鲁棒影响最大化框架,并提出了一种能够在多种影响模型和参数设置下提供保证的近似算法,该算法的性能在多组真实数据集上得到了验证。
Feb, 2016
本研究针对扩散网络中寻找最佳源节点集合,以限定时间内最大化信息、影响力和疾病传播等问题展开研究,利用连续时间马尔可夫链可以解析计算扩散过程中源节点覆盖数量的平均值,并发现选择时间连续状态下的最具影响力的源节点是 NP-hard 的,因此提出了一种高效的近似算法,并在实验中针对合成和真实扩散网络展示出其明显优越性。
May, 2012
本文提出了一种基于随机算法来进行影响估计的方法,该方法可以在连续的时间传播网络中估计每个节点的影响力,通过大规模的实验数据表明,该方法不仅精度高,而且能够扩展到数百万个节点的网络上。
Nov, 2013
本研究提出了一种应对节点级反馈的独立级联模型(IC)的在线影响最大化问题的算法,通过使用该算法,可以在社交网络中找到最优种子节点来刺激信息在网络中最大范围的传播。
Sep, 2021
本文主要研究了在线影响最大化问题,并提出了 LT-LinUCB 算法与 OIM-ETC 算法,其中前者考虑了节点级反馈,后者简单易用、无需离线计算且具有较低的反馈要求。
Nov, 2020
本文介绍了在社交网络营销环境下,针对影响最大化问题提出了一种在线学习的解决方案,通过多次试验选择种子节点,采用探索 - 利用策略进行影响活动,使用用户反馈信息更新影响概率,相对于传统影响最大化方法在信息不完整情况下效果更佳。
Jun, 2015
本文提出一种基于采样的影响力最大化方法,对于给定的节点影响传播日志数据,采用新颖的网络推断方法,可以学习到网络结构和传播参数,避免网络结构和参数假设所带来的误差。相比以往的方法,本方法不需要最大似然估计和凸规划假设,可以在网络参数学习难度较高的情况下保证一个比较小的近似率。
Jun, 2021