融合节点覆盖范围和结构洞的影响力最大化算法

影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点(通常称为种子节点)。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法(NCA)平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法(SHDD)减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。

基于节点覆盖范围的影响力最大化算法

为解决传统影响力最大化算法时间复杂度高,选出节点过于集中,导致富人俱乐部现象(rich-club)的问题,提出一种基于节点覆盖范围的影响力最大化算法,将节点覆盖范围作为节点选取的中心性评价指标,有效避免选取种子节点时节点过于集中。为进一步减少运行时间,对该算法进行CELF优化。在各种规模网络上的实验结果表明,该算法能够有效选取最具影响力的节点。