李 濤，汪光陽

（安徽工業(yè)大學 計算機科學與技術學院，安徽 馬鞍山 243002）

PageRank在度量標準文獻重要性中的研究

李 濤，汪光陽*

（安徽工業(yè)大學 計算機科學與技術學院，安徽 馬鞍山 243002）

為了更好的度量標準文獻的重要性，現將PageRank算法引入到標準引用網絡中，但算法在計算標準文獻重要性時僅根據出度數來平均分配PageRank值，在一定程度上影響了標準文獻重要性的度量。為此提出了一種StandardRank算法來改進PageRank算法，在計算標準文獻重要性時用標準文獻重要性比例來代替平均分配，并且根據標準引用網絡自身的結構特征修改了阻尼系數。實驗結果表明：StandardRank算法在度量標準文獻重要性時具有更好的效果。

標準文獻；標準引用網絡；PageRank算法；阻尼系數；數據挖掘

在文獻[1]中對標準的定義是：為了在一定范圍內獲得最佳秩序，經協(xié)商一致制定并由公認機構批準，共同使用的和重復使用的一種規(guī)范性文件。

在當今知識經濟時代，標準的重要性日益凸顯，標準反映著該國的經濟、技術和生產水平，對標準以及標準化的理論研究與實踐應用成為學術界的熱點。標準文獻作為標準的重要載體和表現形式，是科研人員研制新產品和改進老產品、了解國家發(fā)展情況的重要科技情報源之一。隨著標準文獻數量的增多，要找到符合要求的標準變的越來越難。因此，對標準文獻的重要性進行研究、評價標準文獻的價值已變的越來越重要。

對于文獻重要性的研究采用的多是引文分析，即依據文獻的被引用次數來衡量一篇文獻是否重要[2]。隨著社會網絡分析方法[3]的興起，越來越多的人開始應用網絡分析來研究文獻的重要性[4]。文中基于標準文獻間的引用關系構建標準引用網絡，其中，節(jié)點表示標準文獻，邊表示標準文獻間的引用關系，由引用標準文獻指向被引用標準文獻。

PageRank算法[5]是一種度量網頁重要性的算法，通過分析鏈接網絡中網頁間的鏈接結構來獲得重要網頁。算法在度量網頁的重要性時，不僅考慮網頁的入鏈數，且考慮入鏈網頁的重要性。算法已經在Google搜索引擎的網頁排名中取得了成功。由于標準引用網絡和鏈接網絡有著相似的網絡構成，文中將PageRank算法引入到標準引用網絡中，通過分析標準間的引用關系結構來獲得重要標準。但算法在計算標準文獻重要性時僅根據出度數來平均分配PageRank值[6-7]，在一定程度上對標準重要性的度量造成影響。文中針對平均分配PageRank值的問題進行了改進，提出一種StandardRank算法，根據被引用標準文獻的重要性按比例分配StandardRank值。并根據標準引用網絡自身的結構特點，修改阻尼系數值，使其更適合標準引用網絡的環(huán)境。實驗結果表明，StandardRank算法在度量標準重要性時具有更好的效果。

1 PageRank算法

1.1 算法簡介

PageRank算法的基本思想[5]：如果一個網頁接收到其他網頁的入鏈數量越多，則這個網頁越重要；盡管一個網頁的入鏈數量不多，但如果被一個重要網頁鏈入，那么這個網頁也可能是重要網頁。PageRank算法基于整個Web網頁的鏈接結構來計算各網頁的PageRank值，即網頁的重要性得分。

PageRank算法的計算公式簡單描述如下

其中，PR（v）表示網頁v的PageRank值，B（u）表示網頁u的入鏈網頁集合，C（v）表示網頁v的出鏈數，N表示網頁的總數量，d表示阻尼系數。

PageRank算法的優(yōu)點：一個與查詢無關的靜態(tài)算法，所有網頁的PageRank值通過離線計算獲得，有效減少了在線查詢時的計算量，極大降低了查詢響應時間。

