Abstract: Influence maximization is a problem of obtaining a subset of nodes in social network to maximize the influence spread. Aiming at the problem of the poor accuracy of heuristic algorithm, existing works consider the overlapped range, and ignore the problem of edge contributions. This paper focuses on how to select a seed set that has the maximum influence based on edge contributions. The algorithm evaluates the influence of information spread by calculating the global influence and adjacent influence. Then it removes the selected node influence range and updates the network to eliminate the interference of edge contributions to node influence evaluation. Finally, this paper proposes an edge-cover algorithm for influence maximization based on independent cascade model. The experimental results show that the proposed algorithm has a greater impact on the spread of range.

Key words:  social network, influence maximization, edge contributions, heuristic algorithm

摘要： 影响力最大化问题是在社交网络中寻找具有最大影响范围的节点集。针对启发式算法准确度相对较差的问题，现有的研究考虑了影响范围重合，但忽略了边缘贡献导致的节点影响力过量评估。重点研究了在考虑边缘贡献的情况下，如何选取影响范围最大的节点集合。采用启发式算法的思想，首先计算节点全局和邻近影响力来评估节点信息传播影响力，通过去除已选节点影响范围并更新网络的方式，消除边缘贡献对节点影响力评估的干扰，在独立级联模型基础上提出了基于边缘去重的节点影响力最大化算法。仿真结果表明所提出算法相比其他算法，能够有效增大节点信息传播影响范围。

关键词: 社交网络, 影响力最大化, 边缘贡献, 启发式算法