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

Positive influence maximization based on reverse influence sampling

作　　者：杨书新[1] 许景峰 YANG Shuxin;XU Jingfeng(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

机构地区：[1]江西理工大学信息工程学院,江西赣州341000

出　　处：《计算机应用》2022年第8期2609-2616,共8页journal of Computer Applications

基　　金：江西省教育厅科学技术研究项目(GJJ170518)。

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

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

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]