基于联盟划分的社会网络影响力最大化问题研究

发布时间：2020-11-20 15:55

　　 随着移动互联网技术的高速发展,在线社会网络平台的出现正改变着人们的生活方式,人们在社会网络平台进行信息发布和交流互动,而社会网络平台强大的信息传播功能使其成为广告发布、企业营销的重要渠道。移动互联网时代,社会网络上的影响力最大化问题研究对于广告发布、市场营销等方面都具有重要意义。影响力最大化问题是指从社会网络中选取少量种子用户,通过这些种子用户的信息传播来使整个网络中尽可能多的用户受到影响。从计算复杂性角度来说,影响力最大化问题是一个NP难题。许多研究者以节点和边的关系提出启发式方法去解决影响力最大化问题,但一个网络不仅仅是节点与节点关系组成的结构,更有个体根据自身利益所采取的不同策略的结构。因此,本文将理性选择的节点加入到使得该节点利益最大的联盟,引入合作博弈论的思想,首次提出利用联盟划分的启发式方法,并设计Shapley value方法来判定联盟结构、合理分配利益,从而提出了一种基于Shapley value的影响力最大化算法。该算法可以缩短寻找种子节点的范围,从而减少解决影响力最大化问题的时间。由于Shapley value在联盟形成的过程中,只考虑参与者(节点)自己的利益,忽略了该参与者加入联盟时对其他参与者的影响(外部性),进一步影响联盟划分的结果。而Consensus value判断新参与者是否加入到联盟中,除了需要考虑新的参与者对该联盟的贡献,还需要考虑新参与者加入后对同一联盟里其他参与者的影响。只有满足新参与者加入联盟后自身的收益和其他参与者的收益都增大,新参与者才允许加入到联盟中。因此,本文充分考虑了联盟的外部性,提出了一个基于Consensus value的方法,从而弥补Shapley value在联盟划分时的不足。基于Consensus value的影响力最大化方法使得联盟划分的结果更加合理,最终使得选取的种子节点能够影响更多的用户。本文把基于联盟划分的影响力最大化方法分为三个阶段:首先,计算网络上的分组,该计算过程模拟了一个合作博弈,根据两种解概念Shapley value和Consensus value,来分别计算参与者之间达成联盟的过程。其次,通过计算每个联盟的整体收益来选择最有影响力的联盟。最后,通过搜索每个联盟中最有影响力的参与者来确定种子集合,并获得影响力最大化问题的解决方案。基于联盟划分的影响力最大化方法的优势在于它建立了社会网络和联盟之间的桥梁,不仅计算具有影响力的节点,而且计算具有影响力的联盟。本文的工作主要包括以下三个方面:(1)提出基于Shapley value的影响力最大化方法为了提高解决影响力最大化问题的时间效率,本文首次提出将合作博弈思想引入到社会网络中,并设计一种基于Shapley value的影响力最大化算法。该方法首先从社会网络的角度对传统的Shapley value公式做了相应的改进,利用改进后的Shapley value公式将社会网络进行联盟的划分;其次,提出基于每个联盟的收益比例的方法来选择候选联盟。最后,使用MaxDegree算法查找候选联盟中的种子节点集。该算法的目的是在不同的联盟里寻找种子节点集,以避免信息重叠对社会网络中传播扩散范围造成一定的影响。(2)提出基于Consensus value的影响力最大化方法在Shapley value联盟形成的过程中忽略考虑该参与者加入到某个联盟中时对其他参与者的影响,这将影响了联盟划分的结果,最终导致影响力的传播值不准确。Consensus value充分考虑联盟的外部性,因此本文提出一种基于Consensus value的影响力最大化方法。该方法首先将经济学里的Consensus value进行归纳整理,推导出简单易理解的Consensus value公式。再依据该公式进行联盟的划分—选择候选联盟—寻找种子节点集。(3)实验验证本文从影响力传播值和运行时间两个方面对实验结果进行分析,并将基于联盟划分的影响力最大化方法、基于非联盟划分的方法和传统经典的算法进行对比。通过实验分别模拟ER随机模型、无标度网络模型、小世界网络模型等不同复杂网络模型和现实网络数据集,验证了基于联盟划分的Shapley value和Consensus value方法的可行性。从传播效果方面的试验表明:基于联盟划分的影响力最大化方法的影响力传播值优于其他启发式算法;Consensus value方法比Shapley value方法的传播效果更好;Consensus value方法的影响力更接近于贪心算法。随后本文从时间运行的方面进行实验分析,实验表明:基于联盟划分的影响力最大化方法比贪心算法更快。
【学位单位】：西南大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP18;O225
【部分图文】：

第 1 章 绪论第1章 绪 论会网络影响力最大化问题的研究背景及国内外研主要研究内容和论文组织结构。网络的概念最早由 Simmel 提出，他把社会想象为事物之间各种关系的集合，其中关系的互动会影社会网络的定义是 Wellman 于 1988 年提出的“社系构成的相对稳定的系统”，即把“网络”视为，它们相对稳定的模式构成社会结构[2]。利用个体间切联系的人们或组织联合在一起。其中社会关系图 1-1 显示了社会网络中用户之间的关系。

第 1 章 绪论范围比基于 Shapley value 的影响力最大化方法更广。与传统的影响力最大化方法相比，基于 Consensus value 的影响力最大化方法能够产生更好的传播效果，同时缩短了运行时间。本文提出基于联盟划分的影响力最大化方法建立了社会网络和联盟之间的桥梁，不仅计算具有影响力的节点，而且计算具有影响力的联盟。该方法的主要优点可以概括为如下两点：（1）无需提前设定网络的规模和社区的数量，基于节点的偏好理性选择加入到某联盟中，自动生成稳定的联盟结构。（2）将合作博弈论与影响力最大化问题相结合，提出基于联盟划分的影响力最大化方法。该方法主要是将整个网络划分为不同的联盟，在候选的联盟里选择种子节点集。这将缩小选择种子节点集的范围，进一步提高运算速度。图 1-2 显示了基于联盟划分的影响力最大化方法的框架。

第 2 章 相关理论中，并且引入了长距离连接（或捷径）。在小世界网络模型中，当概率p=0时，成的网络为环形栅格网络；当p=1时，则会形成一个随机图；当0<p<1时，随着 的增加，网络由稀疏的规则网络演变为小世界网络，最后形成一个稠密的规则网[47]。网络的演化过程如图 2-1 所示。
【参考文献】

相关博士学位论文 前1条

1 马茜;社会网络中的节点影响力度量和k-节点集的影响力最大化问题研究[D];山东大学;2017年

相关硕士学位论文 前3条

1 沈成光;影响力最大化问题的算法和传播模型研究[D];大连理工大学;2016年

2 颜庆;社会网络中影响力最大化问题的算法设计与分析[D];山东大学;2015年

3 陈思源;合作博弈Shapley值的扩展与应用[D];西安电子科技大学;2011年

本文编号：2891650