于 凯 白西柯 郭煜婕

(1.新疆财经大学公共管理学院 乌鲁木齐 830012；2.新疆财经大学信息管理学院 乌鲁木齐 830012)

0 引 言

识别负面舆情信息源点是一项重要且具有挑战性的任务。近年来，关于舆情传播[1]、计算机病毒传播[2]、谣言传播[3]等问题已严重扰乱社会秩序，由于舆情信息的快速传播和社交网络的动态演变，如何快速、准确追溯负面信息来源并对传播源进行引导和控制是抑制负面舆情传播、精准治理负面舆情的最有效方法之一。

当前，舆情信息大多依赖于社交网络的传播，首先，社交网络上的个体接收到舆情信息的表现不同，个体状态的不断转化形成的复杂关系对舆情信息源点追溯问题带来了新的挑战。其次，在舆情信息传播过程中，通常无法对个体状态集进行完整的观察，只能观察到网络中被舆情信息所传播感染的有限节点状态。最后，舆情传播的线上网络构建是一项艰难的工作，舆情信息传播源点追溯与治理是当前研究的热点亦是需要亟待解决的问题。将舆情治理于源头对推进国家治理体系和治理能力现代化的实现具有重要的理论意义，对深入认识上述问题并得到相应的管理启示具有重要的现实意义。

1 舆情信息溯源问题

图1 舆情信息溯源问题示意图

当前关于源点追溯的研究主要基于以下三种观测类型[9]展开：完全观测、局部观测(快照观测)和监测器观测。完全观测和监测器观测由于存在诸多缺陷，当前研究多采用快照观测——从快照信息出发，利用部分节点的信息，结合相关的技术和算法进行源点追溯，本文亦采取快照观测。。

2 研究现状

目前，源点追溯问题已在多个研究领域展开，但在溯源准确率、溯源错误距离上有进一步改进的空间。因此，本文在已有研究基础之上引入多中心性算法，旨在提升溯源准确率，降低溯源错误距离，这也是研究该问题的主要出发点。

2.1单源追溯Shah等[10]首次系统研究了网络中的信息源点追溯问题，作为单一来源的最大似然估计，假设每个节点只能从它的一个邻居那里接收信息，并在树状网络上研究该问题，将正则树的最大似然估计定义为新的网络中心性——谣言中心性，总结出信息传播扩散遵循的一般系统集成模型——SI模型。Shen等[11]开发了一种时间反向扩散算法来有效追溯扩散源，采用舆情传播动力学过程对算法进行检验，将其应用于H1N1大流感，并给出源点追溯问题的通用条件。

2.2多源追溯Luo等[12]根据Shah[10]的思想将单源定位扩展到多源定位，提出了一种多源估计和社团划分的算法，通过将感染图划分为几个不相交的网络区域，每个区域对应一个源。Cesar等[9]基于计算采样网络上的节点中心性——度中心性、介数中心性、接近中心性和特征向量中心性，提出并验证了一种基于无偏介数中心性的溯源算法，表明源节点往往具有最高的测量值，Zang等[13]将该算法推广到了多源场景。Fioriti等[14]根据感染子图中某个节点移除前后最大特征值的差值提出动态年龄算法(DA)，表明最大特征值差异越大的节点越有可能成为源节点，并以此来识别疾病爆发的多个来源。Prakash等[15]以SI模型作为疾病传播载体模型，提出最小描述长度算法(MDL)来识别传播源，进一步通过贪婪算法优化传播源的描述长度来精准识别传播源。

2.3中心性指标中心性指标[16]是社交网络中衡量网络节点重要性的首要方法。Freeman[17]基于Sabidussi[18]的工作对经典的中心性指标——度中心性，介数中心性、接近中心性和特征向量中心性进行了广泛的讨论。近年来，越来越多的学者[19]将中心性指标引入源点追溯问题中，通过启发式算法更加准确的对舆情、谣言、疾病等信息源进行追溯定位。

基于以上分析，我们不难发现，当前已有学者从不同的角度出发，对舆情、谣言、疾病等源点追溯问题展开了深入研究。但现有算法在溯源准确率、误差距离等方面存在较大的改进空间。鉴于此，本文提出一种基于两阶段的多中心性舆情信息传播源点追溯算法，旨在提高舆情信息源点追溯的准确率，以期更加准确的追溯目标源节点，为政府等公共管理部门提供关于舆情信息源点追溯问题的依据。

3 多中心性算法

