Zipf定律与网络信息计量学

刘胜久，李天瑞，珠 杰, 2

(1. 西南交通大学 信息科学与技术学院，四川 成都 611756;2. 西藏大学 计算机科学系、藏文信息技术研究中心，西藏 拉萨 850000)



Zipf定律与网络信息计量学

刘胜久1，李天瑞1，珠 杰1, 2

(1. 西南交通大学 信息科学与技术学院，四川 成都 611756;2. 西藏大学 计算机科学系、藏文信息技术研究中心，西藏 拉萨 850000)

作为文献计量学重要定律的Zipf定律已在许多领域得到较广泛的应用，网络信息计量学伴随着网络信息的激增而受到人们越来越大的关注。该文结合搜索结果数量的分布情况，提出了在网络信息计量学中仍然存在Zipf定律的猜想，并采用公开的词语集在几个代表性的搜索引擎中进行实验验证，证实了搜索结果数目近似服从Zipf定律的结论，其中Baidu与So搜索结果的Zipf指数为0.003。

Zipf定律；Zipf指数；搜索引擎；网络信息计量学

1 引言

自美国语言学家George Kingsley Zipf于1949年提出Zipf定律以来，Zipf定律已在信息学、计算机科学、经济学、社会学、生物学、地理学、物理学等许多领域得到较广泛的应用，在学术界享有极高的声誉。

Zipf 定律描述的主要是词频和词序之间的联系，它的一种表述形式为： 在自然语言的语料库里，一个单词出现的频率与它在频率表里的排名成反比。Zipf 定律揭示了语言学中的重要现象，使得人类对语言的分布认识更为深刻，对其他学科产生了很大影响。Zipf定律是一个实验定律，而非理论定律，缺乏严格的理论推导与证明，但Zipf定律可以在很多现象中观察到。如果我们在一个广域范围内做出适当的近似，那么，许多自然现象都符合Zipf定律。

网络信息计量学是信息计量学在互联网中的应用与拓展，是伴随着互联网信息爆炸而出现的一门新兴学科，它通过对互联网信息的量化分析，为科研和社会服务。近年来，网络信息计量学已在网上信息本身的直接计量、网上文献信息及其相关特征的信息计量、网络站点的信息计量等其他问题上取得一系列卓有成效的研究成果。作为最重要的互联网应用之一，搜索引擎的出现部分解决了互联网上信息泛滥所导致的信息检索困难问题。搜索引擎的类别也由传统的搜索引擎逐渐衍生出元搜索引擎、垂直搜索引擎、语义搜索引擎及智能搜索引擎等，对搜索引擎的研究是网络信息计量学的重要内容。本文拟通过对搜索引擎结果数量分布的研究，探讨Zipf定律在网络信息计量学中的应用，同时验证网络信息计量学中存在Zipf定律的猜想，并结合实际情况对实际的搜索结果数量进行分析。

2 研究现状

2.1 Zipf定律研究现状

Zipf定律来源于语言学，最早是Zipf在对英文词汇的词频分布的研究中发现的，其在中文[1-3]及印度语[4]、意大利语[5]其他语言词频分布中的适用性已得到证实，对Zipf定律在语言学中的应用尚在进一步深入[6]。而且，Zipf定律也在物理学[7]、经济学[8]、生物学[9]等其他领域都得到了广泛的应用[10]，其研究应用领域有进一步拓宽的趋势。

Zipf定律在中文中的研究与应用由来已久[11]，伴随着经济及社会的高速发展，近年来对Zipf定律的研究也日益关注其对经济及社会的促进作用。郑亚斌等人在中文歌词上做了一些传统的自然语言处理相关实验，利用Zipf定律对歌词语料库的字和词进行统计特征的考察，实验表明其分布基本符合Zipf定律[12]。刘宇凡等人对唐代以来的文学作品按不同时期进行分类建立语料库，字频的分布情况表明自唐代以来不同时期的字频都可以用一个指数截断的幂律函数进行很好的拟合，并且随着历史的发展，幂律性质不断衰减而指数性质不断增强[13]。

