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

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

Influence maximization algorithm based on node coverage and structural hole

Influence maximization is one of the important issues in social network analysis， which aims to identify a small group of seed nodes. When these nodes act as initial spreaders， information can be spread to the remaining nodes as much as possible in the network. The existing heuristic algorithms based on network topology usually only consider one single network centrality， failing to comprehensively combine node characteristics and network topology； thus， their performance is unstable and can be easily affected by the network structure. To solve the above problem， an influence maximization algorithm based on Node Coverage and Structural Hole （NCSH） was proposed. Firstly， the coverages and grid constraint coefficients of all nodes were calculated. Then the seed was selected according to the principle of maximum coverage gain. Secondly， if there were multiple nodes with the same gain， the seed was selected according to the principle of minimum grid constraint coefficient. Finally， the above steps were performed repeatedly until all seeds were selected. The proposed NCSH maintains good performance on six real networks under different numbers of seeds and different spreading probabilities. NCSH achieves 3.8% higher node coverage than to the similar NCA （Node Coverage Algorithm） on average， and 43% lower time consumption than the similar SHDD （maximization algorithm based on Structure Hole and DegreeDiscount）. The experimental results show that the NCSH can effectively solve the problem of influence maximization.