多社交网络的影响力最大化分析

影响力最大化旨在从网络中识别k个节点,使得通过这k个节点产生的影响传播范围最大.该问题在病毒营销领域具有重要的应用背景,它已经引起了学术界和工业界的广泛研究.该文作者观察到已有的研究工作大多数只是针对单一网络,即在给定的一个网络上识别k个节点使得其在该网络上产生最大的影响范围;然而,随着社交网络的普及,丰富多样的社交平台不断涌现,以满足不同的社交需求,这使得社交人群不被局限在一个网络内,而是分布在不同的社交网络上.这种变化的一个直接影响是使得基于病毒式营销的应用,例如单一网络上的产品推广愈加不能满足推广的广度需求,很可能是单一网络上的用户量不能达到推广的目标人群数量,又或者广告商期望在多个网络平台上找到k个用户以最大化影响传播范围.为此,在文中,作者研究多社交网络上的影响力最大化问题.该文首先仔细地研究了影响力最大化问题在单一网络和多社交网络上的不同,并提出了实体的自传播特性以在多个网络之间建立联系.之后,作者提出了多社交网络上的影响计算模型来建模节点间的影响力,然后扩展了基于树的算法模型以适应多社交网络上的影响力最大化问题.基于所提出的影响计算模型和扩展的基于树的算法模型,作者提出了多种策略的优化算法.例如通过深层次挖掘自模特性来避免冗余计算,通过使用影响增益上界近似准确的增益来加速种子选取过程等,最后通过真实数据集上的实验表明文中所提方法在性能和影响范围上都优于已有的算法.