在网络传播领域中，一个较早被人注意的现象是网站的用户数和访问量的分布基本符合Zipf 定律。此后，国内外学者研究后发现，在企业规模的分布[14]、城市规模的分布[15]、地震时间间隔的分布[16]、网站下载分布[17]等现象及自然语言识别系统与资本投资[18]等领域中均存在Zipf定律。

在P2P网络研究中，Cai等人提出在结构化P2P网络的信任发现中仍然存在Zipf定律的猜想，并用实验证实了该猜想，同时研究了Zipf定律在其中的存在形式与特点[19]；在图像处理中，Hamoud等人应用Zipf定律定义了不同的模式及编码方法来描述图像的复杂结构化内容以降低模式的数目，并对图像进行分割及分类等深层次的处理，取得了较好的效果[20]。Zipf 定律也广泛应用于地理、经济、城市、交通等领域[21]。由于Zipf 定律是 Pareto 方程的对数变换，满足分形分维特征，将Zipf定律与分枝分维等其他理论与方法相结合，拓宽Zipf定律的研究应用领域并探讨其在其他领域的存在形式是当前Zipf定律研究的重点。

2.2 网络信息计量学研究现状

自Almind Tomas C在文献[22]中首次提出“网络信息计量学”以来，网络信息计量学作为信息计量学的重要发展趋势在国内外都受到了极大的关注。当前，网络信息计量学的研究热点主要集中在网络链接关系和网络影响因子、搜索引擎、用户行为及Web挖掘等方面。

在中文Web信息检索方面，李静静等人参考国外测试集的构建经验，构建了大规模中文网页信息检索测试集CWT，并对CWT进行了有效的统计分析和实验研究，同时组织了SEWM中文网页检索评测，推动了中文网页信息检索技术的发展[23]。鉴于高质量的数据对网络信息计量学的极端重要性，Shi等人探讨了依托当前数据源，基于Dublin Core元数据元素集合提取新的数据达到为网络计量学提供更好的数据支持目标的可行性[24]；由于网络信息计量学方法是评估高等学府的重要工具之一，Elgharabawy 等人研究了WCAG方法与网络信息计量学方法及搜索引擎在教育机构评估中的关联，结果表明采用网络信息计量学的方法与WCAG方法所得到的教育机构排名存在一致的正相关关系，由此提出可将可访问性作为搜索引擎优化的重要内容[25]；此外，采用复杂网络的理论与方法研究计算机网络上的信息也是当前研究的一大热点[26]。

从当前网络信息计量学研究的内容与方法来看，研究经典的信息计量学，尤其是文献计量学的理论与方法在互联网中的推广与拓展是目前网络信息计量学研究的热点，对作为互联网上最重要应用之一的搜索引擎的研究也引起了人们越来越大的关注，借助搜索引擎研究网络信息计量学是网络信息计量学研究的一大热点。此外，人们也开始将复杂网络的理论与方法应用于网络信息学的研究之中。

2.3 搜索引擎研究现状

自现代搜索引擎的鼻祖——Archie于1990年推出以来，搜索引擎因其隐含的巨大商业价值而得到迅猛发展。现阶段的搜索引擎有上千种之多，搜索结果排序[27]及搜索引擎评测[28]作为搜索引擎研究的两个主要方面历来是搜索引擎研究的重点。近年来，“以用户为中心”的服务理念的深入，使得对用户行为的研究成为搜索引擎新的研究热点。

