基于網(wǎng)絡節(jié)點中心性的新聞重要性評價研究

曹開臣，陳明仁，張千明，蔡世民*，周 濤

(1. 西南電子技術研究所 成都 610036；2. 電子科技大學大數(shù)據(jù)研究中心 成都 611731)

國家級(或權威)報刊的頭版新聞通常報道與國家政治、經濟政策相關的重要信息。正確評價國家級報刊的新聞重要性對理解國家政策變化具有重要意義。如《人民日報》是中國共產黨的機關報刊，也是中共中央向外界表達其觀點的宣傳工具。《人民日報》的頭版新聞(第01 版要聞)在不同時期對我國政治、經濟政策有著指導作用，甚至起到了改變中國發(fā)展歷史的作用[1]。《人民日報》除了為外界提供中國共產黨的政策及觀點等直接信息外，其社論亦反映了中共中央對事件的處理意見，被外界作為分析我國政治、經濟政策變化的重要渠道之一[2]。

在自然界中存在的大量復雜系統(tǒng)都可以通過不同的復雜網(wǎng)絡加以描述[3]。一個典型的復雜網(wǎng)絡是由許多節(jié)點與節(jié)點之間的連邊組成，其中節(jié)點用來代表真實系統(tǒng)中不同的實體，而連邊則用來表示實體間的關系[4]。如大腦神經系統(tǒng)可以看作大量神經細胞(或功能單元)通過神經纖維相互連接形成的神經網(wǎng)絡[5]；電力系統(tǒng)可以看作不同的變壓設備通過電纜相互連接形成的電力網(wǎng)絡[6]；社會系統(tǒng)可以看作不同的人通過交互關系連接形成的社交網(wǎng)絡[7]。類似地，新聞媒體(如《人民日報》)也可以通過其新聞(文章)的內容相似度形成新聞網(wǎng)絡[8]。

在復雜網(wǎng)絡研究領域，節(jié)點重要性可以用于識別社交網(wǎng)絡中意見領袖[9]、科研人員的學術影響力[10]及新聞關鍵詞提取[11]等等。網(wǎng)絡節(jié)點中心性是對節(jié)點核心地位的定量刻畫，以反映該節(jié)點在網(wǎng)絡中的重要性[12-13]。本文通過對H 指數(shù)和PageRank 排序算法的深入分析，提出改進的PageRank 排序算法—H-PageRank。H-PageRank 排序算法保留了H 指數(shù)局部鄰域內對大度節(jié)點的依賴，同時結合了PageRank 算法隨機游走的全局性，是一種兼顧局部和全局中心性的節(jié)點排序算法。

本文以《人民日報》為例，抽取發(fā)表在1946-2008年期間的新聞，利用新聞內容相似性，基于表示學習構建新聞網(wǎng)絡。在此基礎上，基于H-PageRank排序算法對新聞網(wǎng)絡進行節(jié)點重要性度量。以是否成為頭版新聞作為新聞重要性評價準則，相比其他的網(wǎng)絡節(jié)點中心性指標，H-PageRank 中心性能夠更正確地評價新聞重要性，驗證H-PageRank 排序算法的有效性。

1 H-PageRank 排序算法

H-PageRank 排序算法是通過引入H 指數(shù)，對PageRank 排序算法的改進。本章將重點闡述HPagerRank 排序算法的改進。

1.1 PageRank 排序算法

文獻[14]提出了PageRank 排序算法，該算法針對新聞網(wǎng)絡G=(V,E)中任意節(jié)點 vi，其初始 PR值的計算為：

式中，D(vj)表示節(jié)點 vj的度。考慮到 PR值的結果不應該為0，所以文獻[14]將式(1)改寫為：

式中， d為阻尼系數(shù)(通常取d=0.85) ；NG=|V|表示G的節(jié)點數(shù)量。經過迭代計算，節(jié)點 vi的 PR值會趨向于收斂狀態(tài)。

PageRank 排序算法有一些顯著的缺陷，首先在巨大網(wǎng)絡中隨機游走本就是一件極其復雜的過程，容易導致在實際計算過程中需要計算網(wǎng)絡大小為幾十萬階乃至上億階的矩陣的乘法，而超大矩陣的乘法在時間和空間上都難以負擔[15]。在實際應用中，PageRank 排序算法是基于連接分析的，易受到直接連接的重要性較小的節(jié)點影響，不能對網(wǎng)絡降噪之后再進行處理，導致它計算出來的搜索結果存在誤差[16]。

