社交网络影响力最大化问题的增量式算法研究

发布时间：2022-02-04 23:09

　　近年来,众多迅速兴起的在线社交网络平台成为了人们传播信息、影响他人的重要方式;影响力最大化（Influence Maximization,IM）问题是社交网络信息传播分析中的重要问题,在口碑营销、舆情控制、网络监控等众多应用中其中关键作用;该问题及其衍生问题包括主题影响力最大化、关联影响力最大化（Correlated Influence Maximization,CIM）问题等,也因此受到了广泛研究。IM问题旨在找出网络中最具影响力的k个用户,以某种传播模型从选出的用户发出信息传播,使得最终受影响用户的总数最大。传统影响力最大化算法大多数仅关注静态社交网络,然而社交网络拓扑结构天然具有动态特征,传统算法不适用。本文研究动态网络中最大化问题,提出了基于跳步的影响力最大化增量式算法。论文主要研究内容如下:（1）独立级联模型下IM问题的增量式算法为解决动态网络中最具影响力种子集更新问题,基于跳步策略,提出了一种针对独立级联传播模型的影响力最大化增量式算法。该算法利用局部化传播的特点,快速评估网络变化所涉及节点的影响力增益上限,与先前输出结果比较,快速更新有可能需要变动的影响力节点。在大规模真... 

【文章来源】：西北农林科技大学陕西省211工程院校985工程院校教育部直属院校

【文章页数】：69 页

【学位级别】：硕士

【部分图文】：

研究路线图

社交网络的研究分析基本上是基于图论展开的。以有向图为例,如图2-1所示。通常,社交网络可建模为有向图G=(V,E),其中顶点集V表示网络中的所有用户,边集E表示用户u与v之间联系。在社交网络的影响力最大化问题中,为了更好的描述影响力扩散,本文研究均选择构建有向图。图中,每条边e=(u,v)∈E存在着一个概率值pu,v∈[0,1],用来表示影响力扩散过程中用户u对v的激活概率。对于有向边(u,v),称节点v为u的邻居,则Nu={v|(u,v)∈E}为节点u的邻居集;称节点u为v的逆邻居,则Rv={v|(u,v)∈E}为节点v的逆邻居集。

对于大规模网络图,本章实验在Wiki-vote、soc-Epinions1、soc-delicious三个数据集上进行,以影响扩散范围和运行时间为衡量标准,种子集合的大小k分别取1,10,100,1000。根据不同对比需求,设置不同传播概率。图3-1中的(a)-(c)表明了,在一跳步范围内,OneIC-HopInc算法与OneHop算法、IncInf算法运行时间的对比情况,图(d)是影响扩散范围的对比情况,概率模型采取UNI模型。图3-2中的(a)-(c)表明了,在二跳步范围内,TwoC-HopInc算法与TwoHop算法、IncInf算法运行时间的对比情况,图(d)是影响扩散范围的对比情况,概率模型采取TRI模型。

【参考文献】：
期刊论文
[1]基于线性阈值模型的动态社交网络影响最大化算法[J]. 朱敬华,李亚琼,王亚珂,杨艳.  工程科学与技术. 2019(01)
[2]基于结构洞和度折扣的影响力最大化算法[J]. 李敏佳,许国艳,朱帅,张网娟.  计算机应用. 2018(12)
[3]竞争环境中基于主题偏好的利己信息影响力最大化算法[J]. 曹玖新,闵绘宇,王浩然,马卓,刘波.  计算机学报. 2019(07)
[4]关联影响力传播最大化方法[J]. 张云飞,李劲,岳昆,罗之皓,刘惟一.  计算机科学与探索. 2018(12)
[5]基于k-核过滤的社交网络影响最大化算法[J]. 李阅志,祝园园,钟鸣.  计算机应用. 2018(02)
[6]基于用户聚类的社交网络影响力最大化传播模型[J]. 曾燕清,陈志德,李翔宇.  软件. 2017(05)
[7]社会网络节点影响力分析研究[J]. 韩忠明,陈炎,刘雯,原碧鸿,李梦琪,段大高.  软件学报. 2017(01)
[8]基于LT+模型的社交网络影响力最大化研究[J]. 蔡国永,裴广战.  计算机科学. 2016(09)
[9]社会网络中基于主题的影响力最大化算法[J]. 朱玉婷,李雷,施化吉,周从华,施磊磊,徐慧.  计算机应用研究. 2016(12)
[10]多社交网络的影响力最大化分析[J]. 李国良,楚娅萍,冯建华,徐尧强.  计算机学报. 2016(04)

硕士论文
[1]动态复杂网络中的影响最大化算法的研究[D]. 王亚珂.黑龙江大学 2017
[2]社交网络影响力最大化的研究[D]. 王欢欢.南京航空航天大学 2016



本文编号：3614114