PageRank在度量標(biāo)準(zhǔn)文獻(xiàn)重要性中的研究

李 濤，汪光陽

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

PageRank在度量標(biāo)準(zhǔn)文獻(xiàn)重要性中的研究

李 濤，汪光陽*

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

為了更好的度量標(biāo)準(zhǔn)文獻(xiàn)的重要性，現(xiàn)將PageRank算法引入到標(biāo)準(zhǔn)引用網(wǎng)絡(luò)中，但算法在計算標(biāo)準(zhǔn)文獻(xiàn)重要性時僅根據(jù)出度數(shù)來平均分配PageRank值，在一定程度上影響了標(biāo)準(zhǔn)文獻(xiàn)重要性的度量。為此提出了一種StandardRank算法來改進(jìn)PageRank算法，在計算標(biāo)準(zhǔn)文獻(xiàn)重要性時用標(biāo)準(zhǔn)文獻(xiàn)重要性比例來代替平均分配，并且根據(jù)標(biāo)準(zhǔn)引用網(wǎng)絡(luò)自身的結(jié)構(gòu)特征修改了阻尼系數(shù)。實驗結(jié)果表明：StandardRank算法在度量標(biāo)準(zhǔn)文獻(xiàn)重要性時具有更好的效果。

標(biāo)準(zhǔn)文獻(xiàn)；標(biāo)準(zhǔn)引用網(wǎng)絡(luò)；PageRank算法；阻尼系數(shù)；數(shù)據(jù)挖掘

在文獻(xiàn)[1]中對標(biāo)準(zhǔn)的定義是：為了在一定范圍內(nèi)獲得最佳秩序，經(jīng)協(xié)商一致制定并由公認(rèn)機(jī)構(gòu)批準(zhǔn)，共同使用的和重復(fù)使用的一種規(guī)范性文件。

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

對于文獻(xiàn)重要性的研究采用的多是引文分析，即依據(jù)文獻(xiàn)的被引用次數(shù)來衡量一篇文獻(xiàn)是否重要[2]。隨著社會網(wǎng)絡(luò)分析方法[3]的興起，越來越多的人開始應(yīng)用網(wǎng)絡(luò)分析來研究文獻(xiàn)的重要性[4]。文中基于標(biāo)準(zhǔn)文獻(xiàn)間的引用關(guān)系構(gòu)建標(biāo)準(zhǔn)引用網(wǎng)絡(luò)，其中，節(jié)點表示標(biāo)準(zhǔn)文獻(xiàn)，邊表示標(biāo)準(zhǔn)文獻(xiàn)間的引用關(guān)系，由引用標(biāo)準(zhǔn)文獻(xiàn)指向被引用標(biāo)準(zhǔn)文獻(xiàn)。

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

1 PageRank算法

1.1 算法簡介

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

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

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

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

1.2 算法分析

1.2.1 阻尼系數(shù)d

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

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

1.2.2 PageRank值平均分配問題

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

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

2 PageRank算法的改進(jìn)

2.1 改進(jìn)思路

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

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

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

2.2 StandardRank算法描述

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

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

標(biāo)準(zhǔn)v分配其StandardRank值給標(biāo)準(zhǔn)u的比重Wvu的計算公式描述如下

其中，u∈O（v），SR（u）表示標(biāo)準(zhǔn)u的StandardRank值，O（v）表示標(biāo)準(zhǔn)v所引用的標(biāo)準(zhǔn)集合，表示標(biāo)準(zhǔn)v所引用的標(biāo)準(zhǔn)的StandardRank值之和。

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

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

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

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

3 實驗及其結(jié)果分析

為驗證改進(jìn)算法的有效性，進(jìn)行如下實驗。選擇的實驗數(shù)據(jù)來源于中國標(biāo)準(zhǔn)服務(wù)網(wǎng)[11]，收集環(huán)境保護(hù)行業(yè)的標(biāo)準(zhǔn)文獻(xiàn)，經(jīng)過篩選和過濾，得到有效標(biāo)準(zhǔn)文獻(xiàn)數(shù)據(jù)291篇。通過對標(biāo)準(zhǔn)文獻(xiàn)間的引用關(guān)系進(jìn)行整理，構(gòu)建標(biāo)準(zhǔn)引用網(wǎng)絡(luò)，用于實驗分析。

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

3.1 相關(guān)性分析

驗證StandardRank算法、PageRank算法和標(biāo)準(zhǔn)文獻(xiàn)被引用次數(shù)（入度）之間的相關(guān)性，結(jié)果見表1。

表1 相關(guān)性分析結(jié)果

通過相關(guān)性分析結(jié)果可以看出，StandardRank算法和PageRank算法與標(biāo)準(zhǔn)文獻(xiàn)被引用次數(shù)之間具有很高的正向相關(guān)性，相關(guān)度都達(dá)到0.84以上，可以用來度量標(biāo)準(zhǔn)文獻(xiàn)的重要性。

3.2 結(jié)果分析

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

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

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

從引用網(wǎng)絡(luò)的結(jié)構(gòu)可以看出，盡管這兩個標(biāo)準(zhǔn)具有相同的入度（被引用次數(shù)），但二者的重要性明顯不同，HJ/T212在引用網(wǎng)絡(luò)中的位置比HJ/T164重要的多。這一分析結(jié)果吻合StandardRank算法的重要性排名，從而也表明了該算法的有效性。

圖1 實驗結(jié)果圖

圖2 HJ/T212和HJ/T164的引用網(wǎng)絡(luò)

4 結(jié)語

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

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

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

[3]劉軍.社會網(wǎng)絡(luò)分析導(dǎo)論[M].北京：社會科學(xué)文獻(xiàn)出版社，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算法的權(quán)威值不均衡分配問題[J].計算機(jī)工程，2007，33（18）：53-55.

[7]王德廣，周志剛，梁旭.PageRank算法的分析及其改進(jìn)[J].計算機(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]中國標(biāo)準(zhǔn)化研究院.環(huán)境保護(hù)行業(yè)的標(biāo)準(zhǔn)文獻(xiàn)[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

責(zé)任編輯：艾淑艷

TP393

：A

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

2016－01－06

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

李 濤（1990-），男，安徽淮南人，碩士研究生，研究方向：社會網(wǎng)絡(luò)，計算機(jī)技術(shù)。*

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