為了解決上述問題，本文引入H 指數(shù)，使用支持H 指數(shù)貢獻矩陣(support H-index contribution matrix, SHCM)改進PageRank 排序算法。

1.2 H 指數(shù)與H 中心性

H 指數(shù)是一個混合量化指標[17]。文獻[18-19]將H 指數(shù)引入節(jié)點中心性度量。它們認為一個節(jié)點 vi的H 指數(shù)如果是H(vi)，說明這個節(jié)點有H(vi)個鄰居，且它們的度都不小于H(vi)。文獻[18]理論證明H 指數(shù)是一個很好的度量節(jié)點中心性的指標，可以簡單、直觀地反應網(wǎng)絡結構特征和節(jié)點重要性。

另外，對于節(jié)點 vi的H 指數(shù)，H(vi)雖然反映了該節(jié)點在當前網(wǎng)絡中的重要性，但是受網(wǎng)絡規(guī)模影響，不便于進行網(wǎng)絡間對比。為此，本文通過利用網(wǎng)絡規(guī)模歸一化H 指數(shù)，定義節(jié)點的H 中心性(HC)：

1.3 改進PageRank 排序算法

受到文獻[18]啟發(fā)，一個節(jié)點的H 指數(shù)一般要遠小于其節(jié)點的度，所以針對一個點的H 指數(shù)，往往只與該節(jié)點的鄰域中的少數(shù)大度節(jié)點有關。因此，本文定義SHCM 的元素 Bij滿足：

式中， Aij為 G的鄰接矩陣的元素； vi為目標節(jié)點，vj為 vi的鄰居節(jié)點vj∈N(vi)； D(vj)為鄰域中節(jié)點vj的度；H(vi)為目標節(jié)點 vi的H 指數(shù)。SHCM 描述對G過濾操作后的新聞網(wǎng)絡GSHCM=(VSHCM,ESHCM)。對于G 中的節(jié)點 vi來說，它在GSHCM中只保留其鄰域N(vi)中節(jié)點度最大的N(vi)個節(jié)點。通過這種方式，不再考慮 G中那些節(jié)點度相對較小的節(jié)點，從而較大程度地簡化了 G的鄰接矩陣，保證H-PageRank排序算法的高效計算。

H-PageRank 排序算法的詳細流程如下。對于GSHCM中任意節(jié)點 vi，定義其HPR值為：

式中， d 為阻尼系數(shù)；NSHCM=|VSHCM|為GSHCM中節(jié)點數(shù)量(等同于新聞網(wǎng)絡 G的 節(jié)點數(shù)量)；NSHCM(vi)為GSHCM中節(jié)點 vi的鄰域；DSHCM(vj)為GSHCM中節(jié)點 vj的度。

GSHCM中所有節(jié)點的HPR值可以形成一個特征向量 HR：

同時，特征向量H R也是式(7)中方程組的穩(wěn)定解，

式中，鄰接函數(shù)l(vi,vj)代表在GSHCM中節(jié)點 vj在 vi鄰域NSHCM(vi)中的節(jié)點總數(shù)中的比重。如果 vi和 vj不相鄰，則l(vi,vj)=0。一般情況，對于任意節(jié)點 vi，其滿足：

2 新聞重要性評價方法設計

在新聞重要性評價方法設計過程中，本文首先通過自然語言處理方法得到每條新聞的表示向量，利用每條新聞的表示向量計算它們的相似度性時。該過程面臨高時間復雜度。本文采用局部敏感哈希算法實現(xiàn)新聞之間的相似性計算，進而得到刻畫新聞網(wǎng)絡的相似性矩陣。在此基礎上，基于HPageRank 中心性對新聞網(wǎng)絡中的節(jié)點進行排序，以是否成為頭版新聞作為新聞重要性評價準則，通過全局排序與局部排序度量的實驗結果驗證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 算法考慮的上下文詞數(shù)。

進一步，將h(wt|pi)代入Doc2Vec 算法的神經網(wǎng)絡模型中，可得到如下輸出：