3.1算法描述在2.3的启发下，借鉴文献[20]中的基本思想，引入基于多中心性的舆情信息源点追溯算法，该算法分两个阶段进行：第一阶段，以SI模型为舆情传播载体模型在不同数据集上模拟舆情信息传播过程，并设置舆情传播感染规模，当传播规模达到预设阈值时，舆情传播停止，以此生成对应的舆情感染子图，结合表1中的5种中心性指标筛选出目标源节点的候选节点；第二阶段，利用5种中心性指标对目标源节点的候选节点进行二次筛选，即有效组合5种中心性指标来构建多中心性算法，进一步通过大量实验找出溯源效果最好的多中心性算法以此来精准追溯舆情信息传播源点，并针对性的对舆情传播源点进行引导和控制，真正实现将舆情治理于源头之处。5种中心性指标如表1所示。

表1 5种中心性指标

3.2多中心性算法公式性表达多中心性算法(Multicentricity Algorithm，MCA)就是适当选取目标网络中的单一中心性指标，将中心性指标进行有效组合，具体的表达式如式(1)所示：

(1)

MCA(DC)=f[D(i),C(i)]=f[C(i)|D(i)]

(2)

MCA(EC)=f[E(i),C(i)]=f[C(i)|E(i)]

(3)

其中，MCA(DC) 是度中心性和接近中心性的混合函数，即首先根据度中心性筛选出目标源点的候选节点，再根据接近中心性在目标源点的候选节点中进行二次筛选，对两种中心性指标进行有效组合，以此更加准确的定位目标源点。MCA(EC)具体含义同上。

3.3多中心性算法的性能利用R软件分别以随机图(Random)、正则图(Regular)为基础网络构建舆情传播网络，两个网络均包含5 000个节点。首先，以SI模型为舆情信息传播载体模型，在随机图与正则图上随机选择一个节点作为舆情传播源点，初步设定舆情传播感染规模为20%～30%，当舆情传播感染规模达到预设值时舆情传播停止，并生成对应的舆情传播感染子图；其次，选择式(2)和式(3)的多中心性算法，分别为DC、EC，在舆情传播感染子图中进行100次舆情信息源点追溯实验；最后，给出多中心性算法与单一中心性算法的溯源错误距离(目标源节点与各算法追溯源节点之间的距离)、溯源平均错误距离、溯源准确率，具体结果如图2所示。

图2 多中心性与单一中心性算法的溯源错误距离、平均错误距离及准确率对比

由图2(a)、2(c)、2(e)可知，100次实验中不同中心性算法在随机图上的溯源错误距离存在较大差距，其中EC算法表现最好，溯源错误距离为0(即准确溯源)的频数高达98次，离心率中心性表现次之(95次)，特征向量中心性溯源错误距离为1步时的频数为41次；在溯源平均错误距离上，EC的溯源平均错误距离为0.02步，表现最佳，离心率中心性的溯源平均错误距离为0.05步，度中心性、接近中心性、介数中心性和DC算法表现相当，溯源平均错误距离在2步左右，表现较差；此外，在溯源准确率上EC算法的表现也是最佳。

由图2(b)、2(d)、2(f)可知，离心率中心性与EC算法在正则图上的溯源表现较好，溯源平均错误距离均小于1步，分别为0.41步，0.50步，且溯源准确率分别高达65%，61%，显著优于其他中心性算法。而度中心性表现最差，溯源准确率仅有2%，介数中心性溯源准确率为11%，接近中心性与DC算法溯源准确率在20%左右，效果不太理想。

综合来看，EC算法在舆情信息溯源问题上的表现最佳。

3.4多中心性算法与经典算法的溯源表现对比为了将EC算法与经典溯源算法的溯源表现进行对比，分别将EC算法、DA算法、MDL算法在随机图和正则图上的表现作出如下对比实验，实验过程与3.3相同，舆情传播感染规模为20%～30%，3种算法在随机图与正则图上的溯源准确率、溯源错误距离对比情况如图3所示。

图3 3种算法在随机图与正则图上的溯源准确率、错误距离对比

由图3(a)可知，在随机图和正则图上，EC算法在溯源准确率、溯源错误距离上均优于MDL算法与DA算法。3种算法在随机图上的溯源准确率分别为98%、0%、59%，在正则图上的溯源准确率分别为61%、32%、21%。由图3(b)、3(c)可知，3种算法在随机图和正则图上的溯源错误距离分布情况存在较大差异，在随机图上，100次实验中EC算法的溯源错误距离在0步的频次高达98次，而DA算法的溯源错误距离在1—2步时仍有较多频次，MDL表现最差，错误距离在4步的频次高达50次；在正则图上，EC算法的溯源错误距离分布情况仍优于其他两种算法。

3.5算法有效性验证此外，为了验证EC算法的有效性，将3种算法在真实网络—美国电网[22]上的溯源表现作出如下对比实验，该网络是一个无向、无权的网络，网络数据由4941个节点和6594条边组成。实验中生成3组大小不同的舆情感染规模，具体过程同上，3种算法在美国电网上的溯源平均错误距离和溯源错误距离分布情况如图4所示。

图4 3种算法在美国电力网上的溯源平均错误距离及溯源错误距离分布对比

由图4(a)可知，当舆情传播规模为5%～10%时，EC算法、DA算法、MDL算法的溯源平均错误距离分别为4.48步、5.92步、6.15步；当舆情传播规模为30%～40%时，3种算法的溯源平均错误距离分别为7.2步、13.06步、10.38步；当舆情传播规模为40%～60%时，3种算法的溯源平均错误距离分别为8步、14.82步、10.11步，可以发现无论舆情感染规模大小如何，EC算法的溯源平均错误距离都低于其他两种算法。由图4(b)可知，在舆情传播规模为5%～10%的时候，3种算法在100次实验中溯源错误距离出现在4～7步的频次最多，但EC算法溯源错误距离主要集中在0～3步和4～7步，其他两种算法却有较大频次出现在8～11步。此外，由图4(b)、4(c)、4(d)可知，随着舆情感染规模的增加，3种算法的溯源错误距离分布情况均逐渐后移，但EC算法的错误距离分布情况仍优于其他两种算法。

综上所述，EC算法在舆情信息源点追溯问题上有着较好的表现，溯源平均错误距离较低且溯源准确率高，在溯源性能上优于单一中心性算法、MDL算法和DA算法，舆情信息传播网络无论是合成网络(随机图、正则图)还是真实网络(美国电网)，该算法均可以很好地利用网络数据集的结构特征，溯源准确率较高，且溯源错误距离较低。

4 舆情溯源准确率影响因素

此外，网络结构、舆情传播规模可能是影响溯源准确率的潜在因素。为了探究影响舆情溯源准确率的因素，首先在随机图和正则图上生成3组不同规模大小的舆情传播感染子图，当舆情传播感染规模达到预设规模时，舆情传播停止并标记对应规模，如表2所示。其次，将EC算法与经典算法在不同网络结构、不同舆情传播规模上进行溯源实验，实验结果如图5、图6、图7所示(横向对比与纵向对比)。最后，通过实验结果分析影响舆情溯源准确率、溯源错误距离的因素。

表2 不同网络结构上的舆情传播规模设置

由图5可知，不同网络结构对舆情溯源准确率有着显著的影响，无论感染规模大小如何，EC算法在随机图与正则图上的溯源准确率显著优于DA算法与MDL算法，进一步表明了EC算法的优势。

由图6、图7可知，在两种网络结构中，一般来讲，随着舆情传播规模的增加，100次实验中溯源错误距离出现在0步(准确定位)的频次逐渐减少，通过横向对比3种算法的溯源错误距离可知，EC算法在溯源错误距离上的表现优于其他两种算法，DA算法表现次之，MDL算法表现最差。因此，精准把握舆情传播网络结构，运用适当的溯源算法准确定位舆情传播源头，及时进行有效疏导和控制，防止舆情规模扩大，从源头实现网络舆情高效治理。

图6 不同算法在随机图上的溯源错误距离

图7 不同算法在正则图上的溯源错误距离

5 总 结

本文提出了基于两阶段的多中心性算法(EC)，对舆情信息源点追溯问题进行了深度剖析，以SI模型为载体模型模拟舆情信息在随机图与正则图上的传播过程，在生成的感染子图上分别进行溯源实验，并与经典溯源算法进行对比，进一步在美国电网上验证了该算法的有效性，无论是在溯源准确率还是错误距离上，该算法都显现出较大的优势。一般来讲，随着舆情传播规模的增加，溯源准确率会呈现逐渐下降的趋势，且舆情传播规模越大，溯源效果越差。此外，算法的溯源准确率与网络结构有着密切的关系，对网络结构进行深入分析有助于提高溯源准确率。综上，舆情治理的方向应以源头治理为主导，利用相关技术和算法准确定位舆情源点，并对舆情源点进行积极的引导和控制，将源点治理作为网络舆情高效治理的重点。

目前研究仍存在一定的不足，如未考虑加权有向网络、网络稀疏性、存在多源等问题对于多中心性算法溯源准确率的影响，以上问题还需进一步研究和探讨。