1.2 算法分析

1.2.1 阻尼系數d

互聯(lián)網中可能存在一些出鏈數為0的網頁，即不鏈接任何其他網頁的網頁，如果用戶訪問到這樣的網頁，會導致PageRank值傳遞不出去，這就是PageRank值沉淀現象（LinkSink）。公式（1）中阻尼系數d的引入就是為避免這一現象的發(fā)生。

阻尼系數d表示用戶跟隨網頁鏈接向后瀏覽的概率，1-d則表示用戶重新隨機選擇一個新網頁繼續(xù)瀏覽的概率。Brin和Page[5]在最初的研究中將阻尼系數d取值為0.85，這是因為一個用戶瀏覽網頁的鏈接數一般為6，也就是說，用戶停止向后瀏覽而重新隨機選擇一個新網頁繼續(xù)瀏覽的概率為：1-d=1/6≈0.15。然而，Chen等人[8]通過研究發(fā)現，在文獻引用網絡中，引用鏈接有較短的距離，平均值為2，在引用網絡中阻尼系數d一般取值為0.5。由于，文中研究的是標準引用網絡，因此，選取阻尼系數的值為0.5。

1.2.2 PageRank值平均分配問題

網頁鏈接分為岀鏈和入鏈，而入鏈的數量和質量決定PageRank值。一個網頁的入鏈數量越多或者被重要網頁鏈入，則該網頁的重要性越高。PageRank算法將當前網頁的PageRank值按照岀鏈數量平均分配給它所鏈接的網頁。然而，互聯(lián)網中網頁的質量千差萬別，即使是被同一個網頁所鏈接的網頁，其網頁質量也差很多。所以，PageRank算法這種平均分配PageRank值的方法，在一定程度上影響了網頁的重要性度量。

PageRank算法出現平均分配PageRank值的現象，是因為沒有對岀鏈網頁的重要性進行區(qū)分[9]。權威網頁和普通網頁被鏈接的概率是不同的，權威網頁被鏈接的概率很高，但普通網頁被鏈接的概率卻很低。

2 PageRank算法的改進

2.1 改進思路

通過上節(jié)對PageRank值平均分配問題的分析，知道出現這一現象，是因為PageRank算法沒有對出鏈網頁的重要性進行區(qū)分。

在標準引用網絡中，由于標準類型的不同，有國家標準、行業(yè)標準、地方標準、企業(yè)標準等，導致每個標準的重要性各不相同，即使是被同一個標準所引用的標準，重要性也不盡相同。因此，文中在將PageRank算法應用到標準引用網絡中時，為更好地度量標準的重要性，對被引用標準的重要性進行了區(qū)分，對PageRank算法進行改進，提出一種StandardRank算法。

改進后的StandardRank算法在分配StandardRank值時根據被引用標準的重要性按比例進行分配。StandardRank算法改進的主要思路是：如果被引用的標準是一個重要標準，應該多分配給它一些Standard-Rank值；如果被引用的標準是一個普通標準，應該少分配給它一些StandardRank值[10]。衡量一個標準是不是重要標準主要是根據該標準的StandardRank值，StandardRank值越高則該標準越重要。

2.2 StandardRank算法描述

由于StandardRank算法是從PageRank算法改進而來，因此，二者的計算公式很相似，具體描述如下

其中，SR（v）表示標準v的StandardRank值，B（u）表示引用標準u的標準集合，Wvu表示標準v分配其StandardRank值給標準u的比重，SR（v）*Wvu則表示標準v分配給標準u的StandardRank值，N表示標準的總數量，d表示阻尼系數，公式中取值為0.5。

標準v分配其StandardRank值給標準u的比重Wvu的計算公式描述如下

其中，u∈O（v），SR（u）表示標準u的StandardRank值，O（v）表示標準v所引用的標準集合，表示標準v所引用的標準的StandardRank值之和。

