網(wǎng)絡(luò)數(shù)學(xué)建模與交通流

1、 復(fù)雜網(wǎng)絡(luò)數(shù)學(xué)建模與交通流周 濤 中國(guó)科技大學(xué)，近代物理系 Chapter I復(fù)雜網(wǎng)絡(luò)演化機(jī)制Outline 復(fù)雜網(wǎng)絡(luò)研究現(xiàn)狀概述 國(guó)內(nèi)的情況 什么是網(wǎng)絡(luò)？ 典型網(wǎng)絡(luò)的主要統(tǒng)計(jì)特征與物理意義 更加深入細(xì)致的統(tǒng)計(jì)特性 重要的模型介紹 復(fù)雜網(wǎng)絡(luò)上的數(shù)學(xué)模型國(guó)內(nèi)主要研究小組 陳關(guān)榮范正平流動(dòng)訪問(wèn)學(xué)者（香港城市大學(xué)） 汪小帆李翔方錦清呂金虎（上交，中科院） 何大韌（揚(yáng)州大學(xué)）* 狄增如樊瑛鄭志剛李夢(mèng)輝（北師大）* 李春光張洪斌（電子科大） 朱陳平古志鳴（南航）* 馬志明耿顯明（中科院，南航） 許伯銘K. P. Chan（香港中文大學(xué)）* 朱建陽(yáng)朱涵（北師大，南大） 史定華（上海大學(xué)） 章忠志（大連理工

2、）* 劉宗華（華東師范） 蔡勖（華中師范）(William R. Cheswick)(Stephen G. Eick)網(wǎng)絡(luò)最基本的幾個(gè)概念i節(jié)點(diǎn)的度節(jié)點(diǎn)的度ki5簇系數(shù)簇系數(shù)(clustering coefficient): 朋友之間相互是朋友的概率朋友之間相互是朋友的概率節(jié)點(diǎn)簇系數(shù)節(jié)點(diǎn)簇系數(shù)Ci2/10=0.2j距離？距離？dij=3規(guī)則網(wǎng)絡(luò)大的簇系數(shù)大的簇系數(shù)大的平均距大的平均距離離單點(diǎn)度分布單點(diǎn)度分布有限維晶格網(wǎng)絡(luò)，超立方體網(wǎng)絡(luò)等等有限維晶格網(wǎng)絡(luò)，超立方體網(wǎng)絡(luò)等等J.-M. Xu, Topological Structure and Analysis of Interconnection

3、Network, Kluwer Academic, Dordrecht, 2001.隨隨 機(jī)機(jī) 網(wǎng)網(wǎng) 絡(luò)絡(luò)小小 的的 簇簇 系系 數(shù)數(shù)小小 的的 平平 均均 距距 離離泊泊 松松 分分 布布Watts-Strogatz網(wǎng)絡(luò)網(wǎng)絡(luò)以很小的概率以很小的概率p斷鍵重?cái)噫I重連連簇系數(shù)依然很簇系數(shù)依然很大大平均距離變得很平均距離變得很小小指數(shù)分布指數(shù)分布D. J. Watts and S. H. Strogatz, Nature London 393, 440, 1998.M. E. J. Newman and D. J. Watts, Phys. Lett. A 263, 341,1999.Baraba

