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

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

2、）* 劉宗華（華東師范） 蔡勖（華中師范）(William R. Cheswick)(Stephen G. Eick)網(wǎng)絡(luò)最基本的幾個概念i節(jié)點的度節(jié)點的度ki5簇系數(shù)簇系數(shù)(clustering coefficient): 朋友之間相互是朋友的概率朋友之間相互是朋友的概率節(jié)點簇系數(shù)節(jié)點簇系數(shù)Ci2/10=0.2j距離？距離？dij=3規(guī)則網(wǎng)絡(luò)大的簇系數(shù)大的簇系數(shù)大的平均距大的平均距離離單點度分布單點度分布有限維晶格網(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.隨隨 機機 網(wǎng)網(wǎng) 絡(luò)絡(luò)小小 的的 簇簇 系系 數(shù)數(shù)小小 的的 平平 均均 距距 離離泊泊 松松 分分 布布Watts-Strogatz網(wǎng)絡(luò)網(wǎng)絡(luò)以很小的概率以很小的概率p斷鍵重斷鍵重連連簇系數(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ò)每個時步增加一個節(jié)點每個時步增加一個節(jié)點每個節(jié)點按線性偏好連接每個節(jié)點按線性偏好連接Power-law 度分度分布布P(k) k-短的平均距離短的平均距離小的簇系數(shù)小的簇系數(shù)(lnN)2/NA.-L. Barabsi and R. Albert, Science 286, 509 1999.各種網(wǎng)絡(luò)主要拓撲特征一覽各種網(wǎng)絡(luò)主要拓撲特征一覽平均距離簇系數(shù)度分布規(guī)則網(wǎng)絡(luò)大大Delta函數(shù)ER隨機網(wǎng)絡(luò)小小泊松分布WS小世界網(wǎng)絡(luò) 小大指數(shù)分布BA無標度網(wǎng)絡(luò)小小冪率分布部分部分真實網(wǎng)絡(luò)小大近似冪率分布Question 1如何構(gòu)造同時滿足如何構(gòu)造同時滿足三個統(tǒng)計特性的簡三個統(tǒng)計特

5、性的簡單優(yōu)美的網(wǎng)絡(luò)模型單優(yōu)美的網(wǎng)絡(luò)模型更加深入細致 的統(tǒng)計特性度度- -度相關(guān)性度相關(guān)性度很大的節(jié)點到底是傾向于和度大度很大的節(jié)點到底是傾向于和度大的節(jié)點相連還是和度小的節(jié)點相連？的節(jié)點相連還是和度小的節(jié)點相連？正相關(guān)正相關(guān)負相關(guān)負相關(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為什么社會網(wǎng)絡(luò)是正相為什么社會

6、網(wǎng)絡(luò)是正相關(guān)，而技術(shù)生物網(wǎng)絡(luò)是關(guān)，而技術(shù)生物網(wǎng)絡(luò)是負相關(guān)的？如何構(gòu)建正負相關(guān)的？如何構(gòu)建正相關(guān)的無標度網(wǎng)絡(luò)？相關(guān)的無標度網(wǎng)絡(luò)？簇簇- -度相關(guān)性度相關(guān)性好萊塢演員網(wǎng)絡(luò)好萊塢演員網(wǎng)絡(luò)英文單詞網(wǎng)絡(luò)英文單詞網(wǎng)絡(luò)在只有拓撲的網(wǎng)絡(luò)中，簇度往往是負相關(guān)的；在只有拓撲的網(wǎng)絡(luò)中，簇度往往是負相關(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)生原因，這個機制到底是什么？這個機制到底是什么？其 他 超家族分類 定點強度（strength）冪率分布 Strength-Degree冪率相關(guān)性 后代規(guī)模分布 合作規(guī)模分布 定點項目度分布與度分布的一致性問題 特征值譜 一些著名的模型 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)先連接的同時在優(yōu)先連接的同時以一定的概率連接以一定的概率連接被選中節(jié)點的鄰居被選中節(jié)點的鄰居節(jié)點度分布依然是冪指數(shù)為節(jié)點度分布依然是冪指數(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ò)模型老化：真實網(wǎng)絡(luò)中不可避免的現(xiàn)象

9、老化：真實網(wǎng)絡(luò)中不可避免的現(xiàn)象Klemm K and Eguiluz V M 2002 Phys. Rev. E 65 036123老化模型的基本框架老化模型的基本框架連接概率不僅連接概率不僅與節(jié)點的度與節(jié)點的度k有關(guān)，還與節(jié)點的年齡有關(guān)有關(guān)，還與節(jié)點的年齡有關(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、的文獻 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距離偏好模型在很多實際網(wǎng)絡(luò)中，距離因素是必在很多實際網(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é)論：存在一個閾值，當(dāng)主要結(jié)論：存在一個閾值，當(dāng) 大于該值時大于該值時度分布是冪率的，反之度分布是指數(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隨機阿波羅網(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生長老化模型P. -Q. Jiang, B. -H. Wang, T. Z

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

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