式中， W為Doc2Vec 算法的神經網(wǎng)絡模型中的隱層；b 為偏置。

利用上述輸出函數(shù)構建如下?lián)p失函數(shù)：

DIP出現(xiàn)以下情況不得使用：管子表面出現(xiàn)凹陷、裂縫、重皮、毛刺等鑄造缺陷超出規(guī)范和設計要求；飛邊清除后造成壁厚減薄超過壁厚允許值；承插口密封工作面有連續(xù)軸向溝紋；管內表面上任何凸起高度超過內襯厚度的1/2。

式中， D為向量間距離函數(shù)，本文采用二階歐氏距離。通過優(yōu)化式(11)，得到一個Wbest矩陣和bbest偏置。以新聞i對應的one-hot 向量 pi作為輸入，可以得到其低維向量表征 Ri為如下形式：

2.2 局部敏感哈希算法

Doc2Vec 算法所得的新聞的表示向量，其維度仍然較高，同時本文實際探討的新聞規(guī)模也是較大的，所以在遍歷計算新聞之間的相似性具有較高的時間復雜度。為了解決該問題，本文基于局部敏感哈希(local sensitive Hash, LSH)的近似最近鄰查找方法(簡稱LSH 算法)來計算新聞之間相似性[22]。

LSH 算法將n個準備計算相互之間相似性的新聞向量 Ri(i=1,2,···,n)分別與同一個穩(wěn)定分布的正態(tài)分布的數(shù)列 α做向量點乘，得到的n個一維的點值，對于向量 Ri映射到其對應的一維點值的過程：

它利用一維點值的差異來近似高維空間的距離。在實際計算中，LSH 算法把原始向量分成K段，對每一段子向量進行一維點乘，且添加一個隨機的噪音ε，以提高算法穩(wěn)定性。如對于向量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 算法，可以高效地獲取與節(jié)點 vi相似的節(jié)點集合，從而快速構建新聞網(wǎng)絡。在此基礎上，本文基于H-PageRank 中心性(HPR)對新聞網(wǎng)絡中節(jié)點進行排序。通過節(jié)點排序序列，構建Top-N 評價方法( N是截取節(jié)點排序序列的列表長度)[23]。以是否成為頭版新聞作為新聞重要性評價準則，本文通過調節(jié) N實現(xiàn)全局排序和局部排序的度量(詳見3.1 節(jié)實驗設計)，設計基于H-PageRank 中心性的Top-N 評價方法。本文將HPageRank 中心性與其他的中心性指標，如PageRank中心性(PR)、LeaderRank 中心性(LR)[24]、度中心性(DC)[25]、H 中心性、接近中心性(CC)[26]及特征向量中心性(EC)[27]進行對比研究，進一步驗證了H-PageRank 排序算法與基于網(wǎng)絡節(jié)點中心性的Top-N 評價方法的有效性。

3 實驗結果與分析

3.1 實驗設計

在處理數(shù)據(jù)的過程中，本文考慮到不同領導核心執(zhí)政時期《人民日報》的新聞風格與新聞版面差異性，將原始數(shù)據(jù)按照執(zhí)政時間劃分為4 個時代，形成對應的4 個子數(shù)據(jù)集，每一個子數(shù)據(jù)集的時間劃分和新聞數(shù)量等描述如表1 所示。

表1 各個時代的子數(shù)據(jù)集屬性信息

為了驗證H-PageRank 排序算法與基于網(wǎng)絡節(jié)點中心性的新聞重要性評價方法，本文引入4 個準確性評價指標：AUC 指標用于全局排序( N等于新聞網(wǎng)絡規(guī)模)條件下度量Top-N 評價方法；正確率(precision)、召回率(recall)和F1 指標(F1-score)用于局部排序(N 顯著小于新聞網(wǎng)絡規(guī)模)條件下度量Top-N 評價方法。AUC 指標可以通過排序算法產生的全局排序列表中頭版新聞的平均排序分(rank score)近似估算[27]。正確率定義排序列表中頭版新聞與所有新聞的比例；召回率(recall)定義排序列表中頭版新聞與數(shù)據(jù)集中所有頭版新聞的比例；F1 指標(F1-score)定義準確率召回率的調和結果[28]。

3.2 實驗結果

