PageRank在度量标准文献重要性中的研究

李 涛，汪光阳

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243002）

PageRank在度量标准文献重要性中的研究

李 涛，汪光阳*

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243002）

为了更好的度量标准文献的重要性，现将PageRank算法引入到标准引用网络中，但算法在计算标准文献重要性时仅根据出度数来平均分配PageRank值，在一定程度上影响了标准文献重要性的度量。为此提出了一种StandardRank算法来改进PageRank算法，在计算标准文献重要性时用标准文献重要性比例来代替平均分配，并且根据标准引用网络自身的结构特征修改了阻尼系数。实验结果表明：StandardRank算法在度量标准文献重要性时具有更好的效果。

标准文献；标准引用网络；PageRank算法；阻尼系数；数据挖掘

在文献[1]中对标准的定义是：为了在一定范围内获得最佳秩序，经协商一致制定并由公认机构批准，共同使用的和重复使用的一种规范性文件。

在当今知识经济时代，标准的重要性日益凸显，标准反映着该国的经济、技术和生产水平，对标准以及标准化的理论研究与实践应用成为学术界的热点。标准文献作为标准的重要载体和表现形式，是科研人员研制新产品和改进老产品、了解国家发展情况的重要科技情报源之一。随着标准文献数量的增多，要找到符合要求的标准变的越来越难。因此，对标准文献的重要性进行研究、评价标准文献的价值已变的越来越重要。

对于文献重要性的研究采用的多是引文分析，即依据文献的被引用次数来衡量一篇文献是否重要[2]。随着社会网络分析方法[3]的兴起，越来越多的人开始应用网络分析来研究文献的重要性[4]。文中基于标准文献间的引用关系构建标准引用网络，其中，节点表示标准文献，边表示标准文献间的引用关系，由引用标准文献指向被引用标准文献。

PageRank算法[5]是一种度量网页重要性的算法，通过分析链接网络中网页间的链接结构来获得重要网页。算法在度量网页的重要性时，不仅考虑网页的入链数，且考虑入链网页的重要性。算法已经在Google搜索引擎的网页排名中取得了成功。由于标准引用网络和链接网络有着相似的网络构成，文中将PageRank算法引入到标准引用网络中，通过分析标准间的引用关系结构来获得重要标准。但算法在计算标准文献重要性时仅根据出度数来平均分配PageRank值[6-7]，在一定程度上对标准重要性的度量造成影响。文中针对平均分配PageRank值的问题进行了改进，提出一种StandardRank算法，根据被引用标准文献的重要性按比例分配StandardRank值。并根据标准引用网络自身的结构特点，修改阻尼系数值，使其更适合标准引用网络的环境。实验结果表明，StandardRank算法在度量标准重要性时具有更好的效果。

1 PageRank算法

1.1 算法简介

PageRank算法的基本思想[5]：如果一个网页接收到其他网页的入链数量越多，则这个网页越重要；尽管一个网页的入链数量不多，但如果被一个重要网页链入，那么这个网页也可能是重要网页。PageRank算法基于整个Web网页的链接结构来计算各网页的PageRank值，即网页的重要性得分。

PageRank算法的计算公式简单描述如下

其中，PR（v）表示网页v的PageRank值，B（u）表示网页u的入链网页集合，C（v）表示网页v的出链数，N表示网页的总数量，d表示阻尼系数。

PageRank算法的优点：一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得，有效减少了在线查询时的计算量，极大降低了查询响应时间。

1.2 算法分析

1.2.1 阻尼系数d

互联网中可能存在一些出链数为0的网页，即不链接任何其他网页的网页，如果用户访问到这样的网页，会导致PageRank值传递不出去，这就是PageRank值沉淀现象（LinkSink）。公式（1）中阻尼系数d的引入就是为避免这一现象的发生。

阻尼系数d表示用户跟随网页链接向后浏览的概率，1-d则表示用户重新随机选择一个新网页继续浏览的概率。Brin和Page[5]在最初的研究中将阻尼系数d取值为0.85，这是因为一个用户浏览网页的链接数一般为6，也就是说，用户停止向后浏览而重新随机选择一个新网页继续浏览的概率为：1-d=1/6≈0.15。然而，Chen等人[8]通过研究发现，在文献引用网络中，引用链接有较短的距离，平均值为2，在引用网络中阻尼系数d一般取值为0.5。由于，文中研究的是标准引用网络，因此，选取阻尼系数的值为0.5。

1.2.2 PageRank值平均分配问题