在用户行为研究方面，王继民等对北京大学“天网”的用户点击记录进行研究，发现用户点击不同URL的数量遵从Heaps定律，点击URL的频度-频级服从类Zipf分布，点击URL与页面大小相关以及点击URL具有时间局部性[29]；余慧佳及岑荣伟等基于搜索引擎的用户行为日志对用户行为进行分析和研究，提出了一种自动进行搜索引擎性能评价的方法[30], 对改进搜索引擎的检索算法及搜索引擎算法优化与系统改进等均有较好的指导意义[31-32]；韩筱璞等对搜索引擎网站所公布的关键词搜索频率排行榜中的数据进行分析发现关键词搜索词频分布总体基本符合Zipf 定律且大多存在局部对Zipf 定律的分段符合。

从现阶段Zipf定律、网络信息计量学及搜索引擎等研究可以发现，在许多领域均得到广泛应用的Zipf定律在网络信息计量学中尚有很大的推广应用空间，即对Zipf定理在网络信息计量学尤其是其重要研究对象之一——搜索引擎中的研究与应用尚不深入。下面尝试将Zipf定律应用于搜索引擎中，提出搜索结果数目服从Zipf定律的猜想，并以实验验证该猜想，同时分析研究其对应的Zipf指数。

3 Zipf定律在网络信息计量学中的研究与应用

3.1 网络信息计量学中可能存在Zipf定律的猜想

搜索引擎是互联网信息的新的组织形式，其通过对用户输入的搜索关键字的分析将与搜索关键字最相关的信息返回给用户。对大部分输入而言，搜索引擎均能给出足够数量的结果，下面给出网络信息计量学中可能存在Zipf定律的猜想。

假设搜索关键字集合为{Qi,i=1, 2, …, m}，对任一搜索引擎SEj(j=1, 2, …, n)而言，搜索关键字Qi在时刻t的搜索结果数目为Num(Qi,SEj,t)，将在同一时刻t得到的k个搜索结果数目进行排序，则可以得到Num(Qi,SEj,t)(r)∝1/r,其中Num(Qi,SEj,t)(r)表示排名第r的搜索结果数目，在对数坐标系中，所有的点(r,Num(Qi,SEj,t)(r))近似分布在一条直线上，即存在如下的函数关系。

(1)

其中a为正常数，即为对应的Zipf系数。

上述猜想是对Zipf定律在搜索引擎结果中的应用与推广，由于搜索引擎的搜索范围基本涵盖全部互联网信息，采用搜索引擎结果作为类似于自然语言中的“词频”有一定的合理性与可行性。下面选用几个具有代表性的搜索引擎进行实验以验证该猜想。

3.2 实验方案

搜索关键字的选取比较困难，搜索引擎网站公布的关键词搜索频率排行榜更新频繁且数量过少，不宜选用为搜索关键字。由于Zipf定律来源于对自然语言领域中词频分布的分析，因此本文采用词语作为搜索关键字。另外，Zipf定律在中文词频分布中的适用性已得到验证，这里同样可以选用足够数量的中文词语作为搜索关键字进行实验。

在搜索词语方面，尽管Sogou等搜索引擎运营商提供有部分搜索词语数据集以供测试之用，如SogouQ等*http://www.sogou.com/labs/dl/q.html，但却并未提供搜索结果数量。再者，由于搜索结果的时效性，在现阶段采用搜索词语的历史记录进行搜索并对搜索结果进行分析不尽合理，因为热点话题会直接反应到搜索的查询词中以导致搜索结果数量出现较大的波动。

对提供中文搜索的搜索引擎而言，必须面对的一个问题是中文分词。现今的搜索引擎运营商或选取其他公司的产品作为分词工具或自行开发中文分词工具。Google的中文分词技术采用的是Basis Technology*http://www.basistech.com公司提供的中文分词技术，百度使用的是自己公司开发的分词技术，中搜使用的是海量科技*http://www.hylanda.com提供的分词技术。中文分词的准确度，与搜索引擎结果相关性和准确性有相当大的关系。所有的分词工具的共同点是必须提供足够数量的分词库，而分词工具的词库是作为搜索词语关键字的理想选择。这里，我们选用开源的IKAnalyzer*http://code.google.com/p/ik-analyzer/downloads/list中文分词工具提供的分词库，此处选用的版本为2012-u6，对应的基本分词库容量为275 714。

