2019年6月5日，密歇根大学的博士生陶表帅访问北京大学前沿计算研究中心，并在静园五院做了题为“Influence Maximization on Undirected Graphs”的学术报告。报告由中心助理教授孔雨晴博士主持，听众主要为信息学院和数学学院学生。

陶表帅报告中

　　背景介绍

　　在社交网络中，信息会以让人想象不到的速度很快传开：电子病毒会通过自动向好友分享链接达到飞速的传播；营销商可以通过找明星等有影响力的人代言，使得很快有很多的人知道一个产品；一些网络用语，也是通过社交网络的飞速传播，变成流行用语并被大家使用。这使得社交网络中影响力最大化问题变得十分重要，这一问题有重要的理论价值和实际价值。

　　在简要介绍了问题的背景和意义之后，陶表帅博士开始正式定义影响力最大化问题：在一个图G=(V,E)中，给定传播模型σ:2^V→R，以及整数k，影响力最大化问题需要找一个集合S⊆V ,|S|≤k，使得集合S的影响力σ(S)尽可能大。这一问题的开创性工作来自Kempe，Kleinberg和Tardos，他们在2003年提出了这一社交网络中影响力最大化问题的基本框架，并提出了独立传播模型（Independent Cascade Model）和线性阈值模型（Linear Threshold Model）这两大基本传播模型。简单来说，在独立传播模型中，每个点独立地作用于其相邻点，对于图中的一对连边的点对(u,v)，u只能影响点v一次，影响成功的概率为p_u,v。常见的传播概率包括均匀独立概率，即所有概率独立，p_(u,v)=p，以及带权重的独立概率，即所有概率为p_u,v=1/deg⁡(v)，其中deg⁡(v)表示点v的邻居个数。而在线性阈值模型中，每条边都被赋予一个权值，这一模型中会事先均匀采样一个权值，然后对于每个点，判断该点邻居中被影响的点对应的边权之和是否大于采样值，是的话该点就被影响，否则该点未被影响。这里常见的权值包括带权重线性阈值w(u,v)=1/deg⁡(v)。Kempe等人同时证明，在这些模型下，贪心算法可以做到1-1/e的近似。

　　陶表帅博士随后介绍了该问题的有向图和无向图版本，并用表格展示了这一系列工作的研究现状：在一些情况下，假设NP≠P，可以证明影响力最大化问题没有多项式时间算法做到(1-1/e+ϵ)的近似，对任意ϵ>0。陶博士提到，对于更多的情况，之前只能证明精确计算影响力最大化问题是NP-hard的，甚至有些情况也不确定是否是NP-hard的。而他们这份工作，推动了这一问题的研究进程：他们证明了这些情况下，影响力最大化问题是APX-hard的，即假设NP≠P，存在常数τ>0，使得这一问题没有多项式时间算法做到(1-τ)的近似。

　　接下来是陶表帅博士这次报告的技术部分：APX-hard结论的证明。陶博士以线性阈值模型为例，给出了证明的大体思路。整个证明框架分为两部分，首先对传播函数σ(S)给出合适的上界（如σ(S)≤|S|+|E(S,V∖S)|）。这一部分的证明用到了耦合论证（coupling argument）方法，将图中每条可能传播路径耦合到路径展开森林的一个点，并证明这样对应完后传播函数至少不减。对于森林，传播函数的解是显而易见的。这样就大致完成了这一部分的证明。

　　随后，陶博士基于一个变元度数不超过d的MAX-3SAT问题，构造一个社交网络场景，并证明如果有一个可满足的变元的赋值，那么该场景下的影响力至少为m+mD+md，其中D为某个足够大的常数。如果没有满足的变元赋值，PCP定理保证了这一问题没有1-γ近似，其中γ是一个大于0的常数。基于这一点，以及前述传播函数的上界，他们证明了该场景下影响力至多为m+mD+md-mγ。故对于常数τ=(1+D+d-γ)/(1+D+d)>0，假设NP≠P，这一问题没有多项式时间算法可以做到(1-τ)的近似（否则就可以给出MAX-3SAT问题的1-γ近似的算法）。

　　作为副产物，他们在两大基本模型下，分别给出了传播函数σ(S)的不同的上界，并提出了对应的局部启发式贪心算法，和其他启发式算法做了实验对比。这份工作已经被计算经济学顶级会议ACM EC 2019接收。

　　最后陶博士提到，这一领域还有一系列公开问题待解决，包括改进上下界，以及在更特殊的场景下，证明不可近似性等。报告引起了大家的热烈讨论，一些感兴趣的同学在报告后还和陶博士进行了交流。