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

夏 欣，马 闯，张海峰*

(1.安徽大学数学科学学院 合肥230601；2.安徽大学互联网学院 合肥 230601)

在线社交平台如Twitter、Weibo、WeChat、Facebook等已经成为人们生活中不可或缺的重要工具，引起了不同领域的学者对社交网络的广泛关注与研究，如社交网络上的影响力最大化问题、链路预测、社团发现及推荐系统等[1-4]。其中影响力最大化问题因其普遍的应用场景而被广泛研究，如在广告投放和市场营销中如何用有限的成本选择具有较大传播力度的人物、地点投放广告，使得了解并且购买该产品的用户最多，从而获取最大收益。在疾病和谣言的传播链中，控制网络中影响力大的节点可以避免其大规模快速传播[5-6]。

影响力最大化问题是指在一个网络中选择一定数目的节点作为种子集，通过激活这些种子节点，使得信息在网络中传播，最终希望网络中被激活的节点数最多。影响力最大化算法主要分为3类：贪婪算法、中心性指标和启发式算法。

在贪婪算法中，文献[7]将影响力最大化问题定义为一个离散的优化问题，证明了在独立级联模型和线性阈值模型下该问题是一个NP-Hard问题。并进一步提出了近似比为(1−1/e)的爬山贪心算法，在每一步迭代中都选择当前边际传播范围最广的节点加入种子集。文献[8]利用子模性提出了CELF(cost-effective lazy forward)算法，该算法大大减少了计算时间。文献[9]提出了改进的CELF++算法，减少了不必要的计算次数。文献[10]提出NewGreedy算法，以传播概率保留网络中的边，根据子图的连通性考虑节点加入种子集的增益。……