4、si-Albert網(wǎng)絡(luò)網(wǎng)絡(luò)每個(gè)時(shí)步增加一個(gè)節(jié)點(diǎn)每個(gè)時(shí)步增加一個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)按線性偏好連接每個(gè)節(jié)點(diǎn)按線性偏好連接Power-law 度分度分布布P(k) k-短的平均距離短的平均距離小的簇系數(shù)小的簇系數(shù)(lnN)2/NA.-L. Barabsi and R. Albert, Science 286, 509 1999.各種網(wǎng)絡(luò)主要拓?fù)涮卣饕挥[各種網(wǎng)絡(luò)主要拓?fù)涮卣饕挥[平均距離簇系數(shù)度分布規(guī)則網(wǎng)絡(luò)大大Delta函數(shù)ER隨機(jī)網(wǎng)絡(luò)小小泊松分布WS小世界網(wǎng)絡(luò) 小大指數(shù)分布BA無(wú)標(biāo)度網(wǎng)絡(luò)小小冪率分布部分部分真實(shí)網(wǎng)絡(luò)小大近似冪率分布Question 1如何構(gòu)造同時(shí)滿足如何構(gòu)造同時(shí)滿足三個(gè)統(tǒng)計(jì)特性的簡(jiǎn)三個(gè)統(tǒng)計(jì)特

5、性的簡(jiǎn)單優(yōu)美的網(wǎng)絡(luò)模型單優(yōu)美的網(wǎng)絡(luò)模型更加深入細(xì)致 的統(tǒng)計(jì)特性度度- -度相關(guān)性度相關(guān)性度很大的節(jié)點(diǎn)到底是傾向于和度大度很大的節(jié)點(diǎn)到底是傾向于和度大的節(jié)點(diǎn)相連還是和度小的節(jié)點(diǎn)相連？的節(jié)點(diǎn)相連還是和度小的節(jié)點(diǎn)相連？正相關(guān)正相關(guān)負(fù)相關(guān)負(fù)相關(guān)M. E. J. Newman, Phys. Rev. Lett. 87, 208701(2002)W. -X. Wang, B. Hu, T. Zhou, B. -H. Wang and Y. -B. Xie,arXiv: cond-mat/0504062 (submitted to Phys. Rev. E)Question 2為什么社會(huì)網(wǎng)絡(luò)是正相為什么社會(huì)

6、網(wǎng)絡(luò)是正相關(guān)，而技術(shù)生物網(wǎng)絡(luò)是關(guān)，而技術(shù)生物網(wǎng)絡(luò)是負(fù)相關(guān)的？如何構(gòu)建正負(fù)相關(guān)的？如何構(gòu)建正相關(guān)的無(wú)標(biāo)度網(wǎng)絡(luò)？相關(guān)的無(wú)標(biāo)度網(wǎng)絡(luò)？簇簇- -度相關(guān)性度相關(guān)性好萊塢演員網(wǎng)絡(luò)好萊塢演員網(wǎng)絡(luò)英文單詞網(wǎng)絡(luò)英文單詞網(wǎng)絡(luò)在只有拓?fù)涞木W(wǎng)絡(luò)中，簇度往往是負(fù)相關(guān)的；在只有拓?fù)涞木W(wǎng)絡(luò)中，簇度往往是負(fù)相關(guān)的；在考慮幾何的網(wǎng)絡(luò)中，簇度往往是不相關(guān)的。在考慮幾何的網(wǎng)絡(luò)中，簇度往往是不相關(guān)的。E. Ravasz and A.-L Barabasi, Phys. Rev. E 67, 026112(2003)Question 3幾何性質(zhì)與簇度相關(guān)性幾何性質(zhì)與簇度相關(guān)性之間的關(guān)系到底是什么之間的關(guān)系到底是什么網(wǎng)絡(luò)中的群落（網(wǎng)絡(luò)中

7、的群落（community）M. Girvan and M. E. J. Newman, PNAS 99, 7821(2002)Question 4網(wǎng)絡(luò)中群落結(jié)構(gòu)的形成網(wǎng)絡(luò)中群落結(jié)構(gòu)的形成是外生原因還是內(nèi)生原是外生原因還是內(nèi)生原因，如果是內(nèi)生原因，因，如果是內(nèi)生原因，這個(gè)機(jī)制到底是什么？這個(gè)機(jī)制到底是什么？其 他 超家族分類(lèi) 定點(diǎn)強(qiáng)度（strength）冪率分布 Strength-Degree冪率相關(guān)性 后代規(guī)模分布 合作規(guī)模分布 定點(diǎn)項(xiàng)目度分布與度分布的一致性問(wèn)題 特征值譜 一些著名的模型 Krapivsky非線性BA模型 Holme-Kim可調(diào)簇系數(shù)模型 Klemm高集聚網(wǎng)絡(luò)模型 Doro

