從Zipf定律推導(dǎo)Heaps定律3課件

和我們主要研究方向關(guān)系較小的四個(gè)問題周濤電子科技大學(xué),互聯(lián)網(wǎng)科學(xué)中心zhutou@四個(gè)問題信息傳播和疾病傳播的本質(zhì)區(qū)別L.Lü,D.-B.Chen,T.Zhou,NewJ.Phys.13(2011)123005傳播動(dòng)力學(xué)點(diǎn)平均場近似的缺陷和改進(jìn)Z.Yang,T.Zhou,arXiv:1112.5683人類行為的標(biāo)度律源于周期或節(jié)律嗎?Z.Yang,A.-X.Cui,T.Zhou,PhysicaA390(2011)4543T.Zhou,Z.-D.Zhao,Z.Yang,C.-S.Zhou,EPL97(2012)18006語言系統(tǒng)的標(biāo)度律Z.-K.Zhang,L.Lü,J.-G.Liu,T.Zhou,EPJB66(2008)557L.Lü,Z.-K.Zhang,T.Zhou,PLoSONE5(2010)e14139L.Lü,Z.-K.Zhang,T.Zhou(unpublished)合作者：趙志丹，陳端兵，呂琳媛，劉建國，周昌松，張子柯，楊紫陌，崔愛香想象信息傳播和疾病傳播的區(qū)別信息傳播活性隨時(shí)間快速衰減，而疾病一般不會信息傳播中不同類型邊不僅是傳播力不同，傳播的模式也不同，而疾病傳播中接觸強(qiáng)度只會造成傳播概率差異信息傳播受到信息內(nèi)容的重大影響，每次傳播激活的有效網(wǎng)絡(luò)不同信息傳播中不同傳播者的角色存在定性上的差異信息傳播具有記憶效應(yīng)，以前的信息接觸會產(chǎn)生影響信息傳播具有社會加強(qiáng)作用，譬如說一個(gè)謠言同時(shí)從兩個(gè)地方聽到，其說服力要高于從一個(gè)地方聽到的兩倍信息傳播中一條鏈接一般只使用一次……社會網(wǎng)絡(luò)行為傳播：一個(gè)間接暗示D.Centola,Science2010一個(gè)簡單模型異質(zhì)網(wǎng)絡(luò)的點(diǎn)平均場近似假設(shè)節(jié)點(diǎn)上狀態(tài)的分布只受到節(jié)點(diǎn)度的影響，在具有相同度的節(jié)點(diǎn)上各狀態(tài)的分布是均勻的是目前處理無標(biāo)度網(wǎng)絡(luò)動(dòng)力學(xué)最常用的工具不能刻畫邊上的異質(zhì)性對于某些具有自維持性質(zhì)系統(tǒng)的熱力學(xué)極限無法刻畫對于淬火系統(tǒng)中的動(dòng)力學(xué)波動(dòng)不能精確刻畫異質(zhì)點(diǎn)平均場近似的缺陷克服缺陷的可能道路完全在矩陣的層面上進(jìn)行分析，這就是淬火系統(tǒng)的完整描述，但是目前只對閾值的計(jì)算有用，無法描述過程[治本]從點(diǎn)到邊，到三階模體，到四階模體……[治標(biāo)]網(wǎng)絡(luò)模型為了完全去除度異質(zhì)性的影響，我們考慮一個(gè)隨機(jī)規(guī)則網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的度都一樣，連接是完全隨機(jī)的權(quán)重分布異質(zhì)性降低傳播速度大致思路考慮SS,SI,II三類邊，利用權(quán)重分類，寫成含時(shí)含權(quán)的馬爾科夫轉(zhuǎn)移方程

A是一個(gè)I節(jié)點(diǎn)下一時(shí)刻恢復(fù)成S節(jié)點(diǎn)的概率，B是一條SS的一個(gè)S端點(diǎn)下一個(gè)時(shí)步變成I節(jié)點(diǎn)的概率，C是一條SI的一個(gè)S端點(diǎn)下一個(gè)時(shí)步變成I節(jié)點(diǎn)的概率確定權(quán)重異質(zhì)性修正點(diǎn)邊平均場的比較展望在VoterModel,EvolutionaryGame等動(dòng)力學(xué)過程上開展應(yīng)用結(jié)合點(diǎn)的度異質(zhì)性和邊權(quán)分布的異質(zhì)性，最終給出無標(biāo)度含權(quán)異質(zhì)網(wǎng)絡(luò)上的動(dòng)力學(xué)問題的平均場解人類行為時(shí)間上的標(biāo)度律群體層面冪律時(shí)間間隔分布的可能來源每一個(gè)個(gè)體都符合冪律分布，且冪指數(shù)很集中每一個(gè)個(gè)體都是泊松的，但是一階矩各不相同，且抽樣自一個(gè)均勻分布這兩種不同來源在群體層面統(tǒng)計(jì)上觀察不出區(qū)別，但是對于動(dòng)力學(xué)有不同的影響C.A.Hidalgo,PhysicaA369(2006)877Z.Yang,A.-X.Cui,T.Zhou,PhysicaA390(2011)4543周期和節(jié)律可能導(dǎo)致冪律時(shí)間間隔分布，且可用周期級聯(lián)泊松過程刻畫

