yanxy-中國高等科學技術中心

1、“復雜網(wǎng)絡論壇圈”博文大賽參賽博文為什么網(wǎng)絡會加速增長?,閆小勇yanxy@sjzri.edu.cn石家莊鐵道大學 交通運輸學院,第六屆全國網(wǎng)絡科學論壇 暨 第二屆全國混沌應用研討會,——網(wǎng)絡加速增長現(xiàn)象的經(jīng)濟學解釋及仿真分析,報告提綱,一、網(wǎng)絡加速增長現(xiàn)象二、加速增長現(xiàn)象的經(jīng)濟學解釋三、網(wǎng)絡加速演化模型及其仿真分析四、結(jié)論與問題,一、網(wǎng)絡加速增長現(xiàn)象,表現(xiàn)：平均度隨時間增加（邊比節(jié)點的增速更快）加速增長是實際網(wǎng)絡演化中

2、的普遍現(xiàn)象已有數(shù)十類網(wǎng)絡被證實具有加速增長特性（因特網(wǎng)、萬維網(wǎng)、引文網(wǎng)、語言網(wǎng)、科學家合作網(wǎng)絡、生物代謝網(wǎng)絡、蛋白質(zhì)作用網(wǎng)絡……）,科學家合作網(wǎng) Barabási et al. 2002,因特網(wǎng)（AS層） Faloutsos et al. 1999,,網(wǎng)絡加速增長的兩種方式,該圖引自： Sen，PRE , 2004,方式a：邊只在新老節(jié)點之間產(chǎn)生，適用于描述引文網(wǎng)絡等少數(shù)網(wǎng)絡（但目前被研究得更多）；方式b：邊

3、可以在老節(jié)點內(nèi)部產(chǎn)生，符合大多數(shù)實際網(wǎng)絡的增長情況（目前尚未受到廣泛關注） 。,從邊增加的視角理解網(wǎng)絡加速增長,在網(wǎng)絡“年輕”時，邊更多地是以連接新節(jié)點的形式增加；隨著網(wǎng)絡年齡的增長，越來越多的邊會在老節(jié)點之間產(chǎn)生；相對于邊增加的速度，網(wǎng)絡節(jié)點增加的速度越來越慢，網(wǎng)絡呈現(xiàn)邊加速增長的趨勢。,,,,,,,,,,,,,,,二、網(wǎng)絡加速增長現(xiàn)象的經(jīng)濟學解釋,為什么一些實際的網(wǎng)絡會有前述這種“初期節(jié)點增速快，后期邊增速快”的規(guī)律？本文嘗試用

4、經(jīng)濟學中的效用理論來解釋這一現(xiàn)象產(chǎn)生的原因。微觀經(jīng)濟學中的效用是用來描述消費品對消費者需求滿足程度的一個概念。根據(jù)效用最大化原理和隨機效用原理，效用越大的消費品被選擇的概率也越大。,邊際效用遞減理論：在消費者連續(xù)消費某種消費品時，隨著所消費的該消費品的數(shù)量增加，其總效用雖然相應增加，但消費品的邊際效用（每消費一次所帶來的效用增量）有遞減趨勢。,邊際效用遞減導致網(wǎng)絡加速增長,如果我們認為網(wǎng)絡是自組織的，那么可以把網(wǎng)絡自身理解為一個消費者

5、，把網(wǎng)絡演化過程中邊的增加理解為一次消費行為，而把邊連接新節(jié)點還是老節(jié)點理解為兩種消費品。在網(wǎng)絡增加邊的一次“消費行為”中，是選擇連接新節(jié)點還是選擇連接老節(jié)點，取決于這二者中的哪個會帶給網(wǎng)絡自身更大的“效用”。而根據(jù)邊際效用遞減理論，隨著網(wǎng)絡中邊數(shù)量的增加，連接新節(jié)點帶給網(wǎng)絡的效用會越來越小。因此，網(wǎng)絡會越來越不傾向于連接新節(jié)點，而是傾向于在老節(jié)點之間建立連接，網(wǎng)絡將呈現(xiàn)出邊加速增長的趨勢。,對一些實際網(wǎng)絡的解釋,公交網(wǎng)絡：

6、 圖片來源：http://openbusmap.org科學家合作網(wǎng)絡： 圖片來源：http://www.commetrix.de,三、網(wǎng)絡加速演化模型及其仿真分析,根據(jù)以上討論，本文構(gòu)造了一個網(wǎng)絡演化模型來模擬網(wǎng)絡加速增長的過程。它按照如下規(guī)則生成一個網(wǎng)絡：Step 1：初始化，令演化時刻 t = 0，創(chuàng)建一個包含n個節(jié)

7、點(n≥2)的完全圖；Step 2：生成一個包含n個節(jié)點(n≥2)的完全圖，以正比于θ(t) 的概率選擇 m 個新節(jié)點(0 < θ(t) < 1 ，且θ(t)是一個減函數(shù))，其余 n-m 個節(jié)點從現(xiàn)有網(wǎng)絡中按正比于節(jié)點度k 的概率選擇（即擇優(yōu)連接）；Step 3：令t = t+1，返回Step 2，直到 t = T （給定的最大步長）。,對模型的一些說明,(1) 以完全圖作為網(wǎng)絡增長的基本單元更符合合作網(wǎng)絡演化的實際情

8、況如果n=2 ，則每步演化加入的是一條邊，可以描述一些非合作網(wǎng)絡的加速增長。(2) 邊際效用遞減律體現(xiàn)在函數(shù)θ(t) 中0< θ(t) ≤1 ，且θ(t)是一個減函數(shù)可根據(jù)網(wǎng)絡增長特性取線性、指數(shù)、冪函數(shù)等多種形式(3) 模型的兩個特例θ(t) 為常數(shù)時，退化為RDP 模型 (Ramasco et al，2004) n=2 且θ(t) =0.5時，退化為BA模型(Barabási et al , 1999)

9、,模型度分布的初步解析,如果θ(t) 為定值（與時間無關），則可用率方程解析得到網(wǎng)絡的節(jié)點度分布為：上式為漂移冪律分布（Chang et al，2007），度分布指數(shù)（隨θ 的減?。? ∞ 到 -2 變化。如果θ(t) 隨時間遞減，尚無法求得解析解，后面將給出度分布的仿真分析結(jié)果。,模型的仿真分析,設定 n = 10, ，每演化100步，對網(wǎng)絡的主要拓撲性質(zhì)進行一次統(tǒng)

10、計，結(jié)果見下表：,特征：平均度隨時間增加，平均距離隨時間下降，平均群聚系數(shù)隨時間下降*無論θ(t) 取線性、指數(shù)還是冪函數(shù)形式，均會出現(xiàn)這一規(guī)律,與科學家合作網(wǎng)實證數(shù)據(jù)的對比,,① 平均度隨時間增加 ② 平均距離隨時間下降③ 平均群聚系數(shù)隨時間下降,數(shù)學領域（M）和神經(jīng)科學領域（NS）科學家合作網(wǎng)從1991年到1998年的主要拓撲特征變化情況（圖引自： Barabási et al. Physica A, 2002）,與

11、城市公交網(wǎng)絡實證數(shù)據(jù)的對比,,城市公交線網(wǎng)拓撲特征統(tǒng)計（石家莊市1996-2008 ，每4年統(tǒng)計一次）,石家莊市公交網(wǎng)絡的平均度隨演化時間增加而增加，平均群聚系數(shù)下降，與模型仿真結(jié)果相吻合。但網(wǎng)絡的平均距離卻也隨演化時間增加，這可能是由于公交網(wǎng)絡演化受空間距離約束，缺乏長程連接所導致的結(jié)果。,模型與實際網(wǎng)絡度分布的對比,仿真模型的節(jié)點累積度分布,石家莊市公交網(wǎng)絡站點累積度分布,數(shù)學領域（M）和神經(jīng)科學領域（NS）科學家合作網(wǎng)度分布（

12、Barabási et al. 2002 ）,四、結(jié)論與問題,結(jié)論：用經(jīng)濟學中的效用理論解釋網(wǎng)絡加速增長現(xiàn)象產(chǎn)生的可能原因，認為若自組織網(wǎng)絡增加節(jié)點的邊際效用是遞減的，則網(wǎng)絡自身對效用最大化的追求會驅(qū)動網(wǎng)絡加速增長。揭示了導致網(wǎng)絡加速增長的一種可能機制。構(gòu)建了一種加速增長的合作網(wǎng)絡演化模型，仿真分析結(jié)果表明，該模型能夠再現(xiàn)實際網(wǎng)絡加速增長的現(xiàn)象，一些關鍵拓撲性質(zhì)與實證數(shù)據(jù)能夠較好地吻合。,需進一步研究的問題,(1) 對

13、模型網(wǎng)絡的拓撲性質(zhì)進行精確解析由于θ(t) 隨時間遞減，這一點并不容易做到……(2) 邊際效用遞減現(xiàn)象能否自發(fā)出現(xiàn)？本文模型的邊際效用遞減規(guī)則是人為設定的，能否構(gòu)造一種模型，使網(wǎng)絡自發(fā)出現(xiàn)邊際效用遞減現(xiàn)象？(3)各種實際網(wǎng)絡增長速度的評價與調(diào)控增長速度如何影響網(wǎng)絡效率……如何優(yōu)化或引導網(wǎng)絡保持合理增速……,謝 謝！請各位老師、同學批評指導！,閆小勇yanxy@sjzri.edu.cn石家莊鐵道大學 交通運輸學院,第