用最大等级法测定幂律.pdfVIP

( ) 第 24 卷第 5 期 总第 149 期 　　　　 　 　系　统　工　程 V o l. 24, N o. 5 2006 年 5 月　　　　　　　　　 　 　 　 Sy stem s Eng ineer ing M ay. , 2006　 ( ) 文章编号: 100 14098 2006 050 12205 用最大等级法测定幂律 1 1 2 孙　颖 , 刘小冬 , 王　羽 ( 1. 西北工业大学 数学与信息科学系, 陕西 西安　7 10072; 2. 西北大学 计算机科学系, 陕西 西安　7 10 127) 摘　要: 幂律是无标度网络的基础, 但它的测定不只是统计节点度的频数那么简单, 这种做法可能导致错误的 结论, 譬如本文图2 (A ) (B ) , 此外频数法的拟合误差不容忽视。本文设计了一种高精度的方法——最大等级 法, 并证明它是判定整数型大样本幂律随机量的充要条件。我们以平均相对误差为主要评价指标, 在相同条 件下比较了多种方法, 发现最大等级法的平均相对误差最低, 只有 0. 11% , 而频数法却有 5. 5 1%. 关键词: 复杂网络; 幂律; 频数法; 最大等级法; 平均相对误差 中图分类号:N 94; O 173　　　文献标识码: A 1　引言 2　最大等级法的原理 自B arabási 和A lbert 提出无标度网络以来, 幂律在 人们对幂律的关注远早于无标度网络的出现。1906 复杂科学中的地位异常突出[ 1, 4, 10, 13 ] 。人们发现, 诸如 年, P areto 提出用于描述国民收入不均衡性的 P areto 分 [8 ]、 [2, 6 ]、遗传网络[ 11]、科学引文网[ 16 ] 等很多 布[ 15 ] , 其密度函数为 ( ) : - - 1 , 它就是幂律的连续形 In tern et WWW p x x 自然的或人造的系统等都体现幂律。如何验证测量值满足 式。1929 年, 发现[ 18 ] 英语单词的频数 与其顺序 之 Zip f f r r 幂律, 及怎样准确估计幂指数, 是一个很基础但往往容易 间成反比关系 : - 。 不很严密地证明这两个分 f r r A dam ic 被忽视的问题。最简单的方法就是计算待测量的频数, 在 [2 ] 布实际上拥有相同的分布函数 :