2.3 StandardRank算法執(zhí)行過程

StandardRank算法和PageRank算法一樣都是通過不斷迭代，直到最后兩次的結果近似或者相同，此時停止計算，最終的結果向量就是各個標準的StandardRank值，具體步驟描述如下：

（1）初始化階段，由于開始階段，標準的重要性未知，初始化標準的StandardRank值向量P，給每個標準的重要性均賦值為1；（2）根據標準的StandardRank值向量P和公式（3），計算標準v分配其StandardRank值給標準u的比重Wvu；（3）根據公式（2），計算標準新的StandardRank值，得到新一輪標準的StandardRank值向量R；（4）如果|R-P|?ε，則停止迭代，向量R為標準最終的StandardRank值向量，即標準的重要性得分向量；否則，P=R，轉向步驟2。

從上述計算步驟可見，StandardRank算法比PageRank算法多了步驟2，即計算比重Wvu，這就導致相比于PageRank算法，StandardRank算法在計算復雜度上要稍大一些，但由于算法是離線計算，因此，可以接受。

3 實驗及其結果分析

為驗證改進算法的有效性，進行如下實驗。選擇的實驗數據來源于中國標準服務網[11]，收集環(huán)境保護行業(yè)的標準文獻，經過篩選和過濾，得到有效標準文獻數據291篇。通過對標準文獻間的引用關系進行整理，構建標準引用網絡，用于實驗分析。

文中針對標準引用網絡主要選擇三種節(jié)點重要性度量方法進行實驗：節(jié)點的入度，即標準文獻的被引用次數、PageRank算法及改進后的StandardRank算法。為評判各度量方法的優(yōu)劣，在進行實驗之前，邀請環(huán)境保護專業(yè)方面的專家人工評判出前10篇相對重要的標準文獻。

3.1 相關性分析

驗證StandardRank算法、PageRank算法和標準文獻被引用次數（入度）之間的相關性，結果見表1。

表1 相關性分析結果

通過相關性分析結果可以看出，StandardRank算法和PageRank算法與標準文獻被引用次數之間具有很高的正向相關性，相關度都達到0.84以上，可以用來度量標準文獻的重要性。

3.2 結果分析

其次，根據各度量方法的實驗結果對標準按重要性進行排名，并結合專家排名，繪制實驗結果圖，如圖1所示。從圖1中的實驗結果可以看出，StandardRank算法和PageRank算法相比于被引用次數（入度）度量方法更容易發(fā)現潛在的重要標準。例如，圖1中的標準編碼為HJ618的標準，在StandardRank算法和PageRank算法中都具有較高的排名，但該標準的被引用次數卻只有4，導致該標準在被引用次數方法中排名靠后。進一步分析發(fā)現，該標準規(guī)定了測定環(huán)境空氣中PM10和PM2.5的重量法，是環(huán)境空氣顆粒物 （PM10和PM2.5）采樣器和監(jiān)測系統(tǒng)方面的基礎性標準，由于有些標準只是間接的引用該標準，導致該標準被引用次數較少，未能體現出該標準的實際重要性。

從圖1中可以清楚地看到，相比于PageRank算法，StandardRank算法度量的標準排名和專家排名更接近，從而表明StandardRank算法在度量標準文獻重要性方面具有更好的效果。

此外，從實驗結果中發(fā)現一組數據 HJ/T212和HJ/T164，這兩個標準具有相同的被引用次數（入度）10，但在StandardRank算法和PageRank算法中，重要性卻不相同，且重要性排名相反。為分析出原因，繪制出這兩個標準的引用網絡，如圖2所示。

從引用網絡的結構可以看出，盡管這兩個標準具有相同的入度（被引用次數），但二者的重要性明顯不同，HJ/T212在引用網絡中的位置比HJ/T164重要的多。這一分析結果吻合StandardRank算法的重要性排名，從而也表明了該算法的有效性。

