基于网络节点中心性的新闻重要性评价研究

曹开臣，陈明仁，张千明，蔡世民*，周 涛

(1. 西南电子技术研究所 成都 610036；2. 电子科技大学大数据研究中心 成都 611731)

国家级(或权威)报刊的头版新闻通常报道与国家政治、经济政策相关的重要信息。正确评价国家级报刊的新闻重要性对理解国家政策变化具有重要意义。如《人民日报》是中国共产党的机关报刊，也是中共中央向外界表达其观点的宣传工具。《人民日报》的头版新闻(第01 版要闻)在不同时期对我国政治、经济政策有着指导作用，甚至起到了改变中国发展历史的作用[1]。《人民日报》除了为外界提供中国共产党的政策及观点等直接信息外，其社论亦反映了中共中央对事件的处理意见，被外界作为分析我国政治、经济政策变化的重要渠道之一[2]。

在自然界中存在的大量复杂系统都可以通过不同的复杂网络加以描述[3]。一个典型的复杂网络是由许多节点与节点之间的连边组成，其中节点用来代表真实系统中不同的实体，而连边则用来表示实体间的关系[4]。如大脑神经系统可以看作大量神经细胞(或功能单元)通过神经纤维相互连接形成的神经网络[5]；电力系统可以看作不同的变压设备通过电缆相互连接形成的电力网络[6]；社会系统可以看作不同的人通过交互关系连接形成的社交网络[7]。类似地，新闻媒体(如《人民日报》)也可以通过其新闻(文章)的内容相似度形成新闻网络[8]。

在复杂网络研究领域，节点重要性可以用于识别社交网络中意见领袖[9]、科研人员的学术影响力[10]及新闻关键词提取[11]等等。网络节点中心性是对节点核心地位的定量刻画，以反映该节点在网络中的重要性[12-13]。本文通过对H 指数和PageRank 排序算法的深入分析，提出改进的PageRank 排序算法—H-PageRank。H-PageRank 排序算法保留了H 指数局部邻域内对大度节点的依赖，同时结合了PageRank 算法随机游走的全局性，是一种兼顾局部和全局中心性的节点排序算法。

本文以《人民日报》为例，抽取发表在1946-2008年期间的新闻，利用新闻内容相似性，基于表示学习构建新闻网络。在此基础上，基于H-PageRank排序算法对新闻网络进行节点重要性度量。以是否成为头版新闻作为新闻重要性评价准则，相比其他的网络节点中心性指标，H-PageRank 中心性能够更正确地评价新闻重要性，验证H-PageRank 排序算法的有效性。

1 H-PageRank 排序算法

H-PageRank 排序算法是通过引入H 指数，对PageRank 排序算法的改进。本章将重点阐述HPagerRank 排序算法的改进。

1.1 PageRank 排序算法

文献[14]提出了PageRank 排序算法，该算法针对新闻网络G=(V,E)中任意节点 vi，其初始 PR值的计算为：

式中，D(vj)表示节点 vj的度。考虑到 PR值的结果不应该为0，所以文献[14]将式(1)改写为：

式中， d为阻尼系数(通常取d=0.85) ；NG=|V|表示G的节点数量。经过迭代计算，节点 vi的 PR值会趋向于收敛状态。

PageRank 排序算法有一些显著的缺陷，首先在巨大网络中随机游走本就是一件极其复杂的过程，容易导致在实际计算过程中需要计算网络大小为几十万阶乃至上亿阶的矩阵的乘法，而超大矩阵的乘法在时间和空间上都难以负担[15]。在实际应用中，PageRank 排序算法是基于连接分析的，易受到直接连接的重要性较小的节点影响，不能对网络降噪之后再进行处理，导致它计算出来的搜索结果存在误差[16]。

为了解决上述问题，本文引入H 指数，使用支持H 指数贡献矩阵(support H-index contribution matrix, SHCM)改进PageRank 排序算法。

1.2 H 指数与H 中心性

H 指数是一个混合量化指标[17]。文献[18-19]将H 指数引入节点中心性度量。它们认为一个节点 vi的H 指数如果是H(vi)，说明这个节点有H(vi)个邻居，且它们的度都不小于H(vi)。文献[18]理论证明H 指数是一个很好的度量节点中心性的指标，可以简单、直观地反应网络结构特征和节点重要性。

另外，对于节点 vi的H 指数，H(vi)虽然反映了该节点在当前网络中的重要性，但是受网络规模影响，不便于进行网络间对比。为此，本文通过利用网络规模归一化H 指数，定义节点的H 中心性(HC)：

1.3 改进PageRank 排序算法

受到文献[18]启发，一个节点的H 指数一般要远小于其节点的度，所以针对一个点的H 指数，往往只与该节点的邻域中的少数大度节点有关。因此，本文定义SHCM 的元素 Bij满足：

