1、和我们主要研究方向关系较小的四个问题周涛电子科技大学,互联网科学中心zhutouustc.edu四个问题 信息传播和疾病传播的本质区别L. L, D.-B. Chen, T. Zhou, New J. Phys. 13 (2011) 123005 传播动力学点平均场近似的缺陷和改进Z. Yang, T. Zhou, arXiv: 1112.5683 人类行为的标度律源于周期或节律吗?Z. Yang, A.-X. Cui, T. Zhou, Physica A 390 (2011) 4543T. Zhou, Z.-D. Zhao, Z. Yang, C.-S. Zhou, EPL 97 (201
2、2) 18006 语言系统的标度律Z.-K. Zhang, L. L, J.-G. Liu, T. Zhou, EPJB 66 (2008) 557L. L, Z.-K. Zhang, T. Zhou, PLoS ONE 5 (2010) e14139L. L, Z.-K. Zhang, T. Zhou (unpublished)合作者： 赵志丹，陈端兵，吕琳媛，刘建国，周昌松，张子柯，杨紫陌，崔爱香想象信息传播和疾病传播的区别 信息传播活性随时间快速衰减，而疾病一般不会 信息传播中不同类型边不仅是传播力不同，传播的模式也不同，而疾病传播中接触强度只会造成传播概率差异 信息传播受到信息内容的重
3、大影响，每次传播激活的有效网络不同 信息传播中不同传播者的角色存在定性上的差异 信息传播具有记忆效应，以前的信息接触会产生影响 信息传播具有社会加强作用，譬如说一个谣言同时从两个地方听到，其说服力要高于从一个地方听到的两倍 信息传播中一条链接一般只使用一次 社会网络行为传播：一个间接暗示D. Centola, Science 2010一个简单模型异质网络的点平均场近似 假设节点上状态的分布只受到节点度的影响，在具有相同度的节点上各状态的分布是均匀的 是目前处理无标度网络动力学最常用的工具 不能刻画边上的异质性 对于某些具有自维持性质系统的热力学极限无法刻画 对于淬火系统中的动力学波动不能精确刻
4、画异质点平均场近似的缺陷克服缺陷的可能道路 完全在矩阵的层面上进行分析，这就是淬火系统的完整描述，但是目前只对阈值的计算有用，无法描述过程治本 从点到边，到三阶模体，到四阶模体治标网络模型为了完全去除度异质性的影响，我们考虑一个 随机规则网络，每个节点的度都一样，连接是完全随机的权重分布异质性降低传播速度大致思路考虑SS,SI,II三类边，利用权重分类，写成含时含权的马尔科夫转移方程 A是一个I节点下一时刻恢复成S节点的概率，B是一条SS的一个S端点下一个时步变成I节点的概率，C是一条SI的一个S端点下一个时步变成I节点的概率确定 权重异质性修正点边平均场的比较展望 在Voter Model,
5、 Evolutionary Game等动力学过程上开展应用 结合点的度异质性和边权分布的异质性，最终给出无标度含权异质网络上的动力学问题的平均场解 人类行为时间上的标度律群体层面幂律时间间隔分布的可能来源 每一个个体都符合幂律分布，且幂指数很集中 每一个个体都是泊松的，但是一阶矩各不相同，且抽样自一个均匀分布 这两种不同来源在群体层面统计上观察不出区别，但是对于动力学有不同的影响C.A. Hidalgo, Physica A 369 (2006) 877Z. Yang, A.-X. Cui, T. Zhou, Physica A 390 (2011) 4543周期和节律可能导致幂律时间间隔分布
6、，且可用周期级联泊松过程刻画 R. D. Malmgrena, D. B Stouffer, A. E. Motter, L. A. N. Amaral, PNAS 105 (2008) 18153.Y. Wu, C. Zhou, J.-H. Xiao, J. Kurths, H.J. Schellnhuber, PNAS 107 (2010) 18803.(i) 泊松个体，无周期性(ii) 泊松个体，有周期性(iii) 异质个体，无周期性(iv) 异质个体，有周期性理论模型结果理论模型结果真实数据结果真实数据结果Zipf定律是Zipf在1949年的一本关于人类定位的最小作用原理的书中首先提出
7、的，其中最令人难忘的例子是在人类语言中，如果以单词出现的频次将所有单词排序，用横坐标表示序号，纵坐标表示对应的频次，可以得到一条很好的向下的幂函数曲线。这个定律被发现适用于大量复杂系统。G. K. Zipf, Human behaviour and the principle of least effort (Addison-Wesly, 1949)Zi-Ke Zhang et al., EPJB 66 (2008) 557Adamic&Huberman, Glottometrics 3 (2002) 143S. K. Baek et al., PRE 76 (2007) 046113R. L
8、. Axtell, Science 293 (2001) 1818Furusawa&Kaneko, PRL 90 (2003) 088102Original oneZipf定律与幂函数律关系假设存在一个分布，可以用Zipf定律表达为( )Z rr其概率密度函数记为p(x)。如右图，考虑从r到r+r的一段，显然这部分数据点的数量是正比于r的。那么，这一段在Z(r)上的差值为11( )()Z rrrrrrrr 注意到这个差值反映在概率密度函数上就是x，所以我们可以得到一个关系式1()()( )()p rxp rZ rp rrr刚才我们已经说过了，这部分数据点的数量是正比于r的，所以说()p rxr
9、代到上面一个式子中，我们就可以得到 1()p rr因此，p(x)是一个幂函数，如果记( )p xx则可得1也就是11 H. S. Heaps. Information Retrieval: Computational and Theoretical Aspects (Academic Press, 1978) Heaps定律是Heaps在1978年一本关于信息挖掘的专著中提出的。事实上，他观察到在语言系统中，不同单词的数目与文本篇幅（所有出现的单词累积数目）之间存在亚线性的关系。如果用表示累积单词数，用N()表示不同单词的数目，Heaps定律可以表示为( )N其中是一个小于1的正数。与Zipf
10、定律受到广泛关注不同，Heaps定律基本只局限在语言系统中。M. A. Serran, A. Flammini, F. Menczer, arXiv: 0902.0606C. Cattuto, A. Barrat, A. Baldassarri, G. Schehr, V. Loreto, PNAS (2009, in press)Zi-Ke Zhang, Linyuan L, Jian-Guo Liu, Tao Zhou, EPJB 66 (2008) 557研究背景研究背景1 Zipf定律研究非常充分，实证结果丰富，且有多种机制上的解释 M. E. J. Newman, Contempor
11、ary Physics 46 (2005) 323 Heaps定律的实证研究主要集中在语言系统中，在其他系统中较少报道，最近一个有趣的例子是有机分子中的刚性链出现频次和增长同时符合Zipf定律和Heaps定律 R. W. Benz, S. J. Swamidass, P. Baldi, J. Chem. Inf. Model. 48 (2008) 1138 一些研究人员在一个系统中同时观察到了Zipf定律和Heaps定律，但是没有给出相应的解释。 Montemurro&Zanette, Glottometrics 4 (2002) 87 Gelbukh&Sidorov, LNCS 2004 (
12、2001) 332; R. W. Benz, S. J. Swamidass, P. Baldi, J. Chem. Inf. Model. 48 (2008) 1138 单独讨论Heaps产生机制的研究很少，一个特别的例子是最近的一篇论文用一个简单的随机游走模型给出了collaborative tagging系统中与给定tag同时出现的其他tags的增长符合Heaps定律，但是该解释很难推广到一般系统中。 C. Cattuto, A. Barrat, A. Baldassarri, G. Schehr, V. Loreto, PNAS (2009, in press)研究背景研究背景2 Za
13、nette和Montemurro利用一个Simon模型的变体，以Heaps定律为已知条件，可以推出Zipf定律，其中指数依赖于和模型的参数。 Zanette&Montemurro, J. Quant. Linguistics 12 (2005) 29 Serrano等人也是在一个随机过程的基础上，以Zipf定律为条件，推出Heaps定律，且得到当1是， =1/。 M. A. Serran, A. Flammini, F. Menczer, arXiv: 0902.0606 Baeza-Yates和Navarro利用较粗糙的数学分析方法，可以再不依赖于任何随机过程的基础上，从Zipf定律推出He
14、aps定律，且同样得到当1是， =1/。 Baeza-Yates&Navarro, J. Am. Soc. Inf. Sci. 51 (2000) 69 Leijenhorst和Weide用更精细的数学方法从Mandelbrot定律出发（ Mandelbrot定律也被叫做漂移幂函数律，Zipf定律是其特例）推导出了Zipf定律，且同样得到当1是， =1/。 Leijenhorst&Weide, Inf. Sci. 170 (2005) 263 以前研究工作认识上的不足 对Heaps定律的认识太狭窄，绝大部分研究只针对语言系统，实际上Heaps定律是一个非常普适的统计规律。 对于Heaps定律和
15、Zipf定律逻辑关系认识不明。 缺少对1的情况的分析，只可能受到Yule-Simon过程的影响，也可能受到数学上对于分布函数的严格定义的影响。 =1/的关系实际上只能刻画1或热力学极限下的渐近行为，在1附近且系统规模有限的时候并不成立。从从Zipf定律推导定律推导Heaps定律定律1( )p kBk( )Z rAr考虑一个离散的幂律分布，既可以写成一般概率密度的形式也可以写成Zipf定律的形式11 注意到Z(1)=A=kmax根据归一化条件max1( )d1kp kk 可以得到（要求不趋于1，这一点实际系统基本都满足）：从从Zipf定律推导定律推导Heaps定律定律2假设系统中有t个样本，包括
16、N(t)个不同值。不妨考虑为有N(t)个不同的单词，每个单词出现的频次不一样，但是累积频次（也称累积单词数，和不同单词数区分）为t。注意到序次号r还有一个意义，就是(r-1)正好是出现频次大于Z(r)的单词的数量，也就是说 往下推导：maxmax11max( )( )1max( ) ( )d( )(1)d( )( ) ( )(1)kkZ rZ rN t p kkN tkkN tZ rkN t krmax( )Z rkr11 消掉(r-1)，综合上面的结果，可以得到kmax的阶次max( )kN t从从Zipf定律推导定律推导Heaps定律定律3把累积频次用Z(r)展开，再连续化，可以得到：利用
17、上一页的结果：max( )AkN t可以得到：当明显大于1：111( )1( )(1)N tN tt当明显小于1：1( )1( )(1)N tN tt综合起来，这种方法似乎可以从Zipf定律推导Heaps定律，并得到在明显大于或小于1时的渐近行为，其指数关系为：遗憾的是Zipf定律原始的情况恰恰是 =11, 11, 1故事结束了吗？故事结束了吗？故事从故事从1的地方展开的地方展开在1的时候，原来的近似已经不能用了，但是可以引入新的近似：1( )( ); ( )1 (1)ln( )N tN tN tN t 于是得到( )ln( )N tN tt显然，当t趋于无穷大时，N(t)增长趋势是线性的，但
18、是光得到这种数学上漂亮的结果没有用，因为真实系统总是有限尺度的。事实上，N(t)的解可以写为：( )( )N tt W t其中W(t)便是著名的Lambert W 函数，满足方程：( )( )eW tW ttR. M. Corless et al., Adv. Comput. Maths. 5 (1996) 329于是，给定有限的t，我们便可以利用N(t)=t/W(t)的关系对有限系统进行数值分析。简单的数值分析结果简单的数值分析结果103104105102103104N(t)tSlope=0.881051071091011101310150.840.880.920.96t我们取t=10000
19、0，这是比较典型的真实系统的量级，利用该关系式可以得到，在1的位置，N(t)的增长可以看作近似符合Heaps定律，其指数为0.88从右图可以看到，Heaps定律的指数受文本总规模影响，但并不非常敏感。数值实验进行到了1016，这已经超出了我们遇到过的任何有实际意义的系统增长行为。1. Zipf定律推出Heaps定律这个说法只能在近似的意义下成立，但是这种近似相当好；2. 在Zipf指数靠近1附近时，渐近分析得到的Heaps定律的解误差很大；3. Heaps定律的指数不仅受到Zipf指数的影响，而且还受到系统规模的影响。小小 结结渐近解、数值解和随机过程模拟渐近解、数值解和随机过程模拟 以以t=
20、105为例为例真实数据对比真实数据分析，在真实数据分析，在35个数据集中胜出个数据集中胜出34个个工作价值工作价值 此工作有助于厘清关于Zipf定律和Heaps定律之间关系的认识Zipf定律几乎可以导致Heaps定律； 提高了在=1附近定量刻画两个定律之间关系的精度； 明确指明了系统尺度对Heaps指数的影响，与当前我们知道的一些实证结果吻合； 大大拓广了Heaps定律的适用范围； 为相关方面研究人员提供了大量的实证数据。四本书的实证：以字元为单位全新的观察现象理论模型与解析解结论+讨论 发现了以字元为单位的语言系统与一单词为单位的语言系统不同的统计规律 厘清和补充了以前不完整不准确的认识 凸显了有限选择的重要性 这是完全不同于BA网络那种线性增长，加速网络的Heaps增长的新问题 有限选择的效应无法通过类似于热力学极限或者相似方法驱除谢 谢