国内外的分析结构与评测机构，如Hitwise、Search Engine Watch等会定期或不定期的发布研究报告，公布各个搜索引擎的市场份额。现阶段全国搜索市场份额为： 百度65.7%，360综合搜索8.7%，搜狗6.2%，谷歌香港4.2%，百度图片3.9%，搜搜3.3%，谷歌(英文)1.7%，必应1.2%，谷歌中国0.5%，有道搜索0.5%*http://www.weste.net/2013/1-11/87960.html，这里选用排名前三位的搜索引擎——百度、360综合搜索及搜狗进行实验。

3.3 实验结果

搜索引擎在海量的互联网信息中搜索与查询关键字最相关的记录，除去敏感词汇及过于生僻的词语外均能给出足够数量的搜索结果。在实验中我们发现，在275 714个搜索关键字中，只有极个别的少数词语得不到结果，其余的均能得到较多的搜索结果。

图1、图2、图3分别是在对数坐标系中百度、360综合搜索及搜狗三大搜索引擎对275 714个搜索关键字返回的结果数目与其对应排名的点阵图。

图1 Baidu搜索结果数目

图2 So搜索结果数目

图3 Sogou搜索结果数目

上述三图可以发现，几乎所有的点都分布在一条直线上，采用IBM SPSS Statistics 20对上述数据进行拟合，可以得到如下的回归方程,如式(2)—(4)所示。

NumBaidu=181 048 778.2RankBaidu-0.003，R2=0.988

(2)

NumSo=130 814 766.2RankSo-0.003，R2=0.996

(3)

NumSogou=4 884 107.210RankSogou-3.035×10-5，R2=0.925

(4)

从回归结果可以看出，搜索结果数目与对应的排名之间存在极为显著的幂律分布关系，这很好地验证了上述猜想，证实了网络信息计量学中存在Zipf定律的结论。至于图形右端搜索结果数目的急剧下降是由于搜索结果数目的长尾分布造成的，这与自然语言领域的词频长尾分布类似。

此外，从上述搜索结果的点阵图还可以看出，搜索结果数量的排序有一定的周期性，这在图1及图2中表现得尤为显著，而且右端长尾明显降低。出现此种状况的主要原因在于对大部分搜索引擎而言，若搜索结果数量在1 000以上则是以千、万、十万、百万、千万、亿为单位度量的，若搜索结果数量在1 000以下则给出的是确切的数据，由于搜索结果数量的阶跃导致周期性的出现。图1及图2中的六个周期表明此阶段的Baidu及So搜索结果数量介于不同的区间且分别是以千、万、十万、百万、千万、亿为单位度量的，在对数坐标系中的区间长度也近似等同。至于图3，由于Sogou的搜索结果全部是以个为单位，故未出现与图1及图2类似的周期性现象。右端长尾明显降低的原因在于其对应的搜索结果数量不足1 000，故在对数坐标系中变化得较快。

需要说明的，由于搜索引擎存在定期或不定期的更新，上述分析结果随时间而略有波动，但由于所选用的搜索词有一定的代表性，且变化较小，搜索结果数量的总体趋势变化不大。由于各个搜索引擎运营商采用的搜索技术及侧重点不完全相同，导致对应的分析结果有一定的差距。从上述分析结果中也可以看出，Baidu与So搜索结果数目的Zipf系数相同，但Sogou却与上述二者差别较大。

尽管经典文献计量学的词频分布符合Zipf定律已有相关理论可以给出较合理的解释，如优先连接理论[33]及随机演化模型[34]等，但在网络信息中，词频数目的对数值仍然服从Zipf定律却似乎缺少合适的理论可以给出合理的解释。深入研究Zipf定律在信息计量学中的成因及在网络信息计量学中新形式的机理是后续研究的重点。