式中， Aij为 G的邻接矩阵的元素； vi为目标节点，vj为 vi的邻居节点vj∈N(vi)； D(vj)为邻域中节点vj的度；H(vi)为目标节点 vi的H 指数。SHCM 描述对G过滤操作后的新闻网络GSHCM=(VSHCM,ESHCM)。对于G 中的节点 vi来说，它在GSHCM中只保留其邻域N(vi)中节点度最大的N(vi)个节点。通过这种方式，不再考虑 G中那些节点度相对较小的节点，从而较大程度地简化了 G的邻接矩阵，保证H-PageRank排序算法的高效计算。

H-PageRank 排序算法的详细流程如下。对于GSHCM中任意节点 vi，定义其HPR值为：

式中， d 为阻尼系数；NSHCM=|VSHCM|为GSHCM中节点数量(等同于新闻网络 G的 节点数量)；NSHCM(vi)为GSHCM中节点 vi的邻域；DSHCM(vj)为GSHCM中节点 vj的度。

GSHCM中所有节点的HPR值可以形成一个特征向量 HR：

同时，特征向量H R也是式(7)中方程组的稳定解，

式中，邻接函数l(vi,vj)代表在GSHCM中节点 vj在 vi邻域NSHCM(vi)中的节点总数中的比重。如果 vi和 vj不相邻，则l(vi,vj)=0。一般情况，对于任意节点 vi，其满足：

2 新闻重要性评价方法设计

在新闻重要性评价方法设计过程中，本文首先通过自然语言处理方法得到每条新闻的表示向量，利用每条新闻的表示向量计算它们的相似度性时。该过程面临高时间复杂度。本文采用局部敏感哈希算法实现新闻之间的相似性计算，进而得到刻画新闻网络的相似性矩阵。在此基础上，基于HPageRank 中心性对新闻网络中的节点进行排序，以是否成为头版新闻作为新闻重要性评价准则，通过全局排序与局部排序度量的实验结果验证Top-N 评价方法。图1 给出新闻重要性评价方法的具体工作流程。

图1 新闻重要性评价方法工作流程图

2.1 基于Doc2Vec 算法的新闻向量表示

词嵌入(word embedding)是一种将文本中的词转换成向量的方法[20]。本文将《人民日报》的所有新闻作为文本语料，采用Doc2Vec 算法[21]将新闻进行向量表示。Doc2Vec 算法同时训练词向量表示和新闻向量表示。设新闻i对应的one-hot 编码向量为 pi，新闻中词t对应的one-hot 编码向量为 wt。可以构建词t在文本i的和向量h(wt|pi)为如下形式：

式中， T为Doc2Vec 算法考虑的上下文词数。

进一步，将h(wt|pi)代入Doc2Vec 算法的神经网络模型中，可得到如下输出：

式中， W为Doc2Vec 算法的神经网络模型中的隐层；b 为偏置。

利用上述输出函数构建如下损失函数：

DIP出现以下情况不得使用：管子表面出现凹陷、裂缝、重皮、毛刺等铸造缺陷超出规范和设计要求；飞边清除后造成壁厚减薄超过壁厚允许值；承插口密封工作面有连续轴向沟纹；管内表面上任何凸起高度超过内衬厚度的1/2。

式中， D为向量间距离函数，本文采用二阶欧氏距离。通过优化式(11)，得到一个Wbest矩阵和bbest偏置。以新闻i对应的one-hot 向量 pi作为输入，可以得到其低维向量表征 Ri为如下形式：

2.2 局部敏感哈希算法

Doc2Vec 算法所得的新闻的表示向量，其维度仍然较高，同时本文实际探讨的新闻规模也是较大的，所以在遍历计算新闻之间的相似性具有较高的时间复杂度。为了解决该问题，本文基于局部敏感哈希(local sensitive Hash, LSH)的近似最近邻查找方法(简称LSH 算法)来计算新闻之间相似性[22]。

LSH 算法将n个准备计算相互之间相似性的新闻向量 Ri(i=1,2,···,n)分别与同一个稳定分布的正态分布的数列 α做向量点乘，得到的n个一维的点值，对于向量 Ri映射到其对应的一维点值的过程：

它利用一维点值的差异来近似高维空间的距离。在实际计算中，LSH 算法把原始向量分成K段，对每一段子向量进行一维点乘，且添加一个随机的噪音ε，以提高算法稳定性。如对于向量Ri的第k段子向量 ri,k的哈希值表示为：

因此，任意一个向量都有 K个哈希值。LSH 算法假设，对任意一对向量 Ri和 Rj，如果存在任意一段子向量对的哈希值相同，即hα,ε(ri,k)=hα,ε(rj,k)(k=1,2,···,K)，则该对向量相似，标记为si,j=1，否则si,j=0[22]。

2.3 基于H-PageRank 中心性的评价方法

通过Doc2vec 算法和LSH 算法，可以高效地获取与节点 vi相似的节点集合，从而快速构建新闻网络。在此基础上，本文基于H-PageRank 中心性(HPR)对新闻网络中节点进行排序。通过节点排序序列，构建Top-N 评价方法( N是截取节点排序序列的列表长度)[23]。以是否成为头版新闻作为新闻重要性评价准则，本文通过调节 N实现全局排序和局部排序的度量(详见3.1 节实验设计)，设计基于H-PageRank 中心性的Top-N 评价方法。本文将HPageRank 中心性与其他的中心性指标，如PageRank中心性(PR)、LeaderRank 中心性(LR)[24]、度中心性(DC)[25]、H 中心性、接近中心性(CC)[26]及特征向量中心性(EC)[27]进行对比研究，进一步验证了H-PageRank 排序算法与基于网络节点中心性的Top-N 评价方法的有效性。

3 实验结果与分析

3.1 实验设计

在处理数据的过程中，本文考虑到不同领导核心执政时期《人民日报》的新闻风格与新闻版面差异性，将原始数据按照执政时间划分为4 个时代，形成对应的4 个子数据集，每一个子数据集的时间划分和新闻数量等描述如表1 所示。

表1 各个时代的子数据集属性信息

为了验证H-PageRank 排序算法与基于网络节点中心性的新闻重要性评价方法，本文引入4 个准确性评价指标：AUC 指标用于全局排序( N等于新闻网络规模)条件下度量Top-N 评价方法；正确率(precision)、召回率(recall)和F1 指标(F1-score)用于局部排序(N 显著小于新闻网络规模)条件下度量Top-N 评价方法。AUC 指标可以通过排序算法产生的全局排序列表中头版新闻的平均排序分(rank score)近似估算[27]。正确率定义排序列表中头版新闻与所有新闻的比例；召回率(recall)定义排序列表中头版新闻与数据集中所有头版新闻的比例；F1 指标(F1-score)定义准确率召回率的调和结果[28]。

3.2 实验结果

本文将《人民日报》的新闻划分为4 个时代，对每一个时代构建其新闻网络(对应4 个数据子集)，在此基础上利用头版新闻作为新闻重要性评价准则，验证基于多种网络节点中心性的Top-N评价方法。因此，本文对实验结果的论述主要分为两部分：1) 新闻网络实证研究；2) 基于Top-N 评价方法的新闻重要性评价研究。

3.2.1 新闻网络实证研究

通过上述LSH 算法，可以高效地计算得到新闻(二元)相似性矩阵。值得注意的是，LSH 算法过滤了相似性较低的新闻，使得新闻相似性矩阵中存在值全为0 的行或列。这些值全为0 的行或列对应新闻网络中的孤立节点。本小节对形成的新闻网络进行实证研究。表2 给出了去除掉孤立节点后，4 个新闻网络的拓扑结构特征。它的基本统计参量包括节点数、边数、连通分支数、最大连通分支(包括相对于新闻网络节点的比例)、平均度、聚类系数和同配系数。实验结果表明：1) 新闻网络存在较多的孤立节点(即是新闻网络节点数远小于新闻数)与较多的连通分支，但是最大连通分支相对于新网络节点的比例较大；2) 新闻网络具有较高的平均度、高聚集特性和和同配特性。

表2 各个时代的新闻网络拓扑属性

同时，通过实证分析新闻网络，从时代1～时代4 表示头版新闻的节点数与新闻网络节点数之比依次是18.98%、12.11%、10.73%、8.76%，以及分析4 个新闻网络的度分布p(k)。如图2 所示，4 个新闻网络的度分布都具有出无标度特性(即是近似幂律分布)，表现出复杂网络的一般特性。

图2 新闻网络度分布

3.2.2 新闻重要性评价研究

基于新闻网络的邻接矩阵，分别计算网络中各节点的H-PageRank 中心性、PageRank 中心性、LeaderRank 中心性、度中心、H 中心性、接近中心性及特征向量中心性，形成基于不同网络节点中心性的节点排序序列。在此基础上，利用不同排序列表长度条件下的Top-N 评价方法，对比分析H-PageRank排序算法与基于其他的网络节点中心性的新闻重要性评价的有效性。

首先，针对每一个新闻网络，本文基于7 种网络节点中心性对其节点进行全局排序，通过全局排序列表条件下Top-N 评价方法计算头版新闻的平均排序分估算出对应的AUC 值。图3a 给出不同网络节点中心性计算得到的AUC 值。对于每一个新闻网络，7 种网络节点中心性给出非常相近的AUC 值，表明它们对新闻网络全局排序的相近性，但是AUC 值都显著高于随机排序理论值0.5，表明它们对新闻网络进行全局排序的有效性。值得注意的是，对于每一个新闻网络，基于HPR 和HR 的AUC 值对阻尼系数 d都有很高的鲁棒性，因此本文选取最优AUC 值对应的阻尼系数，d=0.9。

