yanxy-中國(guó)高等科學(xué)技術(shù)中心

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

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

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

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

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

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

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

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

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

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

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

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

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