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

• 作 者: 袁金亮
• 出 处: 兰州大学
• 发表日期: 2019年01期
• 关键词: 影响力最大化 相似性 贪心算法 反向随机游走

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