0 引言

随着在线社交网络的迅速发展及移动智能终端的迅速普及，社交网络中信息的传播对于国家和社会的影响日益深入，既给信息的传递和社交活动带来了便利，也可能构成影响社会稳定的隐患^[1]，例如，在2011年爆发的“埃及革命”中，不法分子利用Twitter和Facebook等社交网络使得骚乱极度放大^[2]。以国内新浪微博社交网络为例，目前的注册用户已超过5亿，每天有超过1亿条微博内容产生^[3]，对于如此大规模社交网络中的信息传播，如何快速、及时地发现当前社会热点事件或不良社会思潮，具有重要意义^[4]。

由于在线社交网络是典型的小世界网络，具有较短的平均路径长度和较高的聚类系数^[5]，社交网络的小世界现象和级联式传播方式具有很强的放大作用^[6]，因此某种信息在社交网络上的某个节点或多个节点传播，极有可能引起很大的社会影响。识别网络中最有影响的传播者、选取具有较强信息传播能力的关键用户，对于确保信息有效传播^[7]、信息传播控制和舆情监控具有重要意义^[8]。针对大规模社交网络，信息传播数量大，关键用户的选取也具有相当的挑战。

对此，本文综合考虑以用户作为节点的大规模社交网络的有向图结构信息，以及用户发布消息的历史数据，重点考虑影响用户信息传播能力的因素，研究用于快速有效地选取大规模社交网络中关键用户的方法，为突发信息传播控制和社交网络舆情监控等问题提供支撑技术。

近年来，研究人员针对社交网络中关键节点发现问题，从不同的角度提出了不同的方法。早期的社交网络关键节点计算，以Kempe等^[9]提出的贪心算法为代表，由于算法时间复杂度较高，随后出现了各种改进的贪心算法和启发式算法，如CELF(Cost-Effective Lazy Forward selection)^[10]和DegreeDiscount^[11]算法，这些算法面对大规模社交网络时效率仍然较低，并且这些算法主要考虑社交网络结构，而用户信息传播能力的定量度量机制，仍有待进一步研究。

从社交网络用户影响力度量的角度，研究人员提出了意见领袖发现或识别方法。例如:文献[12]从热门消息传播趋势预测的角度，提出基于消息传播的微博意见领袖影响力建模与测量分析方法；文献[13]基于微博文本数据分析，从结构、行为和情感三个维度度量用户影响力，从而识别意见领袖。针对大规模社交网络的意见领袖影响力建模技术，仍有待进一步研究；同时，针对社交网络中突发事件和不良突发信息检测等问题，发现具有较强信息传播能力的关键用户，与意见领袖识别具有同样重要的意义。

从社交网络中用户关系建模角度，文献[14]以贝叶斯网作为社交网络中用户之间依赖关系表示和推演的知识模型，利用模型的结构特征和贝叶斯网的概率推理机制，提出了用于关键用户发现的MapReduce算法，但仅考虑了网络结构信息。文献[15]考虑用户交互影响及其动态衰减，提出基于霍克斯过程的社交网络中用户关系强度模型及预测方法，但对于支持社交网络中突发事件检测的用户信息传播能力度量，还需进一步研究，并且针对大规模社交网络的建模和度量方法的效率仍需进一步提升。

因此，为了在大规模社交网络中快速有效地选取关键用户，本文的研究面临以下三方面的挑战和问题：1)大规模社交网络的高效计算；2)用户信息传播能力的有效度量；3)关键用户的有效选取。

Spark是一个面向分布式海量数据分析、基于内存的迭代计算通用框架^[16]，其GraphX工具可以高效地执行大规模图的操作算法^[17]，因此，针对问题1)，本文使用Spark作为数据处理框架，设计基于Spark的大规模社交网络计算与处理算法。

PageRank^[18]算法的核心思想是，每个节点的PageRank值，简称PR值，取决于所有指向它的节点的PR值，且平均分配给它所指向的节点。然而，在社交网络中，用户(即节点)的信息未必总是平均地传播到它所指向的用户，用户之间相互关系的强度(例如不同用户之间消息转发频度)，即节点之间边上的权重，对信息传播也具有重要的影响。因此，针对问题2)，首先基于用户发布消息的历史数据构建带权的社交网络模型，然后借鉴PageRank算法并对其进行扩展，从而有效地度量用户节点的信息传播能力。

针对问题3)，为了使选取的用户可以有效地用于检测社交网络中的突发信息或舆情监控，本文提出了d-距选取算法，其核心思想是通过多次迭代使得所选取用户之间的最短路径长度大于参数d，使得所选取的关键用户的信息传播范围尽量少地重叠。

