《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (8): 2609-2616.DOI: 10.11772/j.issn.1001-9081.2021071185

• 前沿与综合应用 • 上一篇    

基于反向影响采样的积极影响力最大化

杨书新(), 许景峰   

  1. 江西理工大学 信息工程学院,江西 赣州 341000
  • 收稿日期:2021-07-08 修回日期:2021-09-13 接受日期:2021-09-22 发布日期:2021-09-30 出版日期:2022-08-10
  • 通讯作者: 杨书新
  • 作者简介:杨书新(1978—),男,江西九江人,副教授,博士,CCF会员,主要研究方向:社交网络分析、生物信息学;
    许景峰(1996—),男,江西赣州人,硕士研究生,主要研究方向:社交网络分析、数据挖掘。
  • 基金资助:
    江西省教育厅科学技术研究项目(GJJ170518)

Positive influence maximization based on reverse influence sampling

Shuxin YANG(), Jingfeng XU   

  1. School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China
  • Received:2021-07-08 Revised:2021-09-13 Accepted:2021-09-22 Online:2021-09-30 Published:2022-08-10
  • Contact: Shuxin YANG
  • About author:YANG Shuxin, born in 1978, Ph. D., associate professor. His research interests include social network analysis, bioinformatics.
    XU Jingfeng, born in 1996, M. S. candidate. His research interests include social network analysis, data mining.
  • Supported by:
    Scientific and Technology Research Project of Education Department of Jiangxi Province(GJJ170518)

摘要:

影响力最大化问题现有的工作主要集中在无符号网络上,忽略了网络中个体之间存在的敌对关系。针对符号网络中的积极影响力最大化问题,在极性相关的独立级联(IC-P)模型的基础上提出一种符号网络中基于反向影响采样(RIS-S)的算法以最大化积极影响力。首先,在生成反向可达集的阶段考虑了节点的极性关系,以适用于符号网络;其次,为了提高反向可达集的有效性,限制了采样的遍历深度。在三个真实的符号网络数据集上比较了RIS-S、IMM(Influence Maximization via Martingales)、POD(Positive Out-Degree)和Effective Degree等算法的积极影响力范围和运行时间,以验证所提算法的有效性。实验结果表明,RIS-S算法所选的种子更加准确,能获得更广的积极影响力范围,并且该算法的运行时间比同类型算法IMM更短,可以认为RIS-S算法能够解决符号网络中的积极影响力最大化问题。

关键词: 影响力最大化, 符号网络, 独立级联模型, 反向影响采样算法, 病毒式营销

Abstract:

Existing works on influence maximization mainly focus on unsigned network and neglect the hostile relationship between the individuals in the network. Aiming at the positive influence maximization problem in signed network, based on Polarity-related Independent Cascade (IC-P) model, a Reverse Influence Sampling in Signed network (RIS-S) algorithm was proposed to maximize positive influence. Firstly, in order to apply to the signed network, the polarity relationships of nodes in the stage of generating reverse reachable sets were considered. Secondly, to improve the effectiveness of reverse reachable sets, the traversal depth of sampling was limited. Finally, the positive influence ranges and running times of RIS-S, Influence Maximization via Martingales (IMM), Positive Out-Degree (POD) and Effective Degree algorithm were compared on three real signed network data sets to verify the effectiveness of the proposed algorithm. Experimental results show that RIS-S algorithm can obtain wider positive influence range by selecting more accurate seeds, and the proposed algorithm has the running time less than the same type algorithm IMM.It can be thought that RIS-S algorithm can solve the problem of positive influence maximization in signed network.

Key words: influence maximization, signed network, independent cascade model, Reverse Influence Sampling (RIS) algorithm, viral marketing

中图分类号: