基于三元闭包的社交网络影响力最大化研究

作     者：杨杰 

作者单位：中国矿业大学 

学位级别：硕士

导师姓名：王志晓

授予年度：2023年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：三元闭包 影响力最大化 独立级联模型 启发式算法 自适应 

摘      要：社交网络(例如微博和Twitter等)在人们的日常交流中发挥着重要作用。信息和观点可以短时间内在社交网络中广泛传播,这为实现大规模的病毒式营销提供了新的机会。影响力最大化(Influence Maximization,IM)问题是社交网络的一个重要研究方向,目的是从社交网络中选择个最具影响力的节点(即种子节点),使得传播达到稳定状态后最终的影响范围最大。传播模型是影响力最大化的基础,然而,目前传统的独立级联模型计算传播概率时过于理想,通常设为定值或者节点入度的倒数,无法很好地区分个体影响力的差异。现有大多数启发式IM算法在每次选择种子后都需要更新所有剩余节点的影响力期望,更新效率低,不适合大规模的社交网络。另外,现有基于部分反馈的自适应影响力最大化需要获取目标节点给定跳数内所有邻居节点的状态信息,在大规模网络中很难实现。针对上述问题,本文开展了如下研究工作:(1)针对传统的独立级联模型概率设置过于理想的问题,本文提出了一种基于三元闭包加权的传播概率计算方法。该方法利用社交网络中的三元闭包结构来衡量节点之间的紧密程度,据此为每条边分配相应的传播概率,从而提出了基于三元闭包的独立级联模型。实验结果表明,本文所提出的模型可以实现至少85%,甚至高达97%的节点间传播概率的区分度,更好地反映个体传播能力的差异,从而使得有影响力的节点更易被识别出。(2)针对大多数启发式影响力最大化算法需要在种子选择过程中更新所有剩余节点的影响力期望,更新效率低的问题,本文提出了基于三元闭包的非自适应影响力最大化算法。该算法通过综合考虑三元闭包加权传播概率和三元闭包加权度值来评估节点的影响力期望。此外,该算法还提出了一种高效的影响力期望更新策略,在种子选择过程中,仅需更新本轮未更新的最大影响力的节点,大大提高了更新效率。本文通过理论分析证明了更新策略的有效性,同时实验结果也表明,所提算法不仅效率高,且其影响范围与具有近似保障的IMM(Influence Maximization based on Martingale)算法相当,在不同的独立级联模型下都表现出良好的稳定性和普适性。(3)针对基于部分反馈的自适应影响力最大化需要获取目标节点给定跳数内所有邻居节点状态信息的问题,本文提出了融合三元闭包与概率推测的自适应影响力最大化算法。该算法基于一般性部分反馈模式,只需获取给定跳数内部分邻居节点的状态信息,根据这些已知信息去合理推测给定跳数内未知邻居节点的状态,有效弥补反馈信息不足的缺陷。另外,该算法还考虑自适应影响力最大化中的残差网络紧密性下降的问题,引入“三元闭包结构来计算表示节点间紧密性的三元闭包加权度值,使得对于逐渐稀疏的残差网络,每一轮都能选出获得更大的影响范围的种子节点。实验结果表明,在一般性部分反馈下,本文所提出的自适应IM算法优于其他自适应IM算法,且随着反馈程度的增加,自适应提升比逐渐接近于全反馈下的自适应IM算法。因而本文所提出的自适应IM算法可以兼顾反馈信息的成本与影响范围的性能。消融实验也证明了本文所述的未知节点状态推测的有效性。本篇论文共计30幅图,15个表,参考文献85篇。