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

Influence Maximization Algorithm Based on Reverse Reachable Set

现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法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.