基于反向可达集的影响力最大化算法  

Influence Maximization Algorithm Based on Reverse Reachable Set

作　　者：邓心惠 宾晟 孙更新 DENG Xinhui;BIN Sheng;SUN Gengxin(College of Data Science and Software Engineering,Qingdao University,Qingdao,Shandong 266071,China)

机构地区：[1]青岛大学数据科学与软件工程学院,山东青岛266071

出　　处：《计算机工程》2022年第1期60-68,74,共10页Computer Engineering

基　　金：山东省自然科学基金面上项目(ZR2017MG011);教育部人文社会科学研究青年项目(15YJC860001);山东省社会科学规划项目(17CHLJ16)。

摘　　要：现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。Most of the existing influence maximization algorithms are not suitable for large-scale social networks due to their high time complexity or limited influence propagation range.Therefore,an improved influence maximization algorithm named D-RIS is proposed based on the Independed Cascade(IC)model and Reverse Reachable(RR)set sampling.Under the premise that the influence propagation function satisfies monotonicity and sub-modularity,the D-RIS algorithm uses the automatic debugging method to determine the threshold of the number of RR sets.Experimental results on Slashdot and Epinions show that the proposed D-RIS algorithm provides a propagation range that is close to the CELF algorithm and higher than the RIS algorithm,HighDegree algorithm,LIR algorithm and pBmH algorithm.At the same time,compared with the CELF algorithm,the running time is reduced by nearly 100 times,providing higher generalization performance,stability,and applicability to topology changes and large-scale social networks.

关 键 词：社交网络 影响力最大化 信息传播模型 反向可达集 子模性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]