Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 1944-1949.DOI: 10.11772/j.issn.1001-9081.2019091695

• Data science and technology • Previous Articles     Next Articles

Reverse influence maximization algorithm in social networks

YANG Shuxin, LIANG Wen, ZHU Kaili   

  1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou Jiangxi 341000, China
  • Received:2019-10-09 Revised:2019-12-11 Online:2020-07-10 Published:2019-12-18
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61662028), the Science and Technology Research Project of Education Department of Jiangxi Province (GJJ170518), the Special Foundation of Postgraduate Innovation of Jiangxi Province (YC2018-S331).

社交网络中对立影响最大化算法

杨书新, 梁文, 朱凯丽   

  1. 江西理工大学 信息工程学院, 江西 赣州 341000
  • 通讯作者: 杨书新
  • 作者简介:杨书新(1978-),男,江西九江人,副教授,博士,CCF会员,主要研究方向:社会网络分析、生物信息学;梁文(1994-),男,吉林梅河口人,硕士研究生,CCF会员,主要研究方向:社会网络分析、复杂网络;朱凯丽(1994-),女,河南商丘人,硕士研究生,主要研究方向:差分隐私、推荐系统。
  • 基金资助:
    国家自然科学基金资助项目(61662028);江西省教育厅科学技术研究项目(GJJ170518);江西省研究生创新专项资金资助项目(YC2018-S331)。

Abstract: Existing research works on the influence of social networks mainly focus on the propagation of single-source information, and rarely consider the reverse form of propagation. Aiming at the problem of reverse influence maximization, the heat diffusion model was extended to the multi-source heat diffusion model, and a Pre-Selected Greedy Approximation (PSGA) algorithm was designed. In order to verify the validity of the algorithm, seven representative seed mining methods were selected, and the experiments were carried out on different kinds of social network datasets with the propagation revenue of reverse influence maximization, the running time of the algorithm and the degree of seed enrichment degree as evaluation indexes. The results show that the seeds selected by PSGA algorithm have stronger propagation ability, low intensity, and high stability performance, and have advantage in the early stage of propagation. It can be thought that PSGA algorithm can solve the problem of reverse influence maximization.

Key words: reverse influence maximization, social network, multi-source heat diffusion model, tie-breaking rule, rich-club

摘要: 已有社交网络影响力传播的研究工作主要关注单源信息传播情形,较少考虑对立的传播形式。针对对立影响最大化问题,扩展热量传播模型为多源热量传播模型,并提出一种预选式贪心近似(PSGA)算法。为验证算法有效性,选取7种具有代表性的种子挖掘方法,以对立影响最大化传播收益、算法运行时间及种子的富集程度为评价指标,在不同种类社会网络数据集上开展实验。结果表明,PSGA算法所选的种子传播能力更强,且密集程度低、表现稳定,在传播初期占据优势,可以认为PSGA算法能够解决对立影响最大化问题。

关键词: 对立影响最大化, 社交网络, 多源热量传播模型, 打破平局规则, 种子富集性

CLC Number: