报告题目：Host Profit Maximization for Competitive Viral Marketing in Billion-Scale Networks

报告专家：中国人民大学 李德英教授

报告时间：2018年9月8日（周六）10: 00-11: 00

报告地点：数统学院201学术报告厅

报告摘要：该研究考察了如何在竞争性社会网络中最大化网站东家的利润。研究的场景如下：在同一个社会网络中有很多同质性的公司提供类似产品给网络中的顾客。如果一个顾客购买了一个公司的产品，则该公司付给东家一笔佣金。对于同一个顾客，不同公司有可能付给东家不同的佣金。本文中提出了竞争环境下东家利润最大化问题（CPro），寻求一个方案为不同的公司制定不同的种子用户节点进行宣传，使得这些公司付给东家的总佣金最大。我们发现CPro问题是NP难的，同时其目标函数是非次模和非单调的，这意味着现有理论和方法并不能为其提供有效解法。为此，我们提出了一种基于随机方法的近似算法，该方法是同类问题中第一个性能边界被严格证明并能在所有社会网络中使用的近似算法，不仅如此，该算法还是高扩展的。我们使用实际数据对其进行了评测，实验证明，即使对于包含15亿条边的超大社会网络，我们的算法都能在几分钟之内找到有效解。