基于相似性和反向随机游走的影响力最大化算法研究

发布时间：2021-03-09 03:04

　　随着信息技术的飞速发展,各种社交平台不断涌现,人与人之间的交互形成规模庞大,结构复杂的社交网络。分析网络结构,研究网络的信息传播机制,对于舆论控制、病毒式营销、传染病控制等都具有重要的理论意义和实用价值,其中影响力最大化就是一个重要的研究方向。影响力最大化问题就是在一个网络中寻找部分种子节点作为信息传播源,使得这些种子节点组合在一起的影响力传播范围最大,即信息在网络中的传播范围最广。最近十几年,针对该问题,虽然已经有很多的研究工作发表,但是当前的算法在处理大规模网络时依然难以同时满足精确性、时间效率和空间效率的要求。本文将从以下几个方面来研究精确、有效的影响力最大化算法:首先,基于一阶邻居提出相似性框架,用来解决种子节点之间的影响力覆盖问题。通过将提出的相似性框架应用到两个现有的算法,度剪枝和基于传播路径的PMD算法,证明所提出来的相似性框架能够有效提高启发式算法的精度。其次,提出两阶段的框架来提高现有贪心算法的时间效率。该框架首先利用提出的改进度剪枝算法选出候选种子节点,缩小种子节点的选择范围,然后利用现有的贪心算法从候选节点中选出种子节点。然后,提出反向随机游走的策略来评估节点的重... 

【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

一个无向无权网络

图 3-3 不同相似性阈值下影响力的传播范围图 3-3 展示了 SDD(SSD)和 SPMD 算法在不同相似性阈值下的影响力传播范围。横坐标表示相似性阈值，变化范围从 0.1 到 1.0，纵坐标表示选择 50 个种子节点的影响力传播范围。从图 3-3 的六个图中可以看出，在大多数情况下当 的值从 0.1 到 0.9 变化，无论是在独立级联模型还是在权重级联模型，影响力的传播范围都是逐渐增加，这表明当 取 0.9 的时候 SDD(SSD)和 SPMD 能取得最优的传播范围。3.4.2 不同算法的影响力传播范围对比图 3-4 展示了不同算法在独立级联模型，传播概率为 0.01 的情况下在 12 个真实数据集上选出 50 个种子节点的影响力传播范围。横轴表示种子节点的个数从 1 到 50，纵轴表示影响力传播范围，即最终激活的节点数量。为了对比公平，影响力传播范围都是通过 10000 次的蒙特卡洛模拟计算的，下文所有涉及影响力传播范围的不同百分比都是在 = 50情况下计算的。

30图 3-4 各种算法在 12 个真实数据集上的影响力传播范围（IC 模型， = 0 01）不同算法在 12 个真实网络上，在权重级联模型下的影响力传播范围如图 3-5 所示。同样横轴表示节点个数，纵轴表示传播范围，可以看出 SDDCELF 算法在 10 个网络上和 CELF 取得几乎一样的精度。基于相似性改进的算法 SPMD 选出的节点的传播范围总是比 PMD 高，例如在 astro-ph、ca-AstroPh、email-EuAll、facebook、soc-Epinions、Wiki-vote 上分别高出 28.6%、35.6%、64%、36.3%、53.3%、22%。提出的 SSD 算法总是比 SD 在精确度上高或者相同，例如在 astro-ph、com-


本文编号：3072137