4 结束语

本文借鉴文献计量学中Zipf定律的思想，提出了在网络信息计量学中仍然符合Zipf定律的猜想，并采用公开的分词库在几个代表性的搜索引擎中得到验证，实验结果较好地验证了该猜想。同时，结合搜索引擎的特点及搜索结果数量的实际，对搜索结果也给出了合理的解释。后续工作的重点在于在更为广泛的范围内研究Zipf定律的普适性，包括经典的文献计量学理论与方法在网络信息计量学中的应用与推广，同时研究网络信息计量学中Zipf定律的形成原因等。

[1] 关毅, 王晓龙, 张凯. 现代汉语计算语言模型中语言单位的频度-频级关系[J]. 中文信息学报, 1999, 13(2): 8-15.

[2] 游荣彦. Zipf 定律与汉字字频分布. 中文信息学报[J], 2000, 14(3): 60-65.

[3] 王洋, 刘宇凡, 陈清华. 汉语言文学作品中词频的Zipf分布[J]. 北京师范大学学报(自然科学版), 2009, 45(4): 424-427.

[4] Jayaram B D, Vidya M N. Zipf’s law for Indian languages[J]. Journal of Quantitative Linguistics, 2008, 15(4): 293-17.

[5] Tuzzi A, Popescu I I, Altmann G. Zipf’s laws in Italian Texts[J]．Journal of Quantitative Linguistics, 2009, 16(4): 354-367.

[6] Alexander G, Grigori S. Zipf and Heaps Laws’ Coefficients Depend on Language[C]//Proceedings of the CICLing-2001, Mexico City, Mexico, 2001: 332-335.

[7] 韩定定, 马余刚. 原子核碎裂中可能存在Zipf定律[J]. 科学通报, 2000, 45: 913-918.

[8] Kali R. The city as a giant component: a random graph approach to Zipf’s law[J]. Applied Economics Letters, 2003, 10(11): 717-720(4).

[9] 李玉鑑, 肖创柏. 蛋白质序列中可能存在的Zipf定律[J]. 北京工业大学学报, 2005, 31(4): 366-368.

[10] 曹盼盼, 阎春宁. 人类通信模式的幂律分布和Zipf定律[J]. 复杂系统与复杂性科学, 2009, 6(4): 51-56.

[11] 王德进, 张社英, 刘源. 汉语言的几个统计规律[J]. 中文信息学报, 1987, 1(4): 33-39.

[12] 郑亚斌, 刘知远, 孙茂松. 中文歌词的统计特征及其检索应用[J]. 中文信息学报. 2007, 21(5): 61-67.

[13] 刘宇凡, 郭金忠, 陈清华. 唐代以来汉语文学作品中的字频演变[J]. 中文信息学报. 2011, 25(3): 93-97.

[14] Stanley M, Buldyrev S, Havlin S. Zipf’s plots and the size distribution of firms[J]. Economics Letters, 1995, 49: 453-457.

[15] Bruce M H. Zipf’s law and prior distributions for the composition of a population[J]. Journal of the American Statistical Association, 1970, 65: 1220-1232.

[16] Sornette D, Knopoff L, Kagan Y Y. Rank- ordering statistics of extreme events: Application to the distribution of large earthquakes[J]. Journal of Geophysical Research, 1996, 101(B6): 13883-13894.

[17] Han D D. Scale-free download network for publications, Chinese Physics Letter, 2004, 21: 1855-1857.

[18] Sornette D, Zajdenweber D. Economic returns of research: the Pareto law and its implications[J]. European Physical Journal B, 1998, 8: 653-664.

[19] Cai Biao, Chen Liangyin. Zipf’s Trust Discovery in Structured P2P Network[C]//Proceedings of the WKDD2010, 2010: 191-194.

[20] Hamoud M, Merouani H F. Detection of a Region of Interest in the Images Based on Zipf Laws[C]//Proceedings of the SITIS2011, 2011: 416-421.

