十亿级网络中的外部影响和级联规模估计
在社交网络中进行信息传播时,基于动态消息传递方法的算法可以用来估计独立级联模型中的影响力函数,从而代替对具有高计算复杂度的边缘概率的 Monte-Carlo 采样方法,同时提供一个解决计算效率问题的方法。
Dec, 2019
本文提出了一种基于随机算法来进行影响估计的方法,该方法可以在连续的时间传播网络中估计每个节点的影响力,通过大规模的实验数据表明,该方法不仅精度高,而且能够扩展到数百万个节点的网络上。
Nov, 2013
本文提出一种新的集成信息传递、影响排名和影响评估方法的算法 IRIE,用于在独立级联(IC)模型及其扩展中最大化影响力覆盖,并通过实验验证了 IRIE 在不同密度的网络和级联大小情况下比其他算法更具有鲁棒性和稳定性。
Nov, 2011
本文提出了一种基于网络降维的多目标进化算法来解决影响最大化问题,并通过 PageRank 等中心度量指标将降维后的解还原到原始网络中,实验结果表明,该方法在八个大型网络上表现出更高的效率和更少的计算时间。
Apr, 2022
本文提出一种基于采样的影响力最大化方法,对于给定的节点影响传播日志数据,采用新颖的网络推断方法,可以学习到网络结构和传播参数,避免网络结构和参数假设所带来的误差。相比以往的方法,本方法不需要最大似然估计和凸规划假设,可以在网络参数学习难度较高的情况下保证一个比较小的近似率。
Jun, 2021
本文研究独立级联模型中节点的长期影响,并通过一个矩阵的谱半径推导出理论上的界限,表明当该谱半径小于 1 时,行为是次临界的,而在一般网络中,此次临界状态大致的行为是 O(√n)。作者应用结果到随意的网络上的流行病学和渗透并导出一个暴露巨型连接元素出现的关键值的界限,在一大族网络中证明了作者上述边界的紧致性。
Jul, 2014
网络中传播的感染是一个基本过程,可以使用独立级联或代表性痕迹等概率模型来指定扩散模式,而影响查询和影响极大化是扩散研究中的基本计算问题,此文提出基于草图的影响最大化算法(SKIM),其性能接近精确贪心算法,但速度快了一至两个数量级,尤其是该算法还具有保证近似比,并使用预处理技术生成节点草图,使任何种子集合的影响都可以从草图上快速回答。
Aug, 2014
本研究发现,在有限网络中,初始节点的少量失败可能会导致跨越大部分节点的级联,级联大小的分布多为双峰形。通过推导出级联最终大小的全概率分布,证实了此现象的普遍性和重要性,同时着重探讨了全网络和星型网络两种拓扑极端情况下的级联大小分布。
Feb, 2018
本论文提出一种运行时间最优的算法,解决网络扩散下影响力最大化问题,通过寻找一组初始种子节点,使得预期级联大小最大化。该算法可在多项式时间内获得近乎最优的近似因子,在之前已知的运行时间 Omega (mnk POLY (1/epsilon)) 的算法的基础上,显著提高了算法速度和精度。
Dec, 2012
社交网络已经在广泛应用于人们之间的交流并且与传递意见和想法,其中影响最大化是广告推荐和个性化推荐的重要方式之一。此论文提出了一种基于社区结构的方法,利用 K-Shell 算法来生成种子节点和社区之间的连通性得分,以确保信息在社区内的适当传播,并使用熵来评估该方法在独立级联模型上的表现。作者的方法在八个公开网络上的实验中表现出色,比基线方法在四项评价指标上显著优越。
Nov, 2022