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

作者：杨杰; 张名扬; 芮晓彬; 王志晓

来源：计算机应用, 2021, 1-8.

• 社交网络
• 影响力最大化
• 节点覆盖范围
• 结构洞
• 启发式算法

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

• 单位
  中国矿业大学; 中国矿业大学（北京）