[21] 薛飞. 中国城市规模的Zipf 法则检验及其影响因素[D]. 厦门: 厦门大学硕士学位论文, 2007.

[22] Almind T C, Lngwersen P. Informetric analyses on the World Wide Web： Methodological Approaches to “webometrics”[J]. Joumal of Documentation, 1997, 53(4): 404-426.

[23] Shi Longqing, Zhao Qingfeng. Data Sources of Webometrics[C]//Proceedings of the CIS2011, 2011： 1312-1315.

[24] 李静静, 闫宏飞. 中文网页信息检索测试集的构建、分析及应用[J]. 中文信息学报. 2008, 22(1): 30-36.

[25] Elgharabawy M A, Ayu M A. Web content accessibility and its relation to Webometrics ranking and search engines optimization[C]//Proceedings of the ICRIIS2011, 2011： 1-6.

[26] 何宇, 赵洪利, 杨海涛, 赵东杰. 复杂网络演化研究综述[J]. 装备指挥技术学院学报, 2011, 11(2): 120-125.

[27] 刘胜久, 李天瑞, 贾真, 尹红风. 元搜索引擎排序方法建模与算法研究[J]. 计算机科学, 2012, 39(11A): 197-199.

[28] 张伟哲, 张宏莉, 许笑, 何慧. 分布式搜索引擎系统效能建模与评价[J]. 软件学报, 2012, 23(2): 253-265.

[29] 王继民, 彭波. 搜索引擎用户点击行为分析[J]. 情报学报, 2006, 25(2): 154-162.

[30] 刘奕群, 岑荣伟, 张敏, 茹立云, 马少平. 基于用户行为分析的搜索引擎自动性能评价[J]. 软件学报, 2008, 19(11): 3023-3032.

[31] 余慧佳, 刘奕群, 张敏, 茹立云 ,马少平. 基于大规模日志分析的搜索引擎用户行为分析[J]. 中文信息学报, 2007, 21(1): 109-114.

[32] 岑荣伟, 刘奕群, 张敏, 茹立云, 马少平. 基于日志挖掘的搜索引擎用户行为分析[J]. 中文信息学报, 2010, 24(3): 49-54.

[33] Simon H A. On a class of skew distribution functions[J]. Biometrika, 1955, 42: 425-440.

[34] 姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型[J]. 物理学报, 2011, 60(5): 818-826.

Zipf’s Law and Webometrics

LIU Shengjiu1, LI Tianrui1, ZHU Jie1, 2

(1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu， Sichuan 611756, China;2. Research Center of Tibetan Information Technology Department of Computer Science,Tibetan University, Tibetan, Lhasa 850000, China)

Zipf’s Law has been applied widely in many fields as an important rule in bibliometrics. Webometrics has received much attention with the accelerated explosion of network information nowadays. We suggest that Zipf’s Law may exist in webometrics in the distribution of search result. We select the public word set and conduct experiments on several popular search engines. The experimental results confirm that the numbers of search results roughly conform to Zipf’s Law. The Zipf’s index of the numbers of search results of Baidu and So is 0.003.

Zipf’s law; Zipf’s index; search engine; webometrics

刘胜久(1988—),博士研究生,主要研究领域为数据挖掘与知识发现等。E-mail:liushengjiu2008@163.com李天瑞(1969—),博士,教授,博士生导师,主要研究领域为智能信息处理、数据挖掘和云计算等。E-mail:trli@swjtu.edu.cn珠杰(1973—),博士研究生,副教授,主要研究领域为藏文信息处理技术、数据挖掘等。E-mail:790139756@qq.com

1003-0077(2015)04-0089-06

2013-05-05 定稿日期： 2013-10-28

国家自然基金(61175047，61262058，61152001)；中国科学院自动化研究所复杂系统管理与控制重点实验室开放课题(20110102)

TP391

A