总的来说，本文的主要工作概括如下：

1) 利用社交网络的结构信息，构建以用户为节点的有向图，利用用户发布消息的历史数据，基于Spark定量计算由用户活跃度、转发交互度和信息量占比刻画的权重，从而构建社交网络的有向带权图模型。

2) 基于大规模的有向带权社交网络模型，通过用户粉丝节点对其信息传播能力贡献值的累加来衡量用户的信息传播能力，借鉴并扩展PageRank算法，给出基于Spark的节点信息传播能力的度量方法。

3) 针对突发信息检测和舆情监控等应用中选取关键用户的高效性和有效性需求，给出基于Spark的d-距选取算法，通过多次迭代，快速选取关键用户，且不同关键用户的信息传播范围尽量少地重叠。

4) 建立在新浪微博数据集和Spark分布式集群上的实验，测试了本文方法的高效性、可行性和可扩展性。

1 社交网络模型构建

不失一般性，本文用带权有向图G=(V, E)作为社交网络模型^[19]，其中，V为节点集(|V|=n)，节点表示社交网络中的用户；E为有向边的集合，边表示用户之间的关注关系，从v_i到v_j的有向边上的权重w_ij表示v_i对v_j信息传播能力的贡献(1≤i, j≤n, i≠j)。一个包含3个用户的社交网络如图 1所示。

用户发布消息的历史数据中，一条记录的基本信息包含用户、内容、时间及来源，可表示为Item=(v_i, c, t, f)。其中: v_i表示用户，c表示消息内容，t表示消息发布时间; f用以标识消息的来源，若f=0表示该消息为用户原创，否则表示转自其他用户。基于图 1中的社交网络，用户历史消息数据片段如表 1所示。

G中有向边上的权重定量地刻画了存在直接关注关系的用户之间的信息传播关系，是定量度量用户信息传播能力的基础，对此，本文选择与信息扩散和用户相互影响的主要因素作为用户之间权重的度量指标，即用户活跃度、转发交互度、以及信息量占比。进而，可利用用户的历史消息定量地计算上述3个指标的值，从而得到G中边上的权重。

1.1 度量指标定义 1.1.1 用户活跃度

用户活跃度记为a(v_i)，通过用户在一段时间内所发布信息量d(v_i)和转发率r(v_i)两个方面来衡量，反映用户对信息传播的活跃情况，如式(1)：

$ a({v_i}) = d({v_i}) * r({v_i}) = \frac{{{n_p}({v_i})}}{p} * \frac{{{n_{rp}}({v_i})}}{{{n_p}({v_i})}} $

(1)

其中：n_rp(v_i)与n_p(v_i)分别表示用户在这段时间内所转发的信息量、发布的信息量，通过用户历史消息数据统计计算得到；p为时间段长度。

1.1.2 转发交互度

转发交互度记为e_ij，由用户v_i转发v_j消息的概率p_ij和v_j对v_i的重要程度z_ij决定，体现用户对于信息转发的交互在其关注节点上的差异，如式(2)：

$ {e_{ij}} = {p_{ij}} * {z_{ij}} = \frac{{{n_{rp}}({v_i} \to {v_j})}}{{{n_p}({v_j})}} * \frac{{{n_{rp}}({v_i} \to {v_j})}}{{{n_p}({v_i})}} $

(2)

其中，n_rp(v_i→v_j)表示节点v_i转发v_j的信息量，通过用户历史消息数据统计计算得到。

1.1.3 信息量占比

若社交网络中节点v_i的某段时间所发信息量为n_p(v_i)、其关注为节点v_j，则v_j发布的信息量在v_i所关注节点发布信息总量的占比为h_ij，如式(3)：

$ {h_{ij}} = \frac{{{n_p}({v_j})}}{{\sum\limits_{k \in fri({v_i})} {{n_p}({v_k})} }} $

(3)

其中fri(v_i)表示节点v_i所关注节点的集合。

1.2 权重计算

前述3个指标中，用户活跃是信息传播的诱因，信息量占比反映的是用户之间的影响程度，在用户活跃与用户之间有影响的情况下，进而通过转发交互才能向其他用户贡献自己的信息传播能力，因此本文将这3个指标的值相乘来度量节点之间信息传播能力的贡献，即社交网络中边上的权重，v_i到v_j的有向边上的权重w_ij由式(4)计算：

$ {w_{ij}} = a({v_i}) * {e_{ij}} * {h_{ij}} = \frac{{{n_{rp}}({v_i}) \times n_{rp}^2({v_i} \to {v_j})}}{{p \times {n_p}({v_i}) \times \sum\limits_{k \in fri\left( {{v_i}} \right)} {{n_p}({v_k})} }} $

(4)

可以看出，利用用户的历史消息数据，就可以计算式(4)中所需的n_p(v_i)、n_rp(v_i)、n_rp(v_i→v_j), 以及$ \sum\limits_{k \in fri({v_i})} {{n_p}({v_k})} $；特别地，n_rp(v_i→v_j)的值从1开始累加，反映用户之间没有转发交互也可能有一定的影响。

例1  为了确定图 1中社交网络各有向边上的权重，首先对形如表 1中的数据片段进行统计计算，得到如表 2所示的统计信息，其中，“v₂:2”表示来自节点v₂的转发量，式(4)中参数p的值为1，则可得到w₁₂、w₁₃、w₂₁和w₂₃的值分别为0.67、0.17、0.67和0.17。

2 基于信息传播能力的关键用户选取 2.1 节点信息传播能力计算

节点信息传播能力，以定量的方式反映了社交网络模型中某一节点对信息传播的作用，其值为其所有粉丝节点对其信息传播能力贡献值的累加。在此，本文借鉴PageRank算法^[18]，采用NodeCapacity算法计算节点的信息传播能力，简记为NC，其核心思想是:在社交网络模型中，每个节点的NC值为其所有粉丝节点对其贡献值的累加，每个节点的NC值以边上权重的形式贡献给它关注的节点，如式(5)所示：

$n{c_i} = 1 - q + q\sum\limits_{j \in foll({v_i})} {n{c_j}*{w_{ji}}} $

(5)

其中：nc_i表示节点v_i的信息传播能力；foll(v_i)表示关注节点v_i的节点集；w_ji表示节点v_j对v_i信息传播能力的贡献权重；q为阻尼系数，q∈(0, 1)。

针对大规模的带权社交网络，本文首先使用Spark中用于图操作的aggregateMessage方法，将各节点其粉丝节点的NC值以边上的权重汇聚并作为其NC值，然后基于图操作joinVertices方法将汇聚后的值更新为相应节点的NC值，依此进行多次迭代操作，上述思想由算法1给出。

算法1  NodeCapacity。

输入 G为带权社交网络图，N为给定的迭代次数阈值。

输出 NG为带有节点NC值的社交网络图。

1) var g ← G

2) var iteration ← 0

3) var pG: Graph[Double, Double] ← null

   /*用于释放缓存的图RDD*/

4) WHILE iteration < N DO

5)   g.cache()      /*缓存图RDD*/

6)   var updates ← g.aggregateMessage[Double](ctx =>

       ctx.sendToDst(ctx.srcAttr * ctx.attr), _ + _,

       TripletFields.Src)

       /*汇聚其粉丝节点的贡献值*/

7)   pG ← g

8)   g ← g.joinVertices(updates) { (id, oldAr, msgSum) =>

      (1.0-q) + q*msgSum}

      /*更新图节点中的NC值*/

9)   pG.unpersist(false)      /*释放图RDD*/

10)   iteration ← iteration +1

11) END WHILE

12) NG ← g

算法1的执行代价主要取决于步骤6)和8)中的图操作，其执行代价取决于社交网络中节点及其粉丝节点数，时间复杂度为O(mn)，因此，算法1的时间复杂度为O(lmn)，其中，l为算法迭代次数，m为每个节点的平均粉丝节点数，n为社交网络中所包含的节点数。此外，算法1的收敛性与PageRank算法相同，二者的主要区别仅在于节点对于其关注节点的贡献的分配方式，PageRank算法根据节点的出链数进行平均分配，而算法1按照边上的权重进行分配。

例2  针对图 1中的社交网络，假设节点v₁、v₂和v₃的当前NC值分别为nc₁、nc₂和nc₃，算法1的一次迭代操作为：首先由步骤6)得到各节点的汇聚值upNc_i，若upNc₁为nc₂*w₂₁、upNc₂为nc₁*w₁₂、upNc₃为nc₁*w₁₃+nc₂*w₂₃，则由步骤8)，用节点的汇聚值更新相应节点的NC值，得到新的NC值，节点v₁的NC值为(1.0-q)+q*upNc₁。

2.2 关键用户选取

对于社交网络G=(V, E)，本文希望从V中选取关键节点集S，S⊂V，|S|=k，使得S中的节点在G中具有尽量大的信息传播范围，即能够尽量多地影响到其他节点。首先，关键节点应该具有较大的信息传播能力，即具有较大的NC值；其次，不同关键节点的信息传播范围应该尽量少地重叠。若给定节点的信息传播范围阈值d，则节点v_i的信息传播范围可用从v_i出发经过长度不超过d的路径可到达的节点集来描述。

因此，为了高效地选取关键节点，在选取G中的k个关键节点时，每次选取当前具有最大NC值的节点，然后将该节点及与其之间路径长度不大于d的节点进行标记，不作为待选取的关键节点，从而使得选取的节点之间的路径长度都大于d，经过k次迭代，可高效地选取k个关键节点(即关键用户)。根据社交网络的小世界特性，将d的取值范围设为1~6。

针对大规模社交网络，本文基于Spark实现上述关键用户选取的思想，称为d-距选取算法。首先，向图的reduce操作传入一个比较函数，进而选取出当前具有最大NC值的节点、并将其作为关键节点；然后，将与所选取节点之间路径长度不大于d的所有节点的NC值都置为0；接着，使用图的subgraph操作去除NC值为0的节点，以生成一个新的子图，如此进行多次迭代操作。上述思想见算法2。

算法2  d-距选取。

输入 G为带有NC值的图G=(V, E)(由算法1得到), k为关键节点个数，d为路径长度。

输出 S为关键节点集合。

1) var g ← G

2) var S ← new ListBuffer[(Long, Double)]      /*保存关键节点*/

3) var pG: Graph[Double, Double] ← null       /*用于释放缓存的图RDD*/

4) def max(a, b)      /*定义一个比较函数*/

5) FOR i ← 0 TO k DO      /*选取k个关键节点*/

6)   var t ← g.vertices.reduce((a, b) =>max(a, b))      /*选取具有最大NC值的节点*/

7)   S ← S ∪{t}      /*将选取的节点t添加到S中*/

8)   pG ← g

9)   FOR j ← 1 TO d DO

10)     g ←将与节点t的最短路径长度小于等于j的所有节点的NC值置为0

11)   END FOR

12)   g ← g.subgraph(vpred=(id, attr)=> attr > 0.0)

     /*从g中去除NC值为0的节点*/

13)   pG.unpersist(false)

14) END FOR

15) RETURN S      /*返回关键节点集*/

算法2的执行代价主要取决于步骤5)~14)中图操作执行时节点、关注节点及其粉丝节点的数量，步骤6)中图操作的时间复杂度为O(n)，步骤9)~11)的时间复杂度为O(dmn)，步骤12中图操作的时间复杂度为O(mn)，因此，算法2的时间复杂度为O(kdmn)。其中，k为选取的关键节点个数，d为路径长度，m为平均每个节点的粉丝节点数，n为社交网络模型中包含的节点数。

例3  针对图 1中的社交网络，若节点v₂的NC值为当前最大值，若阈值d为1，算法2执行时的一次循环操作为：首先，由步骤6)选取节点v₂，由步骤7)将v₂加入到关键节点集S中，然后由步骤8)~11)将节点v₂、v₁和v₃的NC值设为0，由步骤12)去除这些NC值为0的节点，从而以生成一个新的子图，以进行下一次迭代操作。

3 实验结果

为了测试本文算法的有效性，在Spark集群环境下实现了本文方法，采用新浪微博数据集进行性能测试。首先从数据堂(http://www.datatang.com/detail/6)下载微博用户关系数据集，从中提取出度数大于10的节点，形成一个社交网络，然后使用网络爬虫技术抓取用户发布的消息数据。数据集包含4 269 813个用户节点，共有69 060 604条反映用户之间关系的边，包括67 432 812条2016年5月的用户消息历史数据集，大小为10.75 GB；集群环境由1个Master节点和10个Worker节点组成，其中Master节点CPU为4核、2.2 GHz主频、32 GB内存，Worker节点CPU为2核、2.2 GHz主频、16 GB内存。我们首先测试了关键用户选取结果的有效性，然后测试了算法1和算法2的执行时间、加速比和并行效率。

3.1 有效性测试

为了测试利用本文方法所选取关键用户的有效性，根据新浪微博舆情系统2016年6月热点舆情报告(http://blog.sina.com.cn/s/blog_ec0961940102wn59.html)中的TOP-10社会热点事件，对所选取关键用户的有效性进行评测，测试指标包括捕捉率(Catch Ratio, CR)和捕捉收益(Catch Profit, CP)，其中CR为通过选取的关键用户检测到的突发信息与网络中实际存在的突发信息的比值，CP为通过选取的关键用户对突发信息的检测而可遏制信息量所占比例。这两个评价指标的值越大，说明选取的关键用户的有效性越大。

首先测试关键用户数量k和路径长度阈值d对CR的影响，如图 2所示。可以看出，k与d对CR的影响较大；当d为2时，随着关键用户数量k的增加，CR值稳定增大，基于本文的方法选取关键用户的有效性更加显著。

然后将本文中关键用户选取结果与基于PageRank^[18]和DegreeDiscount^[11]进行关键用户选取的结果进行比较，测试了不同方法的CR和CP，其中将本文方法中路径长度阈值d设置为2。图 3给出了关键用户数量为10、20、30、40和50的情况下，本文方法、PageRank及DegreeDiscount算法对CR的影响。可以看出，随着关键用户数量的增加，本文方法的CR明显优于PageRank及DegreeDiscount算法。

进一步测试本文提出的关键用户选取方法对新浪微博社交网络中的真实突发事件检测的CP，如图 4所示。事件1~事件6分别为“小学生当街闹分手”“8名江西高中老师为学生出征壮行”“六一妈妈偷鸡腿给生病女儿”“网现史上最强的考研指导”“西安南郊变电站闪爆”及“上海浦东机场T2航站楼发生爆炸”。由图 4可以看出，基于本文方法、PageRank及DegreeDiscount算法选取的关键用户检测到的评测事件有所差异，在捕捉到的情况下，各方法的捕捉收益CP基本都在0.75以上，不少情形达到了0.9以上，表明这三种方法选取的关键用户可以较早地检测到评测事件的传播，进而可以对事件的扩散有很好的控制。这说明本文提出的关键用户选取方法，对于用来检测社交网络中的突发事件是有效的。

3.2 效率测试

为了测试算法1和算法2的执行效率，本文将数据集划分为规模为2.2 GB、4.4 GB、6.6 GB、8.8 GB和11 GB的5个数据块，基于这5个数据块构建相应的边数逐渐增加的有向带权社交网络模型，ID分别为1、2、3、4和5，节点数和边数如表 3所示。

在Worker数(计算节点)为1、2、4和8的情况下，本文分别在这5个社交网络模型之上，对算法1和算法2的执行时间、加速比和并行效率进行了测试。通过反复测试，将迭代次数阈值设为10，此时节点信息传播能力的计算收敛；将d和k分别设置为2和50。

算法1和算法2基于不同规模的社交网络模型在不同Worker数下的执行时间如图 5所示。

可以看出，算法1和算法2的执行时间在同一Worker数量下随着社交网络规模的增大而呈线性增长；社交网络规模一定时，执行时间随着Worker数量的增多而明显减少，说明算法1和算法2在数据规模增大时，可以通过增加Worker数来大幅降低其执行时间，即能有效地处理大规模社交网络。

加速比是算法在1个Worker节点与多个Worker节点情形下执行时间的比值。在不同规模的社交网络上、不同Worker数情形下，算法1和算法2的加速比如图 6所示。可以看出，社交网络规模一定时，加速比随着Worker数量的增多而明显增大。当Worker数为2时，加速比均接近1.5；当Worker数为8时，加速比随着社交网络规模的增大而明显增加，说明算法1和算法2具有较好的并行性和可扩展性。

并行效率是算法加速比与Worker数的比值。在不同规模的社交网络上、不同Worker数情形下，算法1和算法2的并行效率如图 7所示。可以看出，算法1和算法2的并行效率在同一Worker数量下，随着社交网络规模的增大而缓慢增大，在Worker为2时，并行效率增大不明显，主要是因为已达到一个比较大的值，由于社交网络规模划分不均匀而造成并行效率和加速比的抖动，说明算法1和算法2具有较好的并行性，且较适合处理大规模社交网络。

4 结语

利用社交网络的结构信息和用户发布消息的历史数据，本文给出了社交网络中用户信息传播能力的定量度量机制，提出了一种高效的大规模社交网络中关键用户的选取方法，并给出了基于Spark的算法实现。在新浪微博社交网络真实数据集上，测试了本文所提出方法的可行性、高效性和可扩展性。本文提出的关键用户选取方法，可作为支撑技术用于解决大规模社交网络中突发信息检测和舆情监控等问题。

然而，本文提出的用户信息传播能力度量和关键用户选取方法，仅考虑用户传播消息的行为而未考虑传播信息的内容，因此可能产生消息主题漂移而选出“伪关键用户”。为了使得选取的关键用户更加准确有效，基于社交网络结构信息，将用户传播消息的行为与用户之间转发交互的内容结合起来，可进一步完善关键用户的性质和选取方法。将社交网络的影响最大化及种子节点选择的已有方法用于本文中关键用户的选取，对目前的方法进行改进，是将要开展的工作。