论文部分内容阅读
随着微博、Facebook等社交网络媒体的普及,社交网络发展为一个平台,在这个平台上人们通过关注、传递信息、分享内容等行为来相互联系,相互影响。社交网络中,同一个群体内的用户具有相似的特征,这些特征可能是结构上的紧密度,也可能是属性上的相似性。用户之间影响力的传播是社交网络分析的另一项重要研究内容。为了解决影响力最大化问题,研究者提出了原始的贪心算法并证明了这一问题是一个NP-hard问题。但是这一算法复杂度太高,需要大量的蒙特卡罗模拟。为了提高算法效率,研究者又提出了基于社区的影响力最大化算法。但是已有的基于社区的影响力最大化在划分社区时仅仅考虑了节点的连接的紧密度,没有考虑节点的传播特性,使得最后在计算影响力传播范围时不能很好的近似,仍需要蒙特卡罗模拟。因此,为了改进基于社区的影响力最大化算法的精度和效率,本文提出基于影响力相似的群体的影响力最大化,利用群体结构计算影响力传播范围。这一类算法首先定义一个能够衡量两个邻节点影响力相似性的度量,然后用聚类的方法划分群体,得到群体结构之后利用群体内节点具有相似影响力的特征近似估计影响力传播范围,找到最具影响力的种子节点。本文的主要工作包括以下几点:1.基于群体的影响力最大化第一步就是将网络划分为不同的群体。区别于社区只考虑了节点连接的紧密度,群体更多的是考虑节点之间属性的相似度。本文基于节点影响力传播性质的相似性划分群体。首先对邻域矢量传播算法进行改进,提出了基于影响力局部相似的群体划分方法来得到具有相似影响力的群体。2.本文用影响力最大化问题来验证两种群体发现算法的效果,结果证明基于影响力局部相似性的群体发现算法具有较低时间效率,因此采用基于影响力全局相似性的群体划分方法来划分群体。在划分好群体结构的基础上采用两阶段传播模型建模影响力的传播过程,选出影响力传播范围最广的种子节点。3.本文将基于社区的影响力最大化算法、贪心算法和和两个启发式影响力最大化算法与本文提出的算法进行对比,在人工数据集和5个真实数据集上分别验证算法的可扩展性和精度。实验证明,本文提出的算法有着更高的精度和很好的扩展性。