R.D.Malmgrena,D.BStouffer,A.E.Motter,L.A.N.Amaral,PNAS105(2008)18153.Y.Wu,C.Zhou,J.-H.Xiao,J.Kurths,H.J.Schellnhuber,PNAS

107(2010)18803.(i)泊松個(gè)體，無周期性(ii)泊松個(gè)體，有周期性(iii)異質(zhì)個(gè)體，無周期性(iv)異質(zhì)個(gè)體，有周期性理論模型結(jié)果真實(shí)數(shù)據(jù)結(jié)果Zipf定律是Zipf在1949年的一本關(guān)于人類定位的最小作用原理的書中首先提出的，其中最令人難忘的例子是在人類語言中，如果以單詞出現(xiàn)的頻次將所有單詞排序，用橫坐標(biāo)表示序號，縱坐標(biāo)表示對應(yīng)的頻次，可以得到一條很好的向下的冪函數(shù)曲線。這個(gè)定律被發(fā)現(xiàn)適用于大量復(fù)雜系統(tǒng)。G.K.Zipf,Humanbehaviourandtheprincipleofleasteffort(Addison-Wesly,1949)Zi-KeZhangetal.,EPJB66(2008)557Adamic&Huberman,Glottometrics3(2002)143S.K.Baeketal.,PRE76(2007)046113R.L.Axtell,Science293(2001)1818Furusawa&Kaneko,PRL90(2003)088102OriginaloneZipf定律與冪函數(shù)律關(guān)系假設(shè)存在一個(gè)分布，可以用Zipf定律表達(dá)為其概率密度函數(shù)記為p(x)。如右圖，考慮從r到r+δr的一段，顯然這部分?jǐn)?shù)據(jù)點(diǎn)的數(shù)量是正比于δr的。那么，這一段在Z(r)上的差值為注意到這個(gè)差值反映在概率密度函數(shù)上就是δx，所以我們可以得到一個(gè)關(guān)系式剛才我們已經(jīng)說過了，這部分?jǐn)?shù)據(jù)點(diǎn)的數(shù)量是正比于δr的，所以說代到上面一個(gè)式子中，我們就可以得到因此，p(x)是一個(gè)冪函數(shù)，如果記則可得也就是H.S.Heaps.InformationRetrieval:ComputationalandTheoreticalAspects(AcademicPress,1978)

Heaps定律是Heaps在1978年一本關(guān)于信息挖掘的專著中提出的。事實(shí)上，他觀察到在語言系統(tǒng)中，不同單詞的數(shù)目與文本篇幅（所有出現(xiàn)的單詞累積數(shù)目）之間存在亞線性的關(guān)系。如果用τ表示累積單詞數(shù)，用N(τ)表示不同單詞的數(shù)目，Heaps定律可以表示為其中λ是一個(gè)小于1的正數(shù)。與Zipf定律受到廣泛關(guān)注不同，Heaps定律基本只局限在語言系統(tǒng)中。M.A.Serran,A.Flammini,F.Menczer,arXiv:0902.0606C.Cattuto,A.Barrat,A.Baldassarri,G.Schehr,V.Loreto,PNAS(2009,inpress)Zi-KeZhang,LinyuanLü,Jian-GuoLiu,TaoZhou,EPJB66(2008)557研究背景1Zipf定律研究非常充分，實(shí)證結(jié)果豐富，且有多種機(jī)制上的解釋

M.E.J.Newman,ContemporaryPhysics46(2005)323

Heaps定律的實(shí)證研究主要集中在語言系統(tǒng)中，在其他系統(tǒng)中較少報(bào)道，最近一個(gè)有趣的例子是有機(jī)分子中的剛性鏈出現(xiàn)頻次和增長同時(shí)符合Zipf定律和Heaps定律

R.W.Benz,S.J.Swamidass,P.Baldi,J.Chem.Inf.Model.48(2008)1138一些研究人員在一個(gè)系統(tǒng)中同時(shí)觀察到了Zipf定律和Heaps定律，但是沒有給出相應(yīng)的解釋。Montemurro&Zanette,Glottometrics4(2002)87

Gelbukh&Sidorov,LNCS2004(2001)332;

R.W.Benz,S.J.Swamidass,P.Baldi,J.Chem.Inf.Model.48(2008)1138單獨(dú)討論Heaps產(chǎn)生機(jī)制的研究很少，一個(gè)特別的例子是最近的一篇論文用一個(gè)簡單的隨機(jī)游走模型給出了collaborativetagging系統(tǒng)中與給定tag同時(shí)出現(xiàn)的其他tags的增長符合Heaps定律，但是該解釋很難推廣到一般系統(tǒng)中。

