社交网络影响最大化问题研究综述

王春佳

（西华大学计算机与软件工程学院，成都610039）

0 引言

在线社交网络是一种社会个体之间用来分享生活、学习、经验和观点的工具和平台。在线社交网络又被称为社交网络。社交网络具有平民性、非专业性、无门槛性。社交网络成为社会个体之间的信息传播的一种新的方式。因此，在线社交网络中的信息传播在多个领域引起了广泛研究，包括计算机科学、流行病研究等，并成为社交网络分析中的一个重点研究问题。

信息传播最大化，又称影响最大化，是信息传播研究领域中的一个研究内容，由于其具有的实际研究价值，近年来受到了广泛关注。本文主要围绕在线社交网络（本文关注微博客类，即Twitter、微博）中影响最大化问题的相关研究工作展开综述，首先概述了社交网络中的信息传播并分析了其特点；其次，介绍了国内外研究者对影响最大化问题所做的各类研究工作；最后，对这类研究存在的问题和未来的研究方向进行了概述。

1 社交网络上的信息传播

1.1 信息传播

信息传播是个人、组织和团体通过符号和媒介交流信息，向其他个人或团体传递信息、观念、态度或情意，以期发生相应变化的活动。在古时候，信息传播使用的是飞鸽传书、烽烟、风筝、孔明灯、飞骑、烟花爆竹、派遣信使等。不论是采用的是哪种方式，信息的传播都受到了地域和时间的限制。后来，由于科技的飞速发展，信息传播的方式发生改变，出现电话、电报传真、手机短信、电视等进行信息传播的媒介。这些现代信息传播速度较快，但信息量小。随着互联网的兴起，互联网被称为继报纸、广播、电视三大传统媒体之后的“第四媒体”。基于互联网的网络媒体集三大传统媒体的诸多优势为一体，是跨媒体的数字化媒体。互联网使信息传播更快捷、更方便。信息传播具有以下几个方面的特点：第一，传播表现为传播者、传播渠道（媒介）、接收者等一系列传播要素之间的传播关系；第二，传播过程是信息传递和信息接收的过程，也是传播者与接收者信息资源共享的过程；第三，传播者与接收者、相关人群之间，由于信息的交流而相互影响、相互作用。

1.2 社交网络中信息传播的特点

微博客类社交网络中的信息传播是通过用户之间的发布行为进行的。信息传播过程的参与者为：信息发布者、信息内容、信息接收者。

（1）信息发布者

原作者：信息原始内容的编辑者和发布者。

分享者：对信息感兴趣，添加内容或不添加内容进行再次发布的信息接收者。

（2）信息内容

信息原文：其中显示内容信息和原文作者。

加工信息：再次发布的信息接收者所编辑的内容。

（3）信息接收者

能够接收到传播过程中的原作者或分享者发布的信息的社交网络用户。

信息的发布者和信息的接收者之间是存在单向的或双向的关联关系的。“信息发布者-（信息内容）-信息接收者”为信息传播过程的“元过程”。社交网络中的信息传播是由无数个这样的“元过程”组成。

2 传播模型

信息传播最大化问题，又被称为影响最大化问题（Influence Maximization）。Domingos 和Richardson 是第一个研究影响最大化的人[1-2]。影响最大化问题最早是由Kempe 和Kleinberg[3]描述为一个离散优化算法问题。它研究的对象是一个社交网络图，表示为有向图或无向图G=（V,E），其中V 表示G 中节点的集合（对应社交网络中的用户），E 表示G 中边的集合（对应社交网络中用户之间的社交联系）。影响最大化问题旨在从G 中找到k 个用户，这k 个用户他们所能影响到的用户范围最大。由于影响最大化问题中的用户之间的影响是通过用户间的信息传播过程进行定义和量化的，我们先回顾影响最大化问题中所使用的几类常用的传播模型。

2.1 独立级联模型（Independent Cascade Model，IC）

独立级联（IC）是经典常用的且被许多研究者研究使用过的传播模型[4]。在独立了级联模型中，一个社交网络表示为图G=( )V,E ，V 为节点集，E 为边集，每条边e( u → v )有一个概率puv，puv表示节点u 把其邻居v 激活的概率。在传播过程开始的t0时间指定种子集S，这个传播过程从种子集开始以离散化的时间步骤进行传播。传播过程以下述原则进行。在时间t，每个激活状态的节点u 都尝试以成功概率puv去激活其指向的每个未激活邻居v。在此过程中，每个激活节点只能尝试激活其指向邻居一次。也就是说一旦这个节点尝试过激活其指向邻居，不论其邻居是否被激活，之后的时间步骤中只是保持激活状态而不进行激活行为。直到没有新节点再被激活，整个传播过程就停止。

2.1 线性阈值模型（Linear Threshold Model，LT）

2.3 触发模型（Triggering Model，TR）

Kempe 等人[3]提出了可概括IC 和LT 模型的触发模型（TR）。触发模型的主要思想在于：对于给定的节点v，分配触发节点集Tv代替LT 中的阈值，即如果Tv中有节点在步骤t-1 被激活，则v 在步骤t 中被激活。与IC 和LT 模型一样，触发模型的整个传播过程也是离散时间的。传播过程描述如下：

（1）首先为网络图G 中的每个节点随机选择一个触发节点集Tv，Tv是v 的所有邻居的集合的一个子集，以及选择一个已激活节点的集合作为初始的种子集；

（2）步骤t 中，对于还未被激活的节点v 而言，只要Tv中有一个节点u 在步骤t-1中被激活，则v 被激活；

（3）重复上个步骤，直到没有新节点再能被激活，整个传播过程结束。

2.4 其他模型

不论是IC 模型，还是LT 模型，亦或是TR 模型，都是以离散步骤进行传播的，即不再有新的节点被激活时停止。然而在实际情况中，传播过程中节点之间的影响是与时间相关的。因此，有研究者针对这个问题开展了相关研究[7-8]。基于IC 模型的连续时间（Continuous-Time，CT）模型[7]认为节点之间成对传播的可能性是时间的连续分布。即节点u 的激活时间tu和其邻居被u 所激活的时间tv满足条件分布p( tv|tu;αu,v)，其中αu,v为参数。CT 模型预先会给定一个停止时间T>0，时间T 内没有新节点被激活，传播过程停止。DynaDiffuse 模型[8]认为节点的传播速率随时间呈指数下降趋势。即给定节点u 的激活时间tu和u 激活v 的初始概率，则u 在时间tv>tu将v 激活的概率为。

又有研究者提出传播过程中网络结构是可能发生变化的。Tong 等人[9]提出了动态独立级联（Dynamic Independent Cascade，DIC）模型，该模型能够追踪真实的社会网络的动态拓扑结构。在DIC 模型中，种子节点可能以一定的概率无法被激活并且两个用户之间的传播概率服从一个分布，由此来反映一个社会网络拓扑结构的变化。

3 影响最大化问题

3.1 基于贪心算法的算法

2003 年，Kempe 等人[3]从离散优化的角度提出如何选择有影响力的种子问题，并证明了该问题是NP 难问题。同时证明了传播影响函数的次模性并提出了一种近似比为1-1/e-ε 的贪心算法，其中ε 是与社交图G 和r 相关的常数，r 是计算E[I（S）]估计值时的测量次数。基于IC 和LT，该算法从初始化S 为空集开始，通过向种子集S 中并入使得传播影响范围的期望E[I（S）]增长最大的节点，直到种子集S 中包含k 个节点，算法结束。

由于简单贪心算法的计算时间很长，通过进一步研究次模性质，Leskovec 等人[10]提出了CELF 算法，该算法利用影响函数的子模属性来计算影响扩散。而后，经过进一步的研究，Goyal 等人[11]提出了CELF++算法优化CELF，并提高了效率。UBLF[12]使用矩阵分析技术减少了CELF 的计算次数，并实现了2 倍到10 倍的加速。Lu 等人[13]提出了CascadeDiscount 算法，使用从ScoreCumulate 模型评估的初始影响中去除节点对邻居的影响损失来估计节点的边际收益从而达到减少计算时长的目的。同样的有好些研究工作[14-15]也对贪心算法进行过改进。虽然改进的贪心算法在传播概率较小的网络中性能良好，但是当网络规模很大或传播概率很大时，依然是高耗时。

3.2 基于启发式的算法

最早Domingos 和Richardso[1-2]提出了影响最大化问题：如何从社交图中寻找t 个初始节点，使得信息的最终传播范围最广，并提出选择全局影响最大用户的启发式算法。启发式算法避免传播概率对算法运行时间的影响。

2009 年，Chen 等人[16]提出了新的度折扣启发式算法，该算法非常有效并且能够产生良好的影响传播，其时间复杂度为O（klogn+m）。在提出的方法中，最初将每个节点的度视为其影响力的指标，并以k 步迭代选择种子。每个迭代步骤中，将影响力最高的节点作为新成员添加到种子集中。如果将节点v 作为新成员添加到集合中，则其邻居的影响力降低，并且随后它们被选择为种子的机会降低。还有一些研究工作[17-18]也是采用这样的方式。

Bao 等人[19]提出了一种启发式聚类方法，首先确定每对节点之间的相似度，然后将节点聚类为k 个不同的聚类。然后，选择每个群集中最具影响力的节点作为种子的成员。

Jiang 等人[20]提出了一种预期扩散值（EDV）度量来近似估计潜在候选种子节点的影响，并采用模拟退火算法来优化和识别有影响的节点。Gong 等人[21]改进EDV，并使用粒子群优化（PSO）算法最大化目标函数。Cui 等人[22]提出了一种使用差分进化算法最大化EDV函数找到种子集的方法。除了节点的影响外，还可以考虑将预算约束定义为IM 的优化问题[23-24]。

3.3 基于反向影响采样的算法

2014 年，Borgs 等人[25]发现没有必要对整个图进行计算而提出一种新的算法思想，即反向影响采样（Reverse Influence Sampling）。根据RIS 的思想，如果一个节点经常以“影响者”的身份出现，那么它可能是最有影响力的节点的良好候选者。基于该思想Borgs等人[25]提出了一种基于阈值的方法（RIS）。该算法需要运行O( ε-3· k·( n+m)·log2n )，并且以不小于1-1/n-1的概率得到近似比为1-1/e-ε 的近似解。

为了优化生成的子图的数量和采样方案，研究者提出了许多改进的方法来缓解基本RIS 算法的不足。Youze Tang 等人[26]提出了TIM 算法，通过使用组合可达性草图来逐步选择种子节点，其预期时间复杂度为O( ε-2· ( n+m)·log n )。此外通过改进参数估计，提出了TIM+算法。TIM＋算法具有与TIM 相同的最坏情况下的时间复杂度，但表现出的经验性能更好。进一步地，唐等人提出IMM[27]来改进TIM/TIM+，IMM 使用一组基于martingale 分析的估计技术，取得比TIM/TIM+更好的性能。

Nguyen 等人[28]提出了两种命名为SSA 和D-SSA的新颖采样框架用于IMM[27]方法的优化。尽管基于采样的算法可以在大规模网络中有效地选择k 个有影响力的种子节点，但是它们不可避免地会遭受巨大的存储成本的问题，因为必须生成大量的RIS 样本才能提供近似的保证，尤其是在大规模网络中。为了减少内存消耗，Wang 等人[29]提出一种惰性采样技术（BKRIS），将IMM[25]速度提高了两个数量级。

3.4 上下文感知影响最大化

近几年来，一些研究工作不再聚焦如何从算法层面对影响最大化问题进行研究，而是开始研究基于上下文感知的影响最大化问题。这类问题对传统的IM问题进行扩展，进一步考虑上下文特征，例如主题，时间和位置。基于主题的影响最大化问题：这类问题需要考虑被传播内容中的主题信息。这类研究问题又可被细分为节点主题感知[30-31]和边主题感知[32-33]，均有相关的研究工作开展。基于时间的影响最大化问题：传统IM 算法是在没有新激活点的时候停止。在实际情况中，这样的停止条件不合理。传播过程是随着时间逐渐变化的。因此，开始有将时间因素纳入传播过程中的研究开展。这类问题可被分为离散时间感知和连续时间感知。离散时间感知的研究工作[34-35]是将离散步骤作为时间度量，限制步骤长度。连续时间感知的研究工作[36-37]认为时间与传播过程密切相关。基于位置的影响最大化问题：随着基于位置的社交网络的普及，一些研究者[38-39]开始研究基于位置的影响最大化问题。基本思想是最大化目标位置相关用户的影响范围。

4 结语

本文概述了影响最大化问题使用的公认传播模型和几种基本的算法。影响最大化问题具有很大的现实应用空间和某些方面的技术困难，成为研究热点之一。同时由于这些现实应用，解决影响最大化问题（尤其是在大型网络中）时，如何在合理的时间消耗甚至内存成本之间很好地平衡求解精度就成为需要考虑的。因为社交网络中的网络结构不是一成不变的，因而影响最大化解决方案的可扩展性、鲁棒性是一个难点。随着越来越多的研究者投入研究，相信这些问题都可以得到解决。