社交网络中个体对群体影响力分析

顾亦然，马德营，孟繁荣

(南京邮电大学 自动化学院，江苏 南京 210023)

1 概 述

影响力分析是复杂网络的重要研究内容，现实社会中的诸多系统都是以复杂网络(complex network)的形式存在[1]。比如社会网络、互联网、交通网络、生物网络、社交网络等。其中，社交网络用户影响力的研究成为当前的热点之一。

为了深入研究及分析社交网络的节点重要性，学者们从网络结构等方面对节点影响力进行了广泛研究[2-6]。其中度中心性[3]、PageRank[4]、k-shell[5]、介数中心性[6]等算法刻画了节点在网络拓扑结构上的重要程度。度中心性(degree centrality，DC)刻画网络的局部特性，无法从全局刻画网络特征；PageRank算法认为节点的重要性取决于网络中指向该节点的节点数量和质量，容易陷入悬挂节点；k-shell是将网络一层层分解找出不同层次不同影响力的节点，其度量重要性比较粗粒化。

此外，节点的重要性不仅体现在拓扑结构上，其社会关系、行为特性同样对邻居节点产生不可忽视的作用。Richardson等[7]提出影响力的计算以及使其最大化是一算法问题。Wang等[8]发现影响力的传播大多发生在社团内部。王金龙等[9]提出了相对权重影响力模型并对影响力传播路径进行分析。肖云鹏等[10]提出了基于节点动态行为的影响力传播模型，但其主要是刻画影响力强度而未定量分析影响力。

当前，在线社交网络发展迅速，社交平台用户之间或因为现实关系或共同的价值观等逐渐形成网络群体，在群体影响力的相互作用下，网络群体行为涌现的更加迅速。例如，在微博社交网络中，由于兴趣等关注点的不同，一个用户可能隶属于不同社团，又由于亲密关系的不同，一个用户又可以在不同社团中进行消息的传递，那么这样的节点实际上成为不同社团间信息传播的桥梁，具有控制网络信息传播的能力。其传播的影响力不仅仅是按照最短路径产生作用，亲密关系也成为消息传递，信息分享的一个重要因素。因此影响力的传递作用不仅和社交网络的拓扑结构有关还和社会关系的因素有关，如文献[11]发现节点贡献度与节点重要性及其影响力范围都存在一定关系。

因此，针对社交网络中桥节点这样的特殊位置节点在信息传播中的重要性，考虑到此类节点信息交流的繁忙程度，以介数中心性作为描述节点拓扑结构重要性的参数；考虑到亲密关系对传播的影响，以节点间的贡献度来描述节点亲密程度，提出了一种个体对群体影响力算法，以此刻画该节点对整个网络的影响力贡献情况，即个体对网络群体的影响力。另外还对计算结果进行定量分析，用以研究其内在规律。

2 相关概念及定义

2.1 介数中心性

介数中心性(betweenness centrality，BC)是以经过某一节点的最短路径数目来刻画节点重要性的指标。它体现了网络中节点对网络信息流动的影响力[12]。具体地，节点vi的介数中心性如下：

(1)

2.2 节点间的贡献度

社交网络中节点之间的共同邻居越多说明节点间的关系越密切。其对彼此的影响力就不仅与自身所处的拓扑位置有关，还与共同邻居作用有关。现实生活中，节点vi对vj的影响程度和节点vj对vi的影响程度是有区别的，因此引入贡献度[11]这一概念。节点vi对vj的贡献度定义如下：

(2)

其中，Γi和Γj分别为节点vi和vj邻居节点的集合。

3 个体对群体影响力算法

文中将影响力看作是一种能够在节点之间进行传递的能量。那么，从节点vi传递到vj的能量多少，就是节点vi对vj的影响力。结合网络上刻画节点控制信息流动的指标介数中心性以及节点之间相互影响作用的贡献度概念，进一步描述个体间影响力的传递机制，建立个体对群体的影响力算法。

3.1 个体间影响力

正如上文所说，将影响力看作一种能够在节点之间流动的能量，该能量沿着节点连边进行扩散。如节点vi传递到vj的能量多少，就是节点vi对vj的影响力，可见，节点间的影响力刻画的是节点之间影响力传递能力的大小。

定义：个体间影响力fn(i,j)为沿最短路径从节点vi开始扩散到节点vj的影响力。

以计算fn(i,j)为例，计算过程如下：设从节点vi到节点vj的最短路径为vi→vx1→vx2…vxk-1→vj，其距离为dij，则有：

Cxk-1xk+αixk*BCxk*Cxkj

(3)

其中，α为根据路径远近设置的权重因子。

由于节点的影响力会因节点之间的距离远近产生差异，因此引入权重因子α[13]来分配计算权重。权重因子α与节点之间的距离dij存在以下关系：

(4)

其中，dij为始末两节点间距离；dik为初始节点vi到节点vk的最短距离，k取正整数。

3.2 个体对群体影响力

如果说个体间的影响力刻画的是节点之间影响力传递能力的大小，那么个体对群体影响力就是刻画节点影响力的全局特性，即节点的影响力扩散对全网的影响程度。

定义：个体对群体影响力为节点vi对群体R中所有其他节点的影响力之和，记为FiR。

在实际计算中，FiR从源节点依次计算至整个群体，显然复杂度太高。在研究中发现，并非要计算至整个网络，原因有二：其一，根据微信以及Facebook最新数据分析，复杂在线网络两节点间平均距离为3左右；其二，由实际计算比对中发现，路径的距离dij>3时，路径权重α的大小对于计算结果排序并无明显影响。基于上述分析，将FiR进一步定义如下：个体vi对群体R的影响力FiR为vi对距源节点路径距离dij≤3所有节点的影响力之和。公式为：

(5)

其中，Vi表示距节点vi路径距离dij≤3的节点集合。

3.3 个体对群体影响力算法描述

综上所述，算法描述如下：

输入：G=(V,E)

输出：节点vi对群体R的影响力

1.通过广度优选搜索算法获取节点vi到集合Vi中节点的路径与距离表D_path

2.计算网络节点间贡献度矩阵Cn

3.计算网络每节点BC值

4.计算节点vi到集合Vi中每个节点的影响力fn(i,j)

5.由式5将每条路径影响力加和，求得FiR

6.END

4 仿真分析

文中研究的FiR算法刻画的是节点影响力的全局特性，即节点的影响力扩散对全网的影响程度。显然，个体对群体的影响力是衡量节点重要性的指标之一。另外影响力大的节点往往是信息传播中的重要节点，信息传播能力强，传播至整个群体速度较快。基于这一思想，本节使用不同网络数据，通过经典的传染病模型进行仿真可以较为直观地分析节点信息传播情况，以验证算法的有效性。实验使用的网络分别为Email和Zachary，两网络参数如表1所示。

表1 网络参数

首先使用SI传染病模型，对Email网络进行传播验证，其传播概率为β=0.03。

4.1 网络仿真分析

4.1.1 Email

对Email网络进行FiR、BC、PageRank和k-shell算法分析，结果如表2所示，其中FiR的分析结果如图1(a)所示。

表2 Email网络各算法排名前三节点

(a)Email网络各节点FiR

(b)Email网络105、333、299号节点传播结果

(c)Email网络23、333、389号节点传播结果

根据表2排序结果，首先将四种算法排在第一位的105、333、299号节点进行传播仿真，结果如图1(b)所示。可以看出，FiR计算出来的105号节点在传播初期明显优于其他影响力指标得出的节点；基于上述的思想将FiR计算出来的23、333节点以及k-shell排序第二的389号节点进行传播仿真实验，结果如图1(c)所示。从图中亦能看出，在整个传播仿真中23号节点较优于333号节点和389号节点。

综上可知，该算法能够较为准确地衡量个体对群体的影响力。

4.1.2 Zachary

在Zachary网络中分别计算节点的FiR、BC、PageRank和k-shell，得到的结果如表3所示。

为了更全面地验证算法，本节传播仿真采用SIR传播。将文中算法排名前20%节点分别和其他三种算法得出的排名前20%节点进行传播比对，传播比对过程中去掉两算法中相同的节点，选取时间步为40，传播100次取平均，结果如图2所示。由图2(a)可知，文中算法选取的节点不但感染峰值比例高于后者，而且到达峰值的时间也比BC早；图2(b)中两者的差异更为明显；图2(c)中两个最大感染比例差异虽没有图2(a)、(b)大，但到达最大值的时间却比较滞后。通过上述分析对比，文中算法在SIR传播仿真中依然有较好表现。

表3 Zachary网络各算法排名前20%节点

(a)FiR与BC排名前20%对比

(b)FiR与PageRank排名前20%对比

(c)FiR与K-shell排名前20%对比

4.2 定量分析

对算法计算结果的定量分析过程如下：首先将Email网络FiR进行升序排列，如图3(a)所示，分别对横纵坐标取对数，对曲线的走向进行分析发现，起始阶段含有较多的节点但是这部分节点影响力的变化范围却很小；在曲线顶部虽然节点数较少，但其影响力却明显快速增加。通过数值计算可以得到前15.36%的节点影响力值总和等于后84.64%的节点影响力值总和。由此可知，只需对前15.36%节点施加影响力便能很大程度上影响整个网络。当然进一步分析前20%节点对群体影响力占总影响力为58.38%，并未出现或接近公众普遍认知的“二八效应”。同时，将FiR值均分150个区间段，取每段中间值代替每段的数值，计算落在每段节点的频数，其频数分布符合幂率分布,分布曲线为y=0.14*x-0.70。将数值和频数取对数进行拟合，拟合的结果如图3(b)所示，其斜率γ=-0.7。可见，网络中少数节点的影响力远远超过大部分普通节点的影响力。

图3 FiR算法结果定量分析

5 结束语

由于节点影响力物理表征和刻画方法到目前为止并没有一个相对完整的体系，文中将影响力看作是一种能够在节点之间进行传递的能量，提出了FiR的计算方法，并建立了算法模型，进行了SI和SIR传播仿真分析。结果表明，该算法在传播仿真中表现优异，能够准确地找出对群体影响力大的节点。进一步分析FiR的分布情况得出影响力值的分布情况符合幂律分布，具有无标度现象。