8、govtsev-Mendes老化網(wǎng)絡(luò)模型 Sen距離偏好模型 BBV含權(quán)網(wǎng)絡(luò)模型 等等等等等等等等等等等等Holme-Kim可調(diào)簇系數(shù)模型在優(yōu)先連接的同時(shí)在優(yōu)先連接的同時(shí)以一定的概率連接以一定的概率連接被選中節(jié)點(diǎn)的鄰居被選中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)度分布依然是冪指數(shù)為節(jié)點(diǎn)度分布依然是冪指數(shù)為-3的冪率分的冪率分布布簇系數(shù)變得很大（解析結(jié)果簇系數(shù)變得很大（解析結(jié)果PRE 67, 056102）平均距離依然很小平均距離依然很小P. Holme and B. J. Kim, Phys. Rev. E 65, 066109 2002.Dorogovtsev-Mendes老化網(wǎng)絡(luò)模型老化：真實(shí)網(wǎng)絡(luò)中不可避免的現(xiàn)象

9、老化：真實(shí)網(wǎng)絡(luò)中不可避免的現(xiàn)象Klemm K and Eguiluz V M 2002 Phys. Rev. E 65 036123老化模型的基本框架老化模型的基本框架連接概率不僅連接概率不僅與節(jié)點(diǎn)的度與節(jié)點(diǎn)的度k有關(guān)，還與節(jié)點(diǎn)的年齡有關(guān)有關(guān)，還與節(jié)點(diǎn)的年齡有關(guān)不考慮年齡則退化為不考慮年齡則退化為BA模型。不同的模型模型。不同的模型有不同的老化函數(shù)有不同的老化函數(shù) 其中最有名的是其中最有名的是DMDorogovtsev S N and Mendes J F F 2000 Phys. Rev. E 62 1842參數(shù) 取值范圍冪指數(shù) 0 2 3 0 1 3 1指數(shù)分布，鏈狀結(jié)構(gòu)主要的有關(guān)老化網(wǎng)絡(luò)

10、的文獻(xiàn) Amaral L A N, Scala A, Barthelemy M and Stanley H E 2000 Proc. Natl. Acad. Sci. U.S.A. 97 11149 Klemm K and Eguiluz V M 2002 Phys. Rev. E 65 036123 Zhu H, Wang X R and Zhu J Y 2003 Phys. Rev. E 68 056121 Dorogovtsev S N and Mendes J F F 2000 Phys. Rev. E 62 1842 Jiang P Q, Wang B H, Zhou T et al

11、, 2005 Chin. Phys. Lett. 22 1285Sen距離偏好模型在很多實(shí)際網(wǎng)絡(luò)中，距離因素是必在很多實(shí)際網(wǎng)絡(luò)中，距離因素是必須考慮的，例如須考慮的，例如Internet和電力網(wǎng)等和電力網(wǎng)等BA模型模型Sen模型模型S. S. Manna and P. Sen, Phys. Rev. E 66, 066114(2002)S. S. Manna, G. Mukherjee and P. Sen, Phys. Rev. E69, 017102(2004)主要結(jié)論：存在一個(gè)閾值，當(dāng)主要結(jié)論：存在一個(gè)閾值，當(dāng) 大于該值時(shí)大于該值時(shí)度分布是冪率的，反之度分布是指數(shù)的。度分布是冪率的，反之

12、度分布是指數(shù)的。我自己的一些工作整數(shù)網(wǎng)絡(luò)T. Zhou et al, arXiv: cond-mat/0405258 合作網(wǎng)絡(luò)模型T. Zhou, Y. -D. Jin et al, arXiv: cond-mat/0502253隨機(jī)阿波羅網(wǎng)絡(luò)與單純形網(wǎng)絡(luò)T. Zhou, et al, Phys. Rev. E 71, 046141T. Zhou, G. Yan, et al, arXiv:cond-mat/0409414Z. -M. Gu, T. Zhou, et al, arXiv: cond-mat/0505175生長(zhǎng)老化模型P. -Q. Jiang, B. -H. Wang, T. Z