网页链接分为岀链和入链，而入链的数量和质量决定PageRank值。一个网页的入链数量越多或者被重要网页链入，则该网页的重要性越高。PageRank算法将当前网页的PageRank值按照岀链数量平均分配给它所链接的网页。然而，互联网中网页的质量千差万别，即使是被同一个网页所链接的网页，其网页质量也差很多。所以，PageRank算法这种平均分配PageRank值的方法，在一定程度上影响了网页的重要性度量。

PageRank算法出现平均分配PageRank值的现象，是因为没有对岀链网页的重要性进行区分[9]。权威网页和普通网页被链接的概率是不同的，权威网页被链接的概率很高，但普通网页被链接的概率却很低。

2 PageRank算法的改进

2.1 改进思路

通过上节对PageRank值平均分配问题的分析，知道出现这一现象，是因为PageRank算法没有对出链网页的重要性进行区分。

在标准引用网络中，由于标准类型的不同，有国家标准、行业标准、地方标准、企业标准等，导致每个标准的重要性各不相同，即使是被同一个标准所引用的标准，重要性也不尽相同。因此，文中在将PageRank算法应用到标准引用网络中时，为更好地度量标准的重要性，对被引用标准的重要性进行了区分，对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算法执行过程

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]，收集环境保护行业的标准文献，经过筛选和过滤，得到有效标准文献数据291篇。通过对标准文献间的引用关系进行整理，构建标准引用网络，用于实验分析。

文中针对标准引用网络主要选择三种节点重要性度量方法进行实验：节点的入度，即标准文献的被引用次数、PageRank算法及改进后的StandardRank算法。为评判各度量方法的优劣，在进行实验之前，邀请环境保护专业方面的专家人工评判出前10篇相对重要的标准文献。

3.1 相关性分析

验证StandardRank算法、PageRank算法和标准文献被引用次数（入度）之间的相关性，结果见表1。

表1 相关性分析结果

通过相关性分析结果可以看出，StandardRank算法和PageRank算法与标准文献被引用次数之间具有很高的正向相关性，相关度都达到0.84以上，可以用来度量标准文献的重要性。

3.2 结果分析

其次，根据各度量方法的实验结果对标准按重要性进行排名，并结合专家排名，绘制实验结果图，如图1所示。从图1中的实验结果可以看出，StandardRank算法和PageRank算法相比于被引用次数（入度）度量方法更容易发现潜在的重要标准。例如，图1中的标准编码为HJ618的标准，在StandardRank算法和PageRank算法中都具有较高的排名，但该标准的被引用次数却只有4，导致该标准在被引用次数方法中排名靠后。进一步分析发现，该标准规定了测定环境空气中PM10和PM2.5的重量法，是环境空气颗粒物 （PM10和PM2.5）采样器和监测系统方面的基础性标准，由于有些标准只是间接的引用该标准，导致该标准被引用次数较少，未能体现出该标准的实际重要性。

从图1中可以清楚地看到，相比于PageRank算法，StandardRank算法度量的标准排名和专家排名更接近，从而表明StandardRank算法在度量标准文献重要性方面具有更好的效果。

此外，从实验结果中发现一组数据 HJ/T212和HJ/T164，这两个标准具有相同的被引用次数（入度）10，但在StandardRank算法和PageRank算法中，重要性却不相同，且重要性排名相反。为分析出原因，绘制出这两个标准的引用网络，如图2所示。

从引用网络的结构可以看出，尽管这两个标准具有相同的入度（被引用次数），但二者的重要性明显不同，HJ/T212在引用网络中的位置比HJ/T164重要的多。这一分析结果吻合StandardRank算法的重要性排名，从而也表明了该算法的有效性。

图1 实验结果图

图2 HJ/T212和HJ/T164的引用网络

4 结语

文中将PageRank算法引入到标准引用网络中，用来度量标准文献的重要性。在对PageRank算法进行分析的基础上，发现PageRank值平均分配问题，针对这一问题进行了改进，提出StandardRank算法，并且根据标准引用网络自身的结构特征修改了阻尼系数。实验结果表明，改进后的算法和PageRank算法相比，能够更好地度量标准文献的重要性；StandardRank算法和PageRank算法相比于被引用次数度量方法更容易发现潜在的重要标准。但StandardRank算法在计算复杂度上比PageRank算法要稍大一些，减少StandardRank算法的计算复杂度将是下一步研究工作的重点。

[1]中华人民共和国国家质量监督检验检疫总局.GB/T 20000.1-2014，标准化工作指南 第1部分：标准化和相关活动的通用词汇[S].北京：中国标准出版社，2014.

[2]吴海峰，孙一鸣.引文网络的研究现状及其发展综述[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]中国标准化研究院.环境保护行业的标准文献[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。