余雷博士的论文“Maximizing Boosted Influence Spread with Edge Addition in Online Social Networks” 被ACM Transactions on Data Science接收。该论文主要研究在线社交网络中影响传播最大化问题。对于这一问题的大量已有相关研究仅考虑结点级的种子挖掘，即在社交网络中选择少量关键用户（即种子）作为产品的初始采纳者，使得在某种影响级联模型下影响传播在网络中达到最大或限制其竞争者的影响传播。然而，在实际的营销应用中，公司在有限的营销预算下往往采用混合的营销策略，除了选择少量关键用户，其还可能通过一些额外的激励或奖赏增加用户间的连接以提高产品的采纳率，最终获取更多的收益。考虑到这一现实需求，论文从边级的角度研究了一种新颖的增量影响传播最大化问题，即在独立级联模型下，找到一个最优的边集并添加到网络中进一步地增加给定种子集的影响传播。该问题是对传统影响传播最大化问题的重要推广和补充，且其深入研究在连接推荐任务、目标广告营销等方面具有广泛的应用价值。

增量影响传播最大化问题在独立级联模型下是NP-hard, 且计算给定种子集的增量影响传播是#P-hard。此外，影响传播函数具有单调性但缺乏重要的子模性。为了解决这些挑战，论文提出了一种受限的影响传播函数，其是单调和子模的。因而，简单的贪心算法能够近似地解决这一NP-hard问题，且能够获得具有理论保证的近似解。然而，当网络的大小以及选择的边的数量较大时，这一算法具有相当低的计算效率。因此，论文进一步提出了一种改进的贪心算法。该算法整合了几种有效的优化策略，其在每一次迭代过程中能够过滤掉大量无效的候选边，极大地提升最优边选择的效率，且不会影响解的质量及近似率。同时提出了扩展的最大影响树模型高效地计算种子集的影响传播。在不同大小和结构特征的真实社交网络上对所提出算法和其他启发式算法在边集质量、运行时间、重要参数影响等指标下进行评估与分析，实验结果表明了提出算法的有效性和高效率性，其能够很好的应用于解决社交网络中基于边级的增量影响传播最大化。