本文將《人民日報》的新聞劃分為4 個時代，對每一個時代構建其新聞網(wǎng)絡(對應4 個數(shù)據(jù)子集)，在此基礎上利用頭版新聞作為新聞重要性評價準則，驗證基于多種網(wǎng)絡節(jié)點中心性的Top-N評價方法。因此，本文對實驗結果的論述主要分為兩部分：1) 新聞網(wǎng)絡實證研究；2) 基于Top-N 評價方法的新聞重要性評價研究。

3.2.1 新聞網(wǎng)絡實證研究

通過上述LSH 算法，可以高效地計算得到新聞(二元)相似性矩陣。值得注意的是，LSH 算法過濾了相似性較低的新聞，使得新聞相似性矩陣中存在值全為0 的行或列。這些值全為0 的行或列對應新聞網(wǎng)絡中的孤立節(jié)點。本小節(jié)對形成的新聞網(wǎng)絡進行實證研究。表2 給出了去除掉孤立節(jié)點后，4 個新聞網(wǎng)絡的拓撲結構特征。它的基本統(tǒng)計參量包括節(jié)點數(shù)、邊數(shù)、連通分支數(shù)、最大連通分支(包括相對于新聞網(wǎng)絡節(jié)點的比例)、平均度、聚類系數(shù)和同配系數(shù)。實驗結果表明：1) 新聞網(wǎng)絡存在較多的孤立節(jié)點(即是新聞網(wǎng)絡節(jié)點數(shù)遠小于新聞數(shù))與較多的連通分支，但是最大連通分支相對于新網(wǎng)絡節(jié)點的比例較大；2) 新聞網(wǎng)絡具有較高的平均度、高聚集特性和和同配特性。

表2 各個時代的新聞網(wǎng)絡拓撲屬性

同時，通過實證分析新聞網(wǎng)絡，從時代1～時代4 表示頭版新聞的節(jié)點數(shù)與新聞網(wǎng)絡節(jié)點數(shù)之比依次是18.98%、12.11%、10.73%、8.76%，以及分析4 個新聞網(wǎng)絡的度分布p(k)。如圖2 所示，4 個新聞網(wǎng)絡的度分布都具有出無標度特性(即是近似冪律分布)，表現(xiàn)出復雜網(wǎng)絡的一般特性。

圖2 新聞網(wǎng)絡度分布

3.2.2 新聞重要性評價研究

基于新聞網(wǎng)絡的鄰接矩陣，分別計算網(wǎng)絡中各節(jié)點的H-PageRank 中心性、PageRank 中心性、LeaderRank 中心性、度中心、H 中心性、接近中心性及特征向量中心性，形成基于不同網(wǎng)絡節(jié)點中心性的節(jié)點排序序列。在此基礎上，利用不同排序列表長度條件下的Top-N 評價方法，對比分析H-PageRank排序算法與基于其他的網(wǎng)絡節(jié)點中心性的新聞重要性評價的有效性。

首先，針對每一個新聞網(wǎng)絡，本文基于7 種網(wǎng)絡節(jié)點中心性對其節(jié)點進行全局排序，通過全局排序列表條件下Top-N 評價方法計算頭版新聞的平均排序分估算出對應的AUC 值。圖3a 給出不同網(wǎng)絡節(jié)點中心性計算得到的AUC 值。對于每一個新聞網(wǎng)絡，7 種網(wǎng)絡節(jié)點中心性給出非常相近的AUC 值，表明它們對新聞網(wǎng)絡全局排序的相近性，但是AUC 值都顯著高于隨機排序理論值0.5，表明它們對新聞網(wǎng)絡進行全局排序的有效性。值得注意的是，對于每一個新聞網(wǎng)絡，基于HPR 和HR 的AUC 值對阻尼系數(shù) d都有很高的魯棒性，因此本文選取最優(yōu)AUC 值對應的阻尼系數(shù)，d=0.9。

圖3 基于7 種網(wǎng)絡節(jié)點中心性的Top-N評價方法的正確性對比