C.Cattuto,A.Barrat,A.Baldassarri,G.Schehr,V.Loreto,PNAS(2009,inpress)研究背景2Zanette和Montemurro利用一個(gè)Simon模型的變體，以Heaps定律為已知條件，可以推出Zipf定律，其中指數(shù)α依賴于λ和模型的參數(shù)。

Zanette&Montemurro,J.Quant.Linguistics12(2005)29Serrano等人也是在一個(gè)隨機(jī)過程的基礎(chǔ)上，以Zipf定律為條件，推出Heaps定律，且得到當(dāng)α>1是，λ=1/α。

M.A.Serran,A.Flammini,F.Menczer,arXiv:0902.0606Baeza-Yates和Navarro利用較粗糙的數(shù)學(xué)分析方法，可以再不依賴于任何隨機(jī)過程的基礎(chǔ)上，從Zipf定律推出Heaps定律，且同樣得到當(dāng)α>1是，λ=1/α。Baeza-Yates&Navarro,J.Am.Soc.Inf.Sci.51(2000)69Leijenhorst和Weide用更精細(xì)的數(shù)學(xué)方法從Mandelbrot定律出發(fā)（Mandelbrot定律也被叫做漂移冪函數(shù)律，Zipf定律是其特例）推導(dǎo)出了Zipf定律，且同樣得到當(dāng)α>1是，λ=1/α。

Leijenhorst&Weide,Inf.Sci.170(2005)263

以前研究工作認(rèn)識上的不足對Heaps定律的認(rèn)識太狹窄，絕大部分研究只針對語言系統(tǒng)，實(shí)際上Heaps定律是一個(gè)非常普適的統(tǒng)計(jì)規(guī)律。對于Heaps定律和Zipf定律邏輯關(guān)系認(rèn)識不明。缺少對α<1的情況的分析，只可能受到Y(jié)ule-Simon過程的影響，也可能受到數(shù)學(xué)上對于分布函數(shù)的嚴(yán)格定義的影響。λ=1/α的關(guān)系實(shí)際上只能刻畫α<<1或

α>>1或熱力學(xué)極限下的漸近行為，在1附近且系統(tǒng)規(guī)模有限的時(shí)候并不成立。從Zipf定律推導(dǎo)Heaps定律1考慮一個(gè)離散的冪律分布，既可以寫成一般概率密度的形式也可以寫成Zipf定律的形式注意到Z(1)=A=kmax根據(jù)歸一化條件可以得到（要求β不趨于1，這一點(diǎn)實(shí)際系統(tǒng)基本都滿足）：從Zipf定律推導(dǎo)Heaps定律2假設(shè)系統(tǒng)中有t個(gè)樣本，包括N(t)個(gè)不同值。不妨考慮為有N(t)個(gè)不同的單詞，每個(gè)單詞出現(xiàn)的頻次不一樣，但是累積頻次（也稱累積單詞數(shù)，和不同單詞數(shù)區(qū)分）為t。注意到序次號r還有一個(gè)意義，就是(r-1)正好是出現(xiàn)頻次大于Z(r)的單詞的數(shù)量，也就是說往下推導(dǎo)：消掉(r-1)，綜合上面的結(jié)果，可以得到kmax的階次從Zipf定律推導(dǎo)Heaps定律3把累積頻次用Z(r)展開，再連續(xù)化，可以得到：利用上一頁的結(jié)果：可以得到：當(dāng)α明顯大于1：當(dāng)α明顯小于1：綜合起來，這種方法似乎可以從Zipf定律推導(dǎo)Heaps定律，并得到α在明顯大于或小于1時(shí)的漸近行為，其指數(shù)關(guān)系為：遺憾的是Zipf定律原始的情況恰恰是α=1故事結(jié)束了嗎？故事從α→1的地方展開在α→1的時(shí)候，原來的近似已經(jīng)不能用了，但是可以引入新的近似：于是得到顯然，當(dāng)t趨于無窮大時(shí)，N(t)增長趨勢是線性的，但是光得到這種數(shù)學(xué)上漂亮的結(jié)果沒有用，因?yàn)檎鎸?shí)系統(tǒng)總是有限尺度的。事實(shí)上，N(t)的解可以寫為：其中W(t)便是著名的LambertW函數(shù)，滿足方程：R.M.Corlessetal.,Adv.Comput.Maths.5(1996)329于是，給定有限的t，我們便可以利用N(t)=t/W(t)的關(guān)系對有限系統(tǒng)進(jìn)行數(shù)值分析。簡單的數(shù)值分析結(jié)果我們?nèi)=100000，這是比較典型的真實(shí)系統(tǒng)的量級，利用該關(guān)系式可以得到，在α→1的位置，N(t)的增長可以看作近似符合Heaps定律，其指數(shù)為0