圖1 實驗結果圖

圖2 HJ/T212和HJ/T164的引用網絡

4 結語

文中將PageRank算法引入到標準引用網絡中，用來度量標準文獻的重要性。在對PageRank算法進行分析的基礎上，發(fā)現PageRank值平均分配問題，針對這一問題進行了改進，提出StandardRank算法，并且根據標準引用網絡自身的結構特征修改了阻尼系數。實驗結果表明，改進后的算法和PageRank算法相比，能夠更好地度量標準文獻的重要性；StandardRank算法和PageRank算法相比于被引用次數度量方法更容易發(fā)現潛在的重要標準。但StandardRank算法在計算復雜度上比PageRank算法要稍大一些，減少StandardRank算法的計算復雜度將是下一步研究工作的重點。

[1]中華人民共和國國家質量監(jiān)督檢驗檢疫總局.GB/T 20000.1-2014，標準化工作指南 第1部分：標準化和相關活動的通用詞匯[S].北京：中國標準出版社，2014.

[2]吳海峰，孫一鳴.引文網絡的研究現狀及其發(fā)展綜述[J].計算機應用與軟件，2012，29（2）：164-168.

[3]劉軍.社會網絡分析導論[M].北京：社會科學文獻出版社，2004.

[4]MA Nan，GUAN Jiancheng，ZHAO Yi.Bringing PageRank to the citation analysis[J].Information Processing and Management，2008，44（2）：800-810.

[5]PAGE L，BRIN S，MOTWANI R，et al.The PageRank citation ranking：Bringing order to the web[DB/OL].（2001-10-30）[2008-12-28].http:// ilpubs.stanford.edu:8090/422/.

[6]田甜，倪琳.基于PageRank算法的權威值不均衡分配問題[J].計算機工程，2007，33（18）：53-55.

[7]王德廣，周志剛，梁旭.PageRank算法的分析及其改進[J].計算機工程，2010，36（22）：291-293.

[8]CHEN P，XIE H，MASLOV S，et al.Finding scientific gems with Google’s PageRank algorithm[J].Journal of Informetrics，2008，1（1）：8-15.

[9]XING W P，GHORBANI A.Weighted PageRank Algorithm[C]//Communication Networks and Services Research.IEEE：Secnod Annual Conference，2004：305-314.

[10]LIU X M，BOLLEN J，NELSON M L，et al.Co-authorship networks in the digital library research community[J].Information Processing and Management，2005，41（6）：1462-1480.

[11]中國標準化研究院.環(huán)境保護行業(yè)的標準文獻[DB/OL].[2015-05-15].http://www.cssn.net.cn/pagesnew/search/search_base_result.jsp?.

PageRank in measuring the importance of standard literature

LI Tao，WANG Guangyang*
（School of Computer Science&Technology，Anhui University of Technology，Ma’anshan 243032，China）

In order to measure the importance of standard literature better，the PageRank algorithm was introduced into the standard citation network，but PageRank value was evenly distributed based only on out-degree in calculating the importance of standard literature，which，to a certain extent，affects the measurement of importance of standard literature.Therefore，StandardRank algorithm，which calculates the importance of standard literature with importance proportion，was proposed to improve the PageRank algorithm.This algorithm modified the damping coefficient according to the structure characteristics of the standard citation network.The experimental results show that the StandardRank algorithm works better in measuring the importance of standard literature.

standard literature；standard citation network；PageRank algorithm；damping coefficient；data mining

責任編輯：艾淑艷

TP393

：A

：2096－3289（2017）02－0059－04

2016－01－06

國家科技支撐計劃項目（2012BAK30B04）

李 濤（1990-），男，安徽淮南人，碩士研究生，研究方向：社會網絡，計算機技術。*

汪光陽（1955-），男，教授，碩士生導師，E-mail：gywang@ahut.edu.cn。