進一步，為了能夠區(qū)分7 種網(wǎng)絡節(jié)點中心性對新聞重要性評價的影響力，本文通過局部排序條件下Top-N (N=20)評價方法，計算頭版新聞的(預測)正確率(圖3b)、召回率(圖3c)和F1 指標(圖3d)。對比分析實驗結果，可以發(fā)現(xiàn)基于H-PageRank 中心性Top-20 評價方法在3 個正確性評價指標上表現(xiàn)出較好的性能(除了時代4 的新聞網(wǎng)絡)。具體而言，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 中心性的新聞重要性評價更優(yōu)，驗證了H-PageRank 排序算法的有效性。

通過圖3 實驗結果的對比分析，可以得出3 個正確性指標給出H-PageRank 中心性相比于其他網(wǎng)絡節(jié)點中心性的相似結果，所以本文從正確率角度對比分析不同局部排序列表長度條對基于7 種網(wǎng)絡節(jié)點中心性的Top-N 評價方法的影響。圖4 給出不同局部排序列表長度對Top-N 評價方法的實驗結果，虛線對應的理論基準(即是頭版新聞占比)。依據(jù)不同時代的新聞網(wǎng)絡。

圖4 不同局部排序列表長度條件下基于7 種中心性的Top-N 評價方法的性能對比分析

時代1 的新聞網(wǎng)絡如圖4a 所示。H-PageRank中心性和PageRank 中心性對Top-N 評價方法影響最大，基于這兩類中心性的正確率要顯著高于其他4 類中心性。特別是，基于H-PageRank 中心性的Top-N 評價方法，其正確率受局部排序列表長度影響較小，且相比于理論基準有極大的提高，比如Top-10 評價方法的正確率可達4.5 倍。

時代2 的新聞網(wǎng)絡如圖4b 所示。基于特征向量中心性的Top-N 評價方法，在不同局部排序列表長度條件下的平均正確率最高，且相比于理論基準有極大的提高，如Top-10 評價方法的正確率可達3.9 倍。

時代3 的新聞網(wǎng)絡如圖4c 所示。與時代1的實驗結果相類似，H-PageRank 中心性和Page-Rank 中心性顯著優(yōu)于其他4 類中心性。但是，局部排序列表長度對基于H-PageRank 中心性和Page-Rank 中心性的Top-N 評價方法影響較明顯。同時，對于基于H-PageRank 中心性和Page-Rank 中心性的Top-N 評價方法，其Top-10 評價方法的正確率相比于理論基準可達5 倍。

時代4 的新聞網(wǎng)絡如圖4d 所示。基于H 中心性的Top-N 評價方法，在不同局部列表長度條件下的平均正確率最高，且相比于理論基準有顯著的提高，如Top-10 評價方法的正確率可達4 倍。

值得注意的是，如果局部排序列表長度過小，樣本數(shù)目過少會使實驗結果有較大的誤差，反之，如果推薦列表長度繼續(xù)加大，基于不同網(wǎng)絡節(jié)點中心性的實驗結果的差異變小，且會逐漸趨向于理論基準。但是，對于有限的局部排序列表長度條件下，基于7 種網(wǎng)絡節(jié)點中心性的Top-N 評價方法的正確率都優(yōu)于理論基準。特別是，當選取的局部排序列表長度N=20 時，在4 個時代的新聞網(wǎng)絡上，基于H-PageRank 中心性的評價方法的最優(yōu)正確率相比于理論基準，分別提高391.9%、249.7%、345.5%和98.2%。綜上所述，實驗結果表明基于7 種網(wǎng)絡節(jié)點中心性的Top-N 評價方法對于有限的局部排序列表長度的魯棒性。

4 結 束 語

本文以《人民日報》為例，從復雜網(wǎng)絡視角研究新聞網(wǎng)絡，利用新聞網(wǎng)絡節(jié)點中心性，構建Top-N 評價方法。在此基礎上，以是否成為頭版新聞作為新聞重要性評價準則，比較不同網(wǎng)絡節(jié)點中心性指標的表現(xiàn)。在橫向比較各類中心性排序算法對評價新聞重要性的影響時，盡管7 種網(wǎng)絡節(jié)點中心性指標在全局排序條件下表現(xiàn)出相近的AUC值，但是Top-20 評價方法的平均正確率、平均召回率及平均 F1值都表明H-PageRank 排序算法要明顯優(yōu)于其他6 種中心性排序算法。基于此，本文認為提出的H-PageRank 算法是有效且高效的。