随着移动互联网技术的高速发展,在线社会网络平台的出现正改变着人们的生活方式,人们在社会网络平台进行信息发布和交流互动,而社会网络平台强大的信息传播功能使其成为广告发布、企业营销的重要渠道。移动互联网时代,社会网络上的影响力最大化问题研究对于广告发布、市场营销等方面都具有重要意义。影响力最大化问题是指从社会网络中选取少量种子用户,通过这些种子用户的信息传播来使整个网络中尽可能多的用户受到影响。从计算复杂性角度来说,影响力最大化问题是一个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方法的影响力更接近于贪心算法。随后本文从时间运行的方面进行实验分析,实验表明:基于联盟划分的影响力最大化方法比贪心算法更快。