基于改进的度折扣方法研究社交网络影响力最大化问题

An Improved Degree Discount Approach for Influence Maximization in Social Networks

在影响力最大化检测算法中,度折扣算法是一个高效的启发式算法。针对现有度折扣算法中的不足,该文对其计算期望影响力的公式进行修正,提出了一阶改进的度折扣算法,并进一步引入冗余弱化机制确保种子节点分散地分布在网络上,得到了二阶改进的度折扣算法。基于独立级联模型,在4个真实网络上与其他算法进行比较,实验结果表明提出的两种算法使信息扩散速度更快、更广,还能保证较低的时间复杂度。

In the influence maximization detection algorithm,the degree discount algorithm is an efficient heuristic algorithm.Aiming at the shortcomings of the degree discount algorithm,the formula for calculating the expected influence is modified and the first-order improved degree discount algorithm is proposed.Furthermore,in order to ensure the seed nodes are scattered in the network,a redundancy weakening mechanism is introduced and then the second-order improved degree discount algorithm is constructed.Based on the independent cascade model,the proposed algorithms are compared with other algorithms in four real networks.The experimental results confirm that the proposed algorithms can ensure faster and wider information spreading with low time complexity.