Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (4): 1155-1161.DOI: 10.11772/j.issn.1001-9081.2021071256

• The 36 CCF National Conference of Computer Applications (CCF NCCA 2020) • Previous Articles    

Influence maximization algorithm based on node coverage and structural hole

Jie YANG, Mingyang ZHANG, Xiaobin RUI(), Zhixiao WANG   

  1. School of Computer Science and Technology,China University of Mining and Technology,Xuzhou Jiangsu 221116,China
  • Received:2021-07-16 Revised:2021-08-19 Accepted:2021-08-24 Online:2021-08-19 Published:2022-04-10
  • Contact: Xiaobin RUI
  • About author:YANG Jie, born in 1997, M. S. candidate. Her research interests include social network analysis, influence maximization.
    ZHANG Mingyang, born in 1996, M. S. His research interests include social network analysis, influence computing.
    WANG Zhixiao, born in 1979, Ph.D., professor. His research interests include social network analysis, social computing, graph theory, graph data mining.
  • Supported by:
    National Natural Science Foundation of China(61876186)


杨杰, 张名扬, 芮晓彬(), 王志晓   

  1. 中国矿业大学 计算机科学与技术学院,江苏 徐州 221116
  • 通讯作者: 芮晓彬
  • 作者简介:杨杰(1997—),女,山东烟台人,硕士研究生,CCF会员,主要研究方向:社交网络分析、影响力最大化
  • 基金资助:


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.

Key words: social network, influence maximization, node coverage, structural hole, heuristic algorithm



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

CLC Number: