摘要

针对影响最大化算法存在选取的种子节点影响力重叠、时间复杂度高等问题,提出了基于覆盖阈值的度最大启发式算法(CTMD)。该算法主要思想是利用改进的k-shell算法计算节点影响力以选取初始种子节点;计算两度以内节点的激活概率,基于覆盖阈值θ,把易激活的节点标记为覆盖状态,更新节点的影响力值,直到选取到指定数量的种子节点;通过实验对核覆盖算法(CCA)、度最大(Max Degree)、影响力排名影响力估计(IRIE)和CTMD算法进行了比较与分析。实验结果表明,在独立级联(IC)模型和加权级联(WC)模型中,CTMD算法的影响范围具有明显的优势。此外,通过对运行时间进行测试可知,随着网络规模的逐步增大,CTMD算法具有较低的时间复杂度。