确定性社会影响力竞争扩散问题研究

翁克瑞,沈 卉,侯俊东

(中国地质大学(武汉)经济管理学院，武汉 430078)

0 引言

近年来，社交网络的发展引人注目，这为病毒式营销创造了广阔的平台，即公司选择一定数量的有影响力的个人作为目标，通过口碑效应创造出大量的用户。影响力最大化问题为病毒式营销的理论基础，更正式地说，给定一个社交网络G和扩散模型M，影响力最大化问题研究选择一个包含k个个体的种子集S(即初始激活节点集)，这些个体能够激活最大数量的后续节点。该问题首先由Domingos和Richardson[1]研究，Richardson和Domingos[2]将网络建模为一个任意的马尔可夫随机域，并给出了最大化的启发式算法。Kempe[3]等人首先将问题表述为组合优化问题，提出了独立集联(IC)和线性阈值(LT)两种基本模型。他们证明了这个问题是NP困难的，并提出了一个贪婪算法。此后，大量研究主要集中在大规模社交网络算法的改进。如惰性计算[4-5]、最短路径[6]、有向无圈图[7]、局部树[8]、局部邻域[9]、度数修正[10]、学习自动机[11]、社团探寻[12-13]、进化算法[14-15]、随机超图[16]。然而，大多数现有的研究只关注于最大化单一产品的扩散。这种模型忽略了涉及多个传播实体的复杂社会交互。近年来，少数研究从竞争角度对独立级联模型和线性阈值模型进行了扩展，讨论了多种产品的最大化问题。如，Lu等[17]首先提出了竞争独立集联模型(Com-IC)，扩展了IC模型来描述具有竞争关系的多个影响的扩散。在此基础上，提出了自我影响力最大化问题和竞争影响力最大化问题。Ou等[18]也独立考虑了竞争影响力最大化问题。他们通过扩展LT模型为多产品扩散问题提出了交互线性阈值(ILT)模型，让后发者在知道先发者决策的情况下尽可能抑制先发者的扩散。Borodin等[19]提出了竞争环境下的采纳机制：消费者根据朋友圈中所有产品的市场占有率(A产品普及率/所有产品普及率之和)的概率选择产品A。在A产品扩散最大化的目标下，Borodin证明难以找到算法保证目标值不少于最优解的平方根。然而，Borodin没有给出有效求解问题的算法。Lu等[20]认为消费者主要受新激活用户的影响，提出了新的竞争机制：消费者根据朋友圈中(A产品新激活率/所有产品普及率之和)的概率选择产品A。然而，Lu等并非寻求A产品扩散最大化，而是寻求将一定数量的种子分配给多种产品的最优分配方案，使得所有产品的总扩散最大化。Bozorgi等[21]提出了两阶段竞争机制：第一阶段根据随机阀值决定是否采纳；如果采纳，第二阶段根据普及率最高原则选择产品。然而，Bozorgi等[21]的算法主要寻求如何用最少的种子超过竞争产品的普及率，而非寻求给定种子数量下的产品扩散最大化目标。此外，现在研究大多基于社会影响的随机扩散过程，在基于IC模型的竞争模型中，当一个非活动用户i在时间步长t上变为活动用户时，它将有一个成功的机会(概率为Pij)在时间步长t+1上独立地激活它当前非活动的邻居j，如果有多个产品在同一时间均能激活同一用户，则用户按照均匀概率随机选择其中一种产品。在基于LT模型的竞争模型中，用户j的阈值均匀分布在[0,1]范围内，其邻居N(j)的影响权重wij，其中Pi∈N(j)，wij≤1。如果传入的影响权重之和不小于其阈值，则j被激活，若多个产品同时激活同一用户，则用户按照权重比例随机选择产品之一。随机影响力最大化问题的目标是激活用户的期望数量最大化。

现有研究主要集中于随机阈值而非确定阈值可以归结为两个原因：一方面，由于对阈值信息掌握不充分，只能假定阈值为[0,1]均匀分布。另一方面，确定性模型失去了次模性特征(反映边际效益递减的函数特性，指新种子的边际扩散能力随着已选种子集合的增加而呈递减趋势)，使得确定阈值模型比传统的LT模型更难求解。然而，随着技术和先进算法的发展，这两个理由似乎已不再充分。首先，随着大数据技术在社交网络中的应用，现在实际上可以找到一些估算阈值的方法[22]。比如，在微信小程序中，可以了解同类app在朋友圈的普及率，假定用户按最大普及率选择产品，则最大普及率可作为确定阈值。再者，有一些算法可以直接应用于确定性模型，如基于中心测度的方法。一些研究开发出了不依赖次模性特征的求解算法，并且得到较好的结果[13,15]。同时考虑到这类基于随机化的扩散模型不利于建立具体的整数规划模型求解和跟踪分析扩散过程，本文研究确定性社会影响力竞争扩散问题(Deterministic Competitive Diffusion of Social Influence，DCDOSI)，即竞争环境下确定性社会影响力最大化问题。

本文首先，考虑竞争与确定性因素，结合现实营销决策拓展了社会影响力最大化问题，提出了DCDOSI，构建了该问题的整数规划模型，对小规模实例运用Gurobi的分支切割算法进行求解，并给出了计算实验结论；其次，为DCDOSI提出了基于扩散信息的边际影响力纠正算法(Diffusion Information Greedy，DIG)来获得大规模实例的解决方案。实验表明，改进后的DIG算法在保证了AG算法的求解质量的前提下缩短了90%以上的求解时间，且在大规模实例中的绩效表现始终领先于其它算法20%以上。

1 确定性社会影响力竞争扩散模型

1.1 问题定义

在真实的市场中，为了达到各自目的，A和B两家公司都会制定适合自己的初始用户选取方案。

在竞争环境下，一个产品激活用户需要满足两个条件：一是该用户收到该产品的影响力大于其激活阈值；二是该用户收到竞争产品的影响力弱于该产品的影响力，或竞争产品的影响力本身未达到阈值。称以上条件为确定性动态竞争阈值模型的规则。于是，在竞争的过程中，新产品B不仅要考虑用户对自己的阈值，还要考虑A的扩散情况，进而选择更优种子使得比A更早激活用户或者与A在同一激活用户阶段时使其影响力大于A，最终使得B的激活用户数量最大。影响力最大化问题就是研究在已知社交网络G(V,E)和A的用户时，如何从B的角度选择初始种子节点，使得最终B的激活用户数量最大化，该问题的定义如下所示。

确定性社会影响力竞争扩散问题定义：给定一个社交网络G(V,E,θA,θB)，其中,V={1,2,…,n}为所有节点的集合，E为边的集合，θA、θB为节点对A和B的阈值信息，已知A的种子集合为SA(SA∈V)，如何选择由k个节点组成的种子集合SB按照确定性动态竞争阈值模型的规则最终使得B所激活的节点数目最大。

1.2 整数规划模型

(1)

S.T. ∑iXi0=k∀i∈N

(2)

Yi0=1 ∀i∈SA

(3)

Xit+Yit≤1 ∀i∈N,t∈{0,1,…,T}

(4)

Xi,t≥Xi,t-1∀i∈N,t∈{1,2,…,T}

(5)

Yi,t≥Yi,t-1∀i∈N,t∈{1,2,…,T}

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2 种子选取算法

P1拥有网络规模二次幂级的变量和约束式，最快的求解器也不能得到竞争影响力在大规模网络里的扩散结果(例如：网络节点数量大于1 000时)，因此需要借助启发式算法求解。在本节中，算法的目标是基于确定性动态竞争阈值模型去找出k个种子节点，从而使k个节点组成的种子集合能够最大化B的传播范围。适应性贪婪算法可以直接用于求解确定性动态竞争阈值模型下的种子选取问题，但贪婪算法时间复杂度还是过高，在网络规模达到一定程度便无法在短时间内求解了。因此，本文提出了基于贪婪算法的改进算法：基于扩散信息的边际影响力纠正算法(Diffusion Information Greedy，DIG)。

DIG算法基于贪婪框架，算法流程如算法1所示，算法1、2步使用悲观策略让A完全扩散，第4步第一次计算所有候选种子的边际影响力的同时记录整个社交网络的扩散信息，之后迭代的选取边际影响力最大的种子并根据该种子和扩散信息更新其它候选种子的边际影响力和社交网络的扩散信息。

算法1 DC-DIG算法

输入：社会网络G=(V,E,θ)，最大扩散阶段限制T,A的种子SA，B的种子个数p

输出：B的种子集合SB

开放存取期刊在20世纪90年代末兴起，作为在线出版物，免费供用户使用。1995年，美国斯坦福大学建立了High Wire出版社，它是全球最大的免费提供全文的学术文献出版商，而且提供的都是高质量的电子期刊。最初它仅提供一种期刊，现在它已经能够提供《科学》、《美国国家科学院院刊》等多种高端刊物的电子全文［4］。

第5步：若|SB|≤p，则循环执行以下步骤：

1)令v*=argmaxν∈V(SA∪SB)mfv,SB=SB∪v*；

相对于AG算法而言，DIG算法的改进之处在于：运用数据结构记忆边际影响力的来源，当选择一个新的种子后，直接对边际影响力的来源进行纠正，进而近似更新边际影响力，从而避免所有候选节点的扩散模拟计算，节约了计算时间。其潜在收益更新策略如算法2所示，需要注意的是影响力扩散信息在算法1中的第4步初始化，其数据结构为词典Info，表示方式如下Info[i]={[s,u,invsv],…}，表示候选点s经过i的邻居u，扩散至i时产生了invsv的影响力。在更新过程中，对所有新种子扩散路径上的节点i，算法2步骤3根据Info[i]追溯并更新与i有关的侯选点边际影响力。

算法2 更新边际影响

第1步：初始化队列Q={s}，令mfs=0，受s影响的节点集合PATH=Ø。

第3步：∀u∈PATH，若au=B则执行a步骤，否则执行b步骤：

1)根据Info清除所有能到达u的边际影响力。

2)∀q∈Info[u],若Info[u][q][1]≠1,则执行以下步骤：

(2)mfq=mfq+mf′-Info[u][q][1]

(3)Info[u][q][1]=mf′

(4)若mf′=1，则令队列Q={u}，当Q≠Ø时，迭代的从Q中取出队首元素u执行以下步骤：

对于具有n个节点和m条边的图，DIG算法的时间复杂度为Ο((n*M1)+(N1*M2))，其中M1,M2≤m和N1≤n。M1是候选节点的影响路径中的边数。M2是所选种子的影响路径中的边数。N1是需要从活动节点更新其边际影响的节点数。

3 计算实验

在小型实验中，采用Barabasi-Albert[23]模型生成网络(设置平均度数为3、随机种子为100)作为实验网络。我们分别设置在节点数量为20、30、40、50、60、70、80的网络里使用Gurobi的分支切割算法(Branch & Cut)、AG算法与DIG算法选取B的种子，A产品的种子为随机选取的20%比例的网络节点。实验结果如表1所示，表1分别给出了DIG、AG、商业软件的求解质量与求解时间，同时最后两列分别比较了DIG与AG、AG与商业软件的求解质量差距。从求解质量上看，DIG与AG的激活数量差别非常小，通常只有一个节点数的差距，同时AG与商业软件最优解的差距也并不明显。这说明，从小规模实例的实验来看，贪婪算法的求解质量令人满意。然而，由于商业软件无法求解更大规模实例，算法在大规模问题的求解质量将通过与其它启发式算法的比较来反映。从求解时间上看，DIG算法相比AG算法节约了大量时间，同时AG算法也相比商业软件节约了大量时间。从实验结果上看，DIG算法相比AG算法节约了95%，AG算法相比商业软件节约了99%。此外，当问题规模超过80个点时，我们的实验机器已经无法在1小时内用商业软件求解，而DIG只花费0.005秒求解，求解质量只相差一个激活数量。算法时间节约的原因主要在于AG算法在选择新种子后，必须模拟扩散所有候选节点以更新边际影响力；而本文的算法通过数据结构记忆对溯源更新，以近似更新的方式避免了扩散模拟计算。

表1 小规模网络实例计算

为了比较DIG与各算法绩效，在扩展实验中我们使用了真实的社交网络数据集，Hept与Phy来源于http://research.microsoft.com/enus/people/weic/graphdata.zip，Epinion来源于http://snap.stanford.edu/data/，各数据集具体说明如表2所示。首先采用随机算法选取15%比例的网络节点作为市场先发者A的种子，再分别采用DIG算法、DD算法、PageRank算法、Random算法选取5%比例的网络节点作为市场后发者B的种子，在T=10下进行实验，实验结果如图1至3所示。图1显示了4种算法最终激活B的数量和求解时间的对比情况，观察可得DIG算法在求解质量上优势明显，且求解效率只存在线性差别。图2显示了在改变最大扩散阶段的限制时各算法的绩效比较，不仅可以得出DIG算法求解质量稳定领先，还可以得出扩散阶段限制在大于某一范围时便没有了“限制”效果，即增加扩散阶段不影响扩散结果。图3显示了在更改B的阈值时各算法绩效对比，DIG算法仍然始终领先其它算法且求解效率稳定。同时，图3表明随着阈值增加，激活数量会呈指数下降，这一现象可解释为：随着阈值增加，不仅消费者兴趣下降，同时竞争对手也会趁机渗透。综上，DIG算法具有良好的扩展性能。

表2 扩展实验数据集

图1 随种子数量变化的各算法绩效对比

图2 限制最大扩散阶段变化时的各算法绩效对比

图3 随阈值变化的各算法绩效对比

4 结论

影响力最大化(IM)最著名应用是病毒式营销，除了病毒式营销，IM在许多其他重要领域中也有广泛应用，如网络监控、谣言控制、社会推荐等。本文针对一类竞争环境下具有确定性阈值的社会影响最大化问题提出了两种方法。第一种方法基于整数规划模型，使用Gurobi优化软件求解问题模型，得到了小规模实例的精确解决方案。

第二种方法是包括DIG在内的启发式算法。启发式算法比Gurobi快得多，其中AG算法能够用更少的时间提供具有竞争力且更高质量的解决方案种子集。与现有其他算法相比，DIG算法的求解质量从对新产品最终激活数量上和对竞争产品的竞争策略都明显优于其他算法。通过对在线社交网络的数据挖掘，我们最终可以了解个人的阈值，也可以得到竞争对手的种子分布。在此基础上，竞争环境下确定性阈值模型可以扩展到各种产品与服务的竞争中，为创新产品或服务争取到更大的效益。

传统的贪婪算法难以处理5 000个节点以上的确定性竞争问题，本文提出的DIG算法能够在2分钟内求解70 000个节点的实例。然而，现实社会网络可能高达几十亿个节点，仍然无法直接运用DIG算法求解，有两个解决这类超大规模网络的思路：1)运用社区探寻的方法，对超大规模网络社区进行压缩；2)引入分布式计算与存储，进行并行运用。对超大规模现实网络的处理，将是该问题未来重点的研究方向。此外，近年来网络达人、明星直播的传播效应成为许多企业的营销手段，对于这类明星种子来说，节点成本将成为一个重要因素。考虑节点成本后，算法需要评估侯选节点的单位边际影响力(即边际影响力/节点成本)，然后按照背包问题的求解思路寻求解决方案。因此，考虑成本预算，节点成本的竞争扩散问题也是一个较有现实意义的研究拓展。此外，该问题还可以在考虑用户偏好、负面观点等方面开展研究。