基于覆盖阈值的影响最大化算法的研究

摘要：

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

关键词：社交网络、节点影响力、影响最大化、覆盖阈值、k-shell

所属期刊栏目：29

资助基金：国家自然科学基金61602401, 61472340;河北省高等学校科学技术研究QN2018074

在线出版日期：2019-06-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：438-448