Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (12): 3419-3424.DOI: 10.11772/j.issn.1001-9081.2018040920

Previous Articles     Next Articles

Influence maximization algorithm based on structure hole and degree discount

LI Minjia, XU Guoyan, ZHU Shuai, ZHANG Wangjuan   

  1. College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China
  • Received:2018-05-04 Revised:2018-07-02 Online:2018-12-10 Published:2018-12-15
  • Contact: 李敏佳
  • Supported by:
    This work is partially supported by the Science and Technology Research Project of Water Resources Department of Jiangsu Province (2017065, 2016023).


李敏佳, 许国艳, 朱帅, 张网娟   

  1. 河海大学 计算机与信息学院, 南京 211100
  • 通讯作者: 李敏佳
  • 作者简介:李敏佳(1994-),女,河南周口人,硕士研究生,主要研究方向:社交网络、数据管理;许国艳(1971-),女,内蒙古赤峰人,副教授,博士,CCF会员,主要研究方向:大数据、数据起源、数据管理;朱帅(1992-),男,江苏扬州人,硕士研究生,主要研究方向:社会网络、数据管理;张网娟(1992-),女,江苏盐城人,硕士研究生,主要研究方向:大数据、数据管理。
  • 基金资助:

Abstract: The existing Influence Maximization (IM) algorithms of social network have the problem of low influence range caused by only selecting local optimal nodes at present. In order to solve the problem, considering the propagation advantage of core node and structure hole node, a maximization algorithm based on Structure Hole and Degree Discount (SHDD) was proposd. Firstly, the ideas of structure hole and centrality degree were integrated and applied to the influence maximization problem, and the factor α combining the structure hole node and the core node was found out to play the maximum propagation function, which made the information spread more widely to increase the influence of the whole network. Then, in order to highlight the advantages of the integration of two ideas, the influence of second-degree neighbor was added to the evaluation criteria of structure hole to select the structure hole node. The experimental results on data sets of different scales show that, compared with DegreeDiscount algorithm, SHDD can increase the influence range without consuming too much time, and compared with the Structure-based Greedy (SG) algorithm, SHDD can expand the influence range and reduce the time cost in the network with large clustering coefficient. The proposed SHDD algorithm can maximize the advantages of structure hole node and core node fusion when factor α is 0.6, and it can expand the influence range more steadily in the social network with large clustering coefficient.

Key words: social network, Influence Maximization (IM), Independent Cascade model (IC), structure hole, degree discount

摘要: 在社会网络影响力最大化(IM)算法中,针对目前仅选取局部最优节点造成的影响范围较小的问题,综合考虑核心节点和结构洞节点的传播优势,提出了一种基于结构洞和度折扣的最大化算法(SHDD)。首先,该算法将结构洞思想和中心度思想互相融合应用到影响力最大化问题中,并找出能将结构洞节点和核心节点综合发挥最大传播作用的α因子,使得信息更大范围地扩散从而扩大整个网络的影响范围。其次,为突出两个思想融合的优势,将二度邻居的影响添加到结构洞评价标准中来选取结构洞节点。在不同规模的数据集上实验结果表明,与DegreeDiscount算法相比,SHDD在没有增加过多时间开销的同时扩大了影响范围;与基于结构的贪心(SG)算法相比,在聚类系数较大的网络中SHDD扩大了影响范围并降低了时间开销。SHDD在α因子取0.6时能最大限度地发挥结构洞节点和核心节点融合的作用并且在聚类系数较大的社交网络中能更加稳定地扩大影响范围。

关键词: 社交网络, 影响力最大化, 独立级联模型, 结构洞, 度折扣

CLC Number: