群体对个体影响力传播算法

顾亦然，赵 栋，孟繁荣

（南京邮电大学自动化学院，江苏 南京 210023）

0 引言

社交网络兴起在一定程度上打破了固化的社会结构，使得社会各阶层的领袖、精英和大众都可以在社交媒体上拥有自己的“麦克风”，扮演着信息制造者、传播者和接收者的多重角色。信息经由一层一层的信息传播圈迅速向外传递的过程中，逐渐形成不同的群体化行为。

扎利亚·戈维特在一篇关于“群体极端化”的文章中写到，人们的头脑总是受周围群体的影响而出现意见趋同现象。网络群体作为虚拟网络社会中的网民，对某一事件或主题表现出的群体行为，已经被多次的真实事件表明，这些群体性行为可以撼动事件的结果。因此，社交网络的舆情已经从公众舆论的折射场转为了引发地、爆发场，成为网络舆情的重要阵地，对社会活动影响深远。身处舆论中的普罗大众们通过各自的影响力相互作用，组织演化，使得在线社交网络的舆情呈现出多样化和复杂性[1-3]。

群体行为作为大规模的非正式的行为，往往带有一定破坏性。如，网络舆情、社会突发事件、公共危机、网络攻击等。因此，有必要针对个体的行为特点和影响力的关联性进行研究，进一步理解和揭示影响力的作用机制和潜在的机理[4]。

1 研究现状

近年来，随着社会中突发舆论事件的不断增多，关于网络群体及群体行为的研究备受学界的关注。有很多学者从自然科学和交叉学科的角度建模研究网络舆论中的个体和群体的社会化影响，试图深入分析传播的交互机制。从建模方式上来看，有的模型侧重于群体特征的描述，直接建立群体行为的动态演化过程模型；有的模型侧重于刻画个体的交互机制[4]，通过建立个体观点的更新规则模型，研究宏观上产生的群体观点演化现象。Li等[5]对在人类行为中普遍存在的极化现象的机理进行深入研究，并运用阈值理论解释骚乱暴动等激进群体行为，以及 Web上群体观点极化与社会认同理论之间的联系；朱丽萍等[6]认为情绪效价作为社会信息的重要特征，影响着人们对信息的感知与加工，相对于中性刺激，人们对情绪性刺激（正性和负性）的加工更加迅速，表现为对情绪刺激的反应时间缩短，说明情绪刺激能更快地进入认知加工，信息的情绪特征能更快地调动认知资源；刘凯等[7]通过构建结构方程模型计算了互联网舆情中网民参与心理对参与行为的路径系数，测定了网民不同舆情参与心理下舆情参与行为的强度，同时对各因素进行了有效分析；Hegselmann R等[3]探讨了不同在线论坛用户参与行为，发现在线论坛用户之间的关系存在随机性且用户之间信任性较弱，用户对在线参与行为显示出了强有力的规律。Li N等[6]以人类的信息传播行为为例做了实证研究，发现在人类的行为中普遍存在幂律特性；Gunjan Verma等[8]认为当出现相斥证据时，有些人的观点容易受到他人影响而改变其原有观点；不断有学者指出等[9-10]指出处于社会网络结构中的有些人会受到邻居节点的影响[12]，并证明影响值正比于累计的回报值。Bonzom V基于Ising模型，在无标度网络结构中，考虑个体的空间位置和人际交往的双层等级结构，构建了人际交往的观点形成模型。该模型认为个体对其他个体的影响程度取决于他们的权威度；Gargiulo F等[13]证明了有些人在制定决策时会受历史选择与旁人的影响。可见，群体一个很重要的特征就是群体化的影响力。而从影响力的角度来看，上述描述现阶段多数都是从个体与个体的角度分析影响力。还鲜有从个体与群体角度来分析研究影响力，也没有对影响值进行定量分析。因此本文通过研究群体对个体行为的影响力作用，提出了群体对个体的影响力交互模型，并对该算法进行定量分析。

2 相关概念及定义

2.1 K-Shell

Kitask等人认为位于网络核心位置的节点i即使其度值很小，其对网络的影响力也很大，相反的，即使节点 j具有很高的度值，但是位于网络边缘位置，则其对网络的影响力并没有节点i大，基于此提出了K-Shell (K-壳)分解算法，这是一种粗粒化的节点重要性分类方法。它体现了网络中节点影响力的扩散，类似能量向外一层一层在涌动。

K-Shell分解算法分解步骤如下：假设网络中不存在度为0的节点，即每个节点度值 k ≥ 1，先将网络中所有度值为 1的节点剥落，剥落所有度值为 1的节点后，生成的新网络中会继续有度值为1的节点，重复之前的步骤，继续进行剥落度值为1的节点，直到新网络中所有的节点的度值 k ≥ 2 ，把所有剥落的节点称为网络的1-Shell（1-壳）；新网络中节点的度值有 k ≥ 2 ，同第一步相同，重复剥落度值为2的节点，直到网络中所有节点的度值 k ≥ 3 ，将这一步剥落的节点称为网络的2-Shell。以此类推，进一步得到网络的3-Shell、4-Shell等更高的Shell层，直到网络中的所有的节点都被剥落，这样网络中的每个节点都有对应的K-Shell值 ks，例如属于2-Shell的节点，其 ks= 2 ，对于属于K-Shell层的节点都有度值 k ≥ks。

2.2 贡献度

网络可以抽象为节点集 V(Vertex)与连边集E(Edge)组成的图 G=(V,E)。通过节点间连边关系反应网络情况，在现实网络中节点对彼此间的影响力是不同的，比如Vi节点是一个影响力很大的节点而Vj节点则是一个影响力较小的节点，Vi对Vj的影响力要高于Vj对Vi的影响力，为了表征这种差异，引入贡献度[11]这一概念，节点 i对 j的贡献度定义见公式（1），其中 i和j分别为节点Vi和Vj邻居节点的集合。

3 群体对个体影响力算法

3.1 亲密度

表1 社交关系亲密度的符号和含义Tab.1 The symbol and meaning of social relationship intimacy

3.2 群体对个体的影响力

上文中节点的 Ks值的大小表示网络中该节点所在的核心位置，既影响力传播深度。贡献度表述节点某属性对各邻居节点的贡献情况。综合考虑节点对全网信息的传播影响力，将相邻个体间影响力定义如下。节点iv对节点jv的影响力，为节点iv的K-Shell值、节点iv对节点jv的贡献度、节点iv对节点jv的亲密度因子三者的乘积：

定义 1：群体由微博、微信最新数据分析，在线社交网络两节点间的平均距离为 3，因此本文在做群体对个体影响力分析时，计算仅考虑路径距离为3以内的所有节点群体。

节点在群体中受到的平均影响力定义：首先本文使用广度优先搜索算法，可以寻找到网络中，某节点iv三步之内的所有节点集合iV（实验表明两步范围太小不够全面，四步开始对结果影响很小，故这里选择了三步）。由公式（2）可以计算出iv对集合内所有节点的影响力，再进行求和记为节点iv对群体的影响力iGF 。其次，本文计算出网络中 m个节点对群体的影响力之和，再求平均数记为 i节点在群体中受到的平均影响力大小：

群体对个体影响力算法：假设要求群体对目标节点 t的影响力大小，考虑到每个群体对个体造成最直接影响的因素，往往是群体内具有群体观点，且与目标个体有直接交际关系的节点，对目标节点带来的影响。因此本文使用广度优先搜索算法找出群体内与节点tv相连一步之内的所有节点（m节点，l节点…），然后用群体影响力与相邻个体影响力的乘积，再求和记为整个群体对个体的影响力：

3.3 基于影响力的传播

综上所述，可以得出群体对个体影响力传播的算法，如下所示：

输入：G=(V,E)

输出：群体对节点 vt的影响力 FGt

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

2）计算网络中每个节点的k-shell值；

3）计算网络中每个节点间的贡献度 Cn(i, j)；

4）计算i节点在群体中受到的平均影响力大小FG；

5）由公式（4）求得群体对目标节点 vt的影响力 FGt。

6）END

4 仿真实验

4.1 Email网络仿真

通过本文的算法可以确定群体转移给每个节点的影响力值，考虑到从群体转移到目标节点的影响力越大，反过来从该节点向群体可以传播的速度就越快，广度也相应越远。本节使用经典的传染病模型进行仿真，能够较为直观地监测到节点传播情况。本文使用SI传染模型，并在随机网络与Email网络中实现仿真。在 Email网络总进行群体对个体的影响力排序分析，结果如表2所示。

表2 Email网络本算法与经典K-shell算法排名前三节点Tab.2 The algorithm of Email network and classic k-shell algorithm rank the top three points

根据上述排序结果，首先选定节点105号与299号进行传播仿真，结果如图 1所示，105号传播效果明显优于299号；同时将排序第二位及第三位的节点对进行传播仿真，结果如图 2、图 3所示。综上所述，本算法获得的节点传播效果均优于其它算法。

下面将整个网络中的节点，按群体对节点传播的影响力从小到大排序，其横坐标为节点序号的对数，纵坐标为群体对个体的影响力值。

如图4所示，对曲线分析可知，曲线的切线的斜率随着横坐标的增大而增大的更明显，网络整体对大部分节点传播的影响力很少，而对小部分节点传播了很大的影响力。通过这一研究分析，整个网络群体更多的将影响力，传播给了少数不足20%的节点。因此，只需要对GtF 算法中排序靠前的重要节点进行监控，便能了解一个群体影响力的作用程度。

4.2 随机网络仿真

在随机网络总进行群体对个体的影响力排序分析，结果如表3所示。

图1 Email网络105, 299号节点传播结果Fig.1 Email network 105, 299 node communication results

图3 Email网络196, 434号节点传播结果Fig.3 Email network 196, 434 node communication results

表3 随机网络本算法与经典K-shell算法排名前三节点Tab.3 Random network algorithm and classic k-shell algorithm rank the top three nodes

在随机网络中仿真结果如图5(a)(b)表明，在GtF算法中排名前三的节点1、2、3号传播效果均优于，在K-shell算法中排名前三的1、3、5号节。

图2 Email网络16, 389号节点传播结果Fig.2 Email network 16, 389 node communication results

图4 影响力值排序后分布情况Fig.4 Distribution after ranking of influence values

5 结论及未来工作

现如今社交网络的舆情已经从公众舆论的折射场转为了引发地、爆发场，成为网络舆情的重要阵地，对社会活动影响深远。社交网络的舆情又呈现出多样化和复杂性，能够准确地掌握和控制舆情在群体中的演化过程迫在眉睫，因此有必要针对群体对个体的行为特点和影响力的关联性进行研究，进一步理解和揭示影响力的作用机制和潜在的机理。本文提出了群体对个体影响力的计算方法，并建立了算法模型。进行了SI传播仿真分析，群体对个体影响力分布分析，结果表明本文提出的算法在传播仿真中表现优异，能够准确地找出重要的节点。希望能够在控制网络舆情传播、处理社会突发事件等方面，为决策者提供更全面、更准确的帮助。

图5 (a) 随机网络2, 3号节点传播结果Fig.5(a) Random network node 2, 3 transmission results

下一阶段的研究重点是在本文研究的基础之上，进一步分析研究群体对个体的影响是如何随时间而演化的。

[1] 赵旭剑, 张立, 李波, 等. 网络新闻话题演化模式挖掘[J].软件, 2015, 36(6): 1-6

[2] 王非. 基于微博的情感新词发现研究[J]. 软件, 2015,36(11): 06-08

[3] Hegselmann R, Krause U. Opinion Dynamics and Bounded Confidence Models, Analysis and Simulation[J]. Journal of Artificial Societies & Social Simulation, 2002, 5(3): 2.

[4] Li N N, Zhang N, Zhou T. Empirical analysis on temporal statistics of human correspondence patterns[J]. Physica A Statistical Mechanics & Its Applications, 2008, 387(25):6391-6394.

[5] Li Z, Tang X. From Global Polarization to Local Social Mechanisms: A Study Based on ABM and Empirical Data Analysis[M]. Springer Japan, 2015: 29-40.

[6] ZHU Li-ping, YUAN Jia-jin, Li Hong. The Influence of Emotional Valence and Intensity on Vocabulary Processing[J].Psychological Science, 2011, (02): 284-288(In Chinese)朱丽萍, 袁加锦, 李红. 情绪效价及强度对词汇加工的影响[J].心理科学, 2011, (02): 284-288.

图5 (b) 随机网络3, 5号节点传播结果Fig.5(b) Random network node 3, 5transmission results

[7] LIU Kai, ZHU Hengmin, LIU Jingxian, Lu Zifang. R esearch on Netizens Factors in Internet Public Opinion Spread.Journal of Intellige, 2014, (04): 102-104 ( In Chinese)刘凯,朱恒民, 刘静娴等. 互联网舆情传播中的网民作用因素研究[J]. 情报杂志, 2014, (04): 102-104.

[8] Verma G, Swami A, Chan K. The impact of competing zealots on opinion dynamics[J]. Physica A Statistical Mechanics& Its Applications, 2014, 395(4): 310-331.

[9] Portillo I G. Cooperative networks overcoming defectors by social influence[J]. Physica A Statistical Mechanics & Its Applications, 2014, 394(2): 198-210.

[10] 刘璇, 于双元. 非结构化P2P 网络基于马尔科夫链的搜索算法研究[J]. 软件, 2015, 36(3): 116-121

[11] Li Lei, Liu Ji. Empirical Analysis of Micro－blogger Behavior Clustering on Public Opinion Topics. Journal of Intellige, 2014, (03): 118-121 ( In Chinese)李磊, 刘继. 面向舆情主题的微博用户行为聚类实证分析[J]. 情报杂志,2014, (03): 118-121.

[12] Bonzom V, Gurau R, Rivasseau V. The Ising Model on Random Lattices in Arbitrary Dimensions[J]. Physics Letters B, 2011, 711(1): 88-96.

[13] Floriana G, Ramasco J J. Influence of Opinion Dynamics on the Evolution of Games[J]. Plos One, 2012, 7(11): e48916.

[14] 顾亦然, 王兵, 孟繁荣. 一种基于K-Shell的复杂网络重要节点发现算法[J]. 计算机技术与发展, 2015(9): 70-74.GU Yi-ran, Wang Bing, Meng Fan-rong. A algorithm to find important nodes based on K-shell[J] Computer Technology and Development, 2015 25(09) 70-7.