课题组报告:密歇根大学陶表帅谈社交网络中影响力最大化问题

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

  

陶表帅报告中

  

  背景介绍

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

  

  

  在简要介绍了问题的背景和意义之后,陶表帅博士开始正式定义影响力最大化问题:在一个图G=(V,E)中,给定传播模型σ:2V→R,以及整数k,影响力最大化问题需要找一个集合S⊆V ,|S|≤k,使得集合S的影响力σ(S)尽可能大。这一问题的开创性工作来自Kempe,Kleinberg和Tardos,他们在2003年提出了这一社交网络中影响力最大化问题的基本框架,并提出了独立传播模型(Independent Cascade Model)和线性阈值模型(Linear Threshold Model)这两大基本传播模型。简单来说,在独立传播模型中,每个点独立地作用于其相邻点,对于图中的一对连边的点对(u,v),u只能影响点v一次,影响成功的概率为pu,v。常见的传播概率包括均匀独立概率,即所有概率独立,p_(u,v)=p,以及带权重的独立概率,即所有概率为pu,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接收。

  

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