13、hou, et al, Chin. Phys. Lett. 22 1285握手模型含權(quán)合作網(wǎng)絡(luò)自組織無(wú)標(biāo)度網(wǎng)絡(luò)高聚簇?zé)o標(biāo)度的多樣性網(wǎng)絡(luò)整數(shù)網(wǎng)絡(luò)模型整數(shù)網(wǎng)絡(luò)模型規(guī)則：規(guī)則：1到到N之間的合數(shù)，如果有整除之間的合數(shù)，如果有整除關(guān)系就連一條邊，只考慮最大連通分支關(guān)系就連一條邊，只考慮最大連通分支N30的情的情況，最大連況，最大連通分支有通分支有15個(gè)節(jié)點(diǎn)和個(gè)節(jié)點(diǎn)和19條邊條邊主要結(jié)論 簇系數(shù)比BA網(wǎng)絡(luò)大，且隨著N的變化是穩(wěn)定的，大約在0.34左右 度分布是由指數(shù)為2的冪率分布（出度）和亂七八糟單的分布（入度）組合而成，數(shù)值上可以看作近似與指數(shù)2.4的冪率 直徑有一個(gè)常數(shù)上界！ 簇度相關(guān)性C(k)1/

14、k有意思的地方 很簡(jiǎn)單，沒(méi)有超過(guò)高中的數(shù)學(xué) 畢達(dá)哥拉斯的理念 既是模型又是實(shí)證 直徑的常數(shù)上界一個(gè)新的網(wǎng)絡(luò)類(lèi) 環(huán)與理想，各種各樣的數(shù)學(xué)對(duì)象隨機(jī)阿波羅網(wǎng)絡(luò)隨機(jī)阿波羅網(wǎng)絡(luò)Chapter II復(fù)雜網(wǎng)絡(luò)上的交通問(wèn)題動(dòng)力學(xué)問(wèn)題 傳播動(dòng)力學(xué)（SIR,SIS,SI） 網(wǎng)絡(luò)同步與控制 自旋相互作用（Iring, XY臨界模型） 級(jí)聯(lián)動(dòng)力學(xué) 交通流與信息流 網(wǎng)絡(luò)導(dǎo)航 網(wǎng)絡(luò)上的博弈問(wèn)題（囚徒博弈、爭(zhēng)當(dāng)少數(shù)者博弈，退出者博弈） 復(fù)雜網(wǎng)絡(luò)上的交通流交通流理論，已經(jīng)在自然科學(xué)與經(jīng)濟(jì)社會(huì)的許多領(lǐng)域，特別是公路網(wǎng)上的車(chē)輛流問(wèn)題和計(jì)算機(jī)互聯(lián)網(wǎng)上的信息流問(wèn)題上，有著廣泛而深入的應(yīng)用。近年來(lái)關(guān)于復(fù)雜網(wǎng)絡(luò)方面的研究表明，計(jì)算機(jī)互聯(lián)網(wǎng)具有無(wú)標(biāo)度特性，不能用簡(jiǎn)單的規(guī)則網(wǎng)絡(luò)模型或ER隨機(jī)網(wǎng)絡(luò)模型模擬。因此，討論網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)其上交通動(dòng)力學(xué)行為的影響是非常有意義的。 什么是交通流交通是指人,物以及思想,信息的地點(diǎn)間移動(dòng).因此交通流的研究對(duì)象是廣泛的!交通流研究可以屬于廣義傳播范疇,它包括信息流,粒子流,車(chē)輛流,顆粒流等等. 物理學(xué)家感興趣的部分包括:交通系統(tǒng)的動(dòng)力學(xué)行為:相變與自組織臨界性.災(zāi)難救