图3 基于7 种网络节点中心性的Top-N评价方法的正确性对比

进一步，为了能够区分7 种网络节点中心性对新闻重要性评价的影响力，本文通过局部排序条件下Top-N (N=20)评价方法，计算头版新闻的(预测)正确率(图3b)、召回率(图3c)和F1 指标(图3d)。对比分析实验结果，可以发现基于H-PageRank 中心性Top-20 评价方法在3 个正确性评价指标上表现出较好的性能(除了时代4 的新闻网络)。具体而言，H-PageRank 中心性对应的评价指标平均值相比于PageRank 中心性、Leaderrank 中心性、度中心性、H 中心性、接近中心性及特征向量中心性，从正确率角度分别提高18.8%、58.5%、12.9%、70.3%、25.0%及45.8%；从召回率角度分别提高18.6%、58.7%、12.9%、70.2%、24.9%及45.8%；从F1 指标角度分别提高18.7%、58.6%、12.9%、70.3%、25.1%及45.8%。这些实验结果表明基于H-PageRank 中心性的新闻重要性评价更优，验证了H-PageRank 排序算法的有效性。

通过图3 实验结果的对比分析，可以得出3 个正确性指标给出H-PageRank 中心性相比于其他网络节点中心性的相似结果，所以本文从正确率角度对比分析不同局部排序列表长度条对基于7 种网络节点中心性的Top-N 评价方法的影响。图4 给出不同局部排序列表长度对Top-N 评价方法的实验结果，虚线对应的理论基准(即是头版新闻占比)。依据不同时代的新闻网络。

图4 不同局部排序列表长度条件下基于7 种中心性的Top-N 评价方法的性能对比分析

时代1 的新闻网络如图4a 所示。H-PageRank中心性和PageRank 中心性对Top-N 评价方法影响最大，基于这两类中心性的正确率要显著高于其他4 类中心性。特别是，基于H-PageRank 中心性的Top-N 评价方法，其正确率受局部排序列表长度影响较小，且相比于理论基准有极大的提高，比如Top-10 评价方法的正确率可达4.5 倍。

时代2 的新闻网络如图4b 所示。基于特征向量中心性的Top-N 评价方法，在不同局部排序列表长度条件下的平均正确率最高，且相比于理论基准有极大的提高，如Top-10 评价方法的正确率可达3.9 倍。

时代3 的新闻网络如图4c 所示。与时代1的实验结果相类似，H-PageRank 中心性和Page-Rank 中心性显著优于其他4 类中心性。但是，局部排序列表长度对基于H-PageRank 中心性和Page-Rank 中心性的Top-N 评价方法影响较明显。同时，对于基于H-PageRank 中心性和Page-Rank 中心性的Top-N 评价方法，其Top-10 评价方法的正确率相比于理论基准可达5 倍。

时代4 的新闻网络如图4d 所示。基于H 中心性的Top-N 评价方法，在不同局部列表长度条件下的平均正确率最高，且相比于理论基准有显著的提高，如Top-10 评价方法的正确率可达4 倍。

值得注意的是，如果局部排序列表长度过小，样本数目过少会使实验结果有较大的误差，反之，如果推荐列表长度继续加大，基于不同网络节点中心性的实验结果的差异变小，且会逐渐趋向于理论基准。但是，对于有限的局部排序列表长度条件下，基于7 种网络节点中心性的Top-N 评价方法的正确率都优于理论基准。特别是，当选取的局部排序列表长度N=20 时，在4 个时代的新闻网络上，基于H-PageRank 中心性的评价方法的最优正确率相比于理论基准，分别提高391.9%、249.7%、345.5%和98.2%。综上所述，实验结果表明基于7 种网络节点中心性的Top-N 评价方法对于有限的局部排序列表长度的鲁棒性。

4 结 束 语

本文以《人民日报》为例，从复杂网络视角研究新闻网络，利用新闻网络节点中心性，构建Top-N 评价方法。在此基础上，以是否成为头版新闻作为新闻重要性评价准则，比较不同网络节点中心性指标的表现。在横向比较各类中心性排序算法对评价新闻重要性的影响时，尽管7 种网络节点中心性指标在全局排序条件下表现出相近的AUC值，但是Top-20 评价方法的平均正确率、平均召回率及平均 F1值都表明H-PageRank 排序算法要明显优于其他6 种中心性排序算法。基于此，本文认为提出的H-PageRank 算法是有效且高效的。