社交网络中的种子集合与传播时间最小化研究

发布时间：2020-05-14 20:20

【摘要】：近年来,随着大规模社交网络如Facebook、Twitter、Wechat的迅速发展,社交网络已成为信息传播和影响力扩散的主要平台。相较于传统的报纸、电视等媒体,信息可以在社交网络更快地传播和造成更大的影响力。因此社交网络中的影响力传播问题得到了很多学者的关注。影响力传播问题在很多现实场景中,如市场推广、饥饿营销、舆情预警等,具有重要的现实意义。在影响力传播问题中,我们可以确定三个主要变量:初始种子集合的大小、种子集合的影响覆盖范围以及传播所需的时间。我们可以控制其中两个变量去优化第三个变量。Kempe等人系统研究了在无时间约束下,如何选择一定大小的种子集合,使得影响覆盖范围最大化的问题。在此基础上,本文的研究内容围绕以下两个问题展开:一是传播时间最小化问题,即如何选择大小为k的种子集合,使得影响覆盖范围达到指定阈值的时间最短;二是种子集合最小化问题,即如何选择最小的种子集合,以一定的置信度达到指定的影响覆盖范围阈值。本文的主要工作如下:1.基于MIA模型的传播时间最小化算法。基于MIA模型,利用节点的局部子树结构来表征节点的影响力和估计节点的激活时间,并证明了节点期望激活时间的单调性。在此基础上提出了传播时间最小化算法PTSA,并在真实网络上与其他算法进行了对比分析。实验结果表明PTSA算法具有最短的传播时间。2.基于IC模型的种子集合最小化算法。利用IC模型中节点被激活的概率无关性质,我们将节点影响增益的计算复杂度减少了一个线性因子。借鉴传统的MSA算法框架,我们提出了种子集合最小化算法FMSA。真实网络和人工网络的实验结果表明,FMSA算法的运行速度相较于MSA算法得到了数千倍的提高。3.基于社区结构的种子集合最小化算法。考虑到社交网络往往具有社区结构,利用社区的特点,可以将种子节点的搜索范围从整个网络缩小至局部的社区内部,加快种子节点搜索效率。结合动态规划思想,我们提出了一种基于社区结构的种子集合最小化算法ICGA,并在真实网络和人工网络上进行了对比分析,验证了ICGA算法的可行性和高效性。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP393.09

【相似文献】