復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型什么是網(wǎng)絡(luò)? 網(wǎng)絡(luò):一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.互為朋友的人互相鏈接的計(jì)算機(jī)互相指向的網(wǎng)頁互相作用的蛋白質(zhì)2書籍能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進(jìn)復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型什么是網(wǎng)絡(luò)? 網(wǎng)絡(luò):一什么是網(wǎng)絡(luò)? 網(wǎng)絡(luò):一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.互為朋友的人互相鏈接的計(jì)算機(jī)互相指向的網(wǎng)頁互相作用的蛋白質(zhì)2什么是網(wǎng)絡(luò)? 網(wǎng)絡(luò):一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.2圖在數(shù)學(xué)世界,網(wǎng)絡(luò)被稱作圖,實(shí)體被稱作結(jié)點(diǎn),而它們之間的鏈接被稱作邊。關(guān)于圖的理論研究開始于18世紀(jì)，由數(shù)學(xué)家歐拉提出康尼斯堡橋梁問題在那之后圖被更廣泛深入地研究.

3圖在數(shù)學(xué)世界,網(wǎng)絡(luò)被稱作圖,實(shí)體被稱作結(jié)點(diǎn),而它們之間過去的網(wǎng)絡(luò)圖在過去被用作為現(xiàn)有網(wǎng)絡(luò)制作模型(舉例來說.有公交網(wǎng)絡(luò),社會(huì)網(wǎng)絡(luò))通常這些網(wǎng)絡(luò)都很小網(wǎng)絡(luò)可以通過目視檢查進(jìn)行研究從而可以發(fā)現(xiàn)大量信息4過去的網(wǎng)絡(luò)圖在過去被用作為現(xiàn)有網(wǎng)絡(luò)制作模型(舉例來說.有現(xiàn)在的網(wǎng)絡(luò)更多的、更大型的網(wǎng)絡(luò)出現(xiàn)了科技進(jìn)步的產(chǎn)物例如：互聯(lián)網(wǎng)，網(wǎng)頁我們收集更多、更好、更復(fù)雜數(shù)據(jù)的能力例如：基因調(diào)控網(wǎng)絡(luò)由數(shù)以千計(jì)、數(shù)以萬計(jì)甚至數(shù)以億計(jì)的結(jié)點(diǎn)所組成的網(wǎng)絡(luò)不可能形象化5現(xiàn)在的網(wǎng)絡(luò)更多的、更大型的網(wǎng)絡(luò)出現(xiàn)了5因特網(wǎng)地圖6因特網(wǎng)地圖6因特網(wǎng)7因特網(wǎng)7網(wǎng)絡(luò)的類型社會(huì)網(wǎng)絡(luò)知識(信息)網(wǎng)絡(luò)科學(xué)網(wǎng)絡(luò)生物網(wǎng)絡(luò)8網(wǎng)絡(luò)的類型社會(huì)網(wǎng)絡(luò)8社會(huì)網(wǎng)絡(luò)鏈接表示社會(huì)中的互動(dòng)熟人的網(wǎng)絡(luò)協(xié)作網(wǎng)絡(luò)演員的網(wǎng)絡(luò)合作作者的網(wǎng)絡(luò)導(dǎo)演的網(wǎng)絡(luò)電話呼叫網(wǎng)絡(luò)e-mail網(wǎng)絡(luò)IM網(wǎng)絡(luò)藍(lán)牙網(wǎng)絡(luò)性網(wǎng)絡(luò)主頁/博客網(wǎng)絡(luò)9社會(huì)網(wǎng)絡(luò)鏈接表示社會(huì)中的互動(dòng)9知識（信息）網(wǎng)絡(luò)結(jié)點(diǎn)代表信息,鏈接是信息的聯(lián)系引文網(wǎng)絡(luò)(有向無循環(huán)的)網(wǎng)絡(luò)(有向的)點(diǎn)對點(diǎn)網(wǎng)絡(luò)詞網(wǎng)絡(luò)基于信任的網(wǎng)絡(luò)圖形軟件10知識（信息）網(wǎng)絡(luò)結(jié)點(diǎn)代表信息,鏈接是信息的聯(lián)系10科學(xué)網(wǎng)絡(luò)為商品分配所建的網(wǎng)絡(luò)互聯(lián)網(wǎng)路由器標(biāo)準(zhǔn),AS標(biāo)準(zhǔn)能量格航班網(wǎng)絡(luò)電話網(wǎng)絡(luò)交通網(wǎng)絡(luò)公路，鐵路，行人交通11科學(xué)網(wǎng)絡(luò)為商品分配所建的網(wǎng)絡(luò)11生物網(wǎng)絡(luò)網(wǎng)絡(luò)代表生物系統(tǒng)蛋白質(zhì)相互作用網(wǎng)絡(luò)基因調(diào)控網(wǎng)絡(luò)基因共同表達(dá)網(wǎng)絡(luò)代謝路徑食物網(wǎng)神經(jīng)網(wǎng)絡(luò)12生物網(wǎng)絡(luò)網(wǎng)絡(luò)代表生物系統(tǒng)12理解大型的圖關(guān)于現(xiàn)實(shí)生活網(wǎng)絡(luò)的數(shù)據(jù)有哪些？?我們可以解釋網(wǎng)絡(luò)是怎樣產(chǎn)生的嗎？13理解大型的圖關(guān)于現(xiàn)實(shí)生活網(wǎng)絡(luò)的數(shù)據(jù)有哪些？?13關(guān)于網(wǎng)絡(luò)性質(zhì)的研究1999年左右WattsandStrogatz,Dynamicsandsmall-worldphenomenon（動(dòng)力學(xué)和小世界現(xiàn)象）Faloutsos3,Onpower-lawrelationshipsoftheInternetTopology（基于權(quán)利-法律關(guān)系的互聯(lián)網(wǎng)拓?fù)洌㎏leinbergetal.,TheWebasagraph（作為一張圖的互聯(lián)網(wǎng)）BarabasiandAlbert,Theemergenceofscalinginrealnetworks（現(xiàn)實(shí)網(wǎng)絡(luò)中標(biāo)度的出現(xiàn)）14關(guān)于網(wǎng)絡(luò)性質(zhì)的研究1999年左右14現(xiàn)實(shí)網(wǎng)絡(luò)的性質(zhì)大多數(shù)結(jié)點(diǎn)只有少數(shù)的鄰居(度),但也有一些結(jié)點(diǎn)有很高的度數(shù)(度的冪律分布)無標(biāo)度網(wǎng)絡(luò)如果一個(gè)結(jié)點(diǎn)x

連接著y和z,那么y

和z

就很可能是連接的高聚類系數(shù)大多數(shù)結(jié)點(diǎn)平均只相距幾條邊的距離小世界網(wǎng)絡(luò)各個(gè)不同領(lǐng)域的網(wǎng)絡(luò)(從因特網(wǎng)到生物網(wǎng)絡(luò))有著相同的性質(zhì)是否有可能有一個(gè)統(tǒng)一的基本生成過程？15現(xiàn)實(shí)網(wǎng)絡(luò)的性質(zhì)大多數(shù)結(jié)點(diǎn)只有少數(shù)的鄰居(度),但也有一些小世界網(wǎng)絡(luò)例如：六度分離理論但是有超過六十億人口生存在這個(gè)世界上！16小世界網(wǎng)絡(luò)例如：六度分離理論但是有超過六十億人口生存在這個(gè)世小世界網(wǎng)絡(luò)(a)蛋白質(zhì)(b)神經(jīng)元(c)互聯(lián)網(wǎng)17小世界網(wǎng)絡(luò)(a)蛋白質(zhì)(b)神經(jīng)元(c)互生成隨機(jī)圖經(jīng)典圖形理論模型(Erd?s-Renyi)每條邊的獨(dú)立產(chǎn)生概率為P很好的研究模型，但是:大多數(shù)頂點(diǎn)的度大致上相同兩個(gè)結(jié)點(diǎn)相連的概率與它們是否共有一個(gè)鄰居結(jié)點(diǎn)無關(guān)平均路徑短18生成隨機(jī)圖經(jīng)典圖形理論模型(Erd?s-Renyi)18現(xiàn)實(shí)網(wǎng)絡(luò)建?，F(xiàn)實(shí)生活網(wǎng)絡(luò)不是隨機(jī)的我們是否可以定義一個(gè)模型，它能夠產(chǎn)生與現(xiàn)實(shí)生活中相似的具有統(tǒng)計(jì)性能的圖?一系列關(guān)于隨機(jī)圖的模型19現(xiàn)實(shí)網(wǎng)絡(luò)建?，F(xiàn)實(shí)生活網(wǎng)絡(luò)不是隨機(jī)的19網(wǎng)絡(luò)的作用過程理解網(wǎng)絡(luò)的結(jié)構(gòu)為什么重要?流行病學(xué):病毒在無標(biāo)度網(wǎng)絡(luò)中傳播地更快隨機(jī)接種疫苗的結(jié)點(diǎn)無法正常工作，但有針對性的疫苗接種是非常有效的20網(wǎng)絡(luò)的作用過程理解網(wǎng)絡(luò)的結(jié)構(gòu)為什么重要?20網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)21網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)21網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)VS無標(biāo)度網(wǎng)絡(luò)22網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)VS無標(biāo)度網(wǎng)絡(luò)22網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)23網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)23網(wǎng)絡(luò)搜索第一代搜索引擎:萬維網(wǎng)只是作為一個(gè)文件的集合因?yàn)槔]件發(fā)送者，無實(shí)質(zhì)內(nèi)容的、非結(jié)構(gòu)化的、以與無人監(jiān)管的內(nèi)容，增加了萬維網(wǎng)的規(guī)模第二代搜索引擎:作為一個(gè)網(wǎng)絡(luò)的萬維網(wǎng)應(yīng)用鏈接描述文字技術(shù)以用來標(biāo)注好的網(wǎng)頁應(yīng)該被更多的網(wǎng)頁指向好的網(wǎng)頁應(yīng)該被更多的好網(wǎng)頁指向PageRank算法,Google!24網(wǎng)絡(luò)搜索第一代搜索引擎:萬維網(wǎng)只是作為一個(gè)文件的集合24萬維網(wǎng)萬維網(wǎng)是一個(gè)文件之間互相指向的網(wǎng)絡(luò)結(jié)點(diǎn)指網(wǎng)頁而邊指網(wǎng)頁間的鏈接邊是有指向的：鏈接可以從它們出發(fā)或者到達(dá)它們25萬維網(wǎng)萬維網(wǎng)是一個(gè)文件之間互相指向的網(wǎng)絡(luò)25萬維網(wǎng)26萬維網(wǎng)26網(wǎng)絡(luò)的未來網(wǎng)絡(luò)現(xiàn)在看上去是這樣的越來越多系統(tǒng)被網(wǎng)絡(luò)模型化不同學(xué)科的科學(xué)家致力于對網(wǎng)絡(luò)的研究(物理學(xué)家,計(jì)算機(jī)學(xué)家,數(shù)學(xué)家,生物學(xué)家,社會(huì)學(xué)家,經(jīng)濟(jì)學(xué)家)還有許多問題尚未被理解.27網(wǎng)絡(luò)的未來網(wǎng)絡(luò)現(xiàn)在看上去是這樣的27數(shù)學(xué)工具圖理論概率論線性代數(shù)28數(shù)學(xué)工具圖理論28圖理論GraphG=(V,E)V=頂點(diǎn)的集合E=邊的集合12345無向圖E={(1,2),(1,3),(2,3),(3,4),(4,5)}29圖理論GraphG=(V,E)12345無向圖29圖理論GraphG=(V,E)V=頂點(diǎn)的集合E=邊的集合12345有向圖E={?1,2?,?2,1?

?1,3?,?3,2?,?3,4?,?4,5?}30圖理論GraphG=(V,E)12345有向圖30無向圖12345結(jié)點(diǎn)i的度數(shù)dd(i)與結(jié)點(diǎn)i相連的邊數(shù)度序列[d(i),d(2),d(3),d(4),d(5)][2,2,2,1,1]度分布[(1,2),(2,3)]31無向圖12345結(jié)點(diǎn)i的度數(shù)dd(i)度序列度分布3有向圖12345結(jié)點(diǎn)i的入度指向結(jié)點(diǎn)i的邊數(shù)結(jié)點(diǎn)i的出度以結(jié)點(diǎn)i為起始點(diǎn)的邊數(shù)入度序列[1,2,1,1,1]出度序列[2,1,2,1,0]32有向圖12345結(jié)點(diǎn)i的入度結(jié)點(diǎn)i的出度入度序列32路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑:一段連續(xù)的邊(有向或無向從結(jié)點(diǎn)i到結(jié)點(diǎn)j的連接)路徑長度:路徑上的邊數(shù)結(jié)點(diǎn)i和結(jié)點(diǎn)j是相連的循環(huán):一段初始和結(jié)束結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)的路徑123451234533路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑:一段連續(xù)的邊(有向或無向從結(jié)最短路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑也被稱作BFS路徑,或短線程路徑123451234534最短路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑123451234534直徑途中距離最長的一條最短路徑123451234535直徑途中距離最長的一條最短路徑123451234535無向圖12345連通圖:任意兩個(gè)結(jié)點(diǎn)都存在連接的圖非連通圖:一個(gè)無連接的圖連通區(qū)域:包含相連頂點(diǎn)的子圖36無向圖12345連通圖:任意兩個(gè)結(jié)點(diǎn)都存在連接的圖36完全連通圖CliqueKn一個(gè)最多有n(n-1)/2條邊的圖（n為頂點(diǎn)數(shù)）1234537完全連通圖CliqueKn1234537連通圖12345強(qiáng)連通圖:任意兩個(gè)頂點(diǎn)之間存在一條路徑弱連通圖:邊沒有指向時(shí)圖就是連通的38連通圖12345強(qiáng)連通圖:任意兩個(gè)頂點(diǎn)之間存在一條路徑弱連子圖12345子圖:給定V’

V,E’E,圖

G’=(V’,E’)就是G的一個(gè)子圖.生成子圖:給定V’

V,E’E是V’中結(jié)點(diǎn)連成的邊的集合.則圖G’=(V’,E’),是G的一個(gè)生成子圖39子圖12345子圖:給定V’V,E’E,3樹沒有循環(huán)的無向連通圖1234540樹沒有循環(huán)的無向連通圖1234540二分圖集合V可以被分割成兩個(gè)集合L和R的圖,而所有的邊由L和R的結(jié)點(diǎn)連接而成，在集合L和R內(nèi)部不存在邊。41二分圖集合V可以被分割成兩個(gè)集合L和R的圖,而所有的邊由L線性代數(shù)鄰接矩陣對稱矩陣的無向圖1234542線性代數(shù)鄰接矩陣1234542線性代數(shù)鄰接矩陣非對稱矩陣的無向圖1234543線性代數(shù)鄰接矩陣1234543特征值與特征向量若值λ是矩陣A的特征值，且存在不為零向量的向量X，使得,Ax=λx.向量x是矩陣A的一個(gè)特征向量最大的特征向量被稱為主特征值對應(yīng)的特征向量被稱為主特征向量對應(yīng)最大值方向的變動(dòng)44特征值與特征向量若值λ是矩陣A的特征值，且存在不為零向量的特征值45特征值45隨機(jī)游動(dòng)從一個(gè)結(jié)點(diǎn)開始,它的連接結(jié)點(diǎn)一律是隨機(jī)的。平穩(wěn)分布:你訪問結(jié)點(diǎn)i次數(shù)的分?jǐn)?shù),隨著隨機(jī)游動(dòng)經(jīng)過邊數(shù)的增逐漸加接近無窮大如果一個(gè)圖是強(qiáng)連通圖,它的平穩(wěn)分布收斂與一個(gè)唯一的一個(gè)向量。46隨機(jī)游動(dòng)從一個(gè)結(jié)點(diǎn)開始,它的連接結(jié)點(diǎn)一律是隨機(jī)的。46隨機(jī)游動(dòng)平穩(wěn)分布:標(biāo)準(zhǔn)鄰接矩陣左邊的主特征向量x=xP無向圖的度分布1234547隨機(jī)游動(dòng)平穩(wěn)分布:標(biāo)準(zhǔn)鄰接矩陣左邊的主特征向量123454概率論概率空間:給定一對?Ω,P?Ω:樣本空間P:Ω的子集的測量概率隨機(jī)變量X:Ω→R概率分布函數(shù)P[X=x]數(shù)學(xué)期望48概率論概率空間:給定一對?Ω,P?48隨機(jī)圖的類隨機(jī)圖的類被定義為一對?Gn,P?

，Gn

是所有大小為n的圖的集合,P

是集合Gn的概率分布Erd?s-Renyi圖:每條邊出現(xiàn)的概率為p當(dāng)

p=1/2時(shí),我們得到一個(gè)統(tǒng)一的分布49隨機(jī)圖的類隨機(jī)圖的類被定義為一對?Gn,P?，Gn是漸近符號對于兩個(gè)函數(shù)f(n)和g(n)若存在正數(shù)c

和N,使得f(n)≤cg(n),

則對于所有的n≥N，有f(n)=O(g(n))

若存在正數(shù)c

和N,使得f(n)≥cg(n),

則對于所有的n≥N，有f(n)=Ω(g(n))

若f(n)=O(g(n))并且f(n)=Ω(g(n))，則有f(n)=Θ(g(n))若limf(n)/g(n)=0,則隨著n→∞，有f(n)=o(g(n))

若limf(n)/g(n)=∞,

則隨著n→∞，有f(n)=ω(g(n))50漸近符號對于兩個(gè)函數(shù)f(n)和g(n)50P

與NPP:在多項(xiàng)式時(shí)間內(nèi)可以得到解決的一類問題NP:在多項(xiàng)式時(shí)間內(nèi)可以得到驗(yàn)證的一類問題NP-hard:至少與NP中任何問題一樣困難的問題51P與NPP:在多項(xiàng)式時(shí)間內(nèi)可以得到解決的一類問題51近似算法NP-優(yōu)化問題:給定一個(gè)問題的實(shí)例,找到一個(gè)能將目標(biāo)函數(shù)最小化或最大化的解決方法。算法A

是一個(gè)問題的系數(shù)c的近似值,若對于每一個(gè)輸入值x

A(x)≤cOPT(x)(最小化問題)

A(x)≥cOPT(x)(最大化問題)52近似算法NP-優(yōu)化問題:給定一個(gè)問題的實(shí)例,找到一個(gè)能將復(fù)雜網(wǎng)絡(luò)的實(shí)際應(yīng)用維基百科F.Colaiori,V.Servedio,G.Caldarelli,交流物理學(xué)部.,“LaSapienza”,羅馬(意大利)D.Donato,S.Leonardi計(jì)算機(jī)科學(xué)學(xué)部.,“LaSapienza”,羅馬(意大利)L.SaleteBuriol計(jì)算機(jī)科學(xué)學(xué)部.,UniversityofPortoAlegre,RioGrandedoSul(巴西)53復(fù)雜網(wǎng)絡(luò)的實(shí)際應(yīng)用維基百科F.Colaiori,V維基百科的復(fù)雜網(wǎng)絡(luò)網(wǎng)絡(luò)描述維基百科的統(tǒng)計(jì)分析模型與解釋54維基百科的復(fù)雜網(wǎng)絡(luò)網(wǎng)絡(luò)描述54555556565757維基百科是怎樣工作的？多虧了維基科技,一個(gè)用戶可以

增加新的條目到百科全書中

修改已存在條目的內(nèi)容

修改其鏈接在萬維網(wǎng)中，每個(gè)用戶只對從他的網(wǎng)頁發(fā)出的指令負(fù)責(zé)

58維基百科是怎樣工作的？多虧了維基科技,一個(gè)用戶可以58維基百科中的結(jié)點(diǎn)與邊網(wǎng)絡(luò)的邊是百科全書的條目邊是條目間的引用59維基百科中的結(jié)點(diǎn)與邊網(wǎng)絡(luò)的邊是百科全書的條目59統(tǒng)計(jì)特性條目的數(shù)目在時(shí)間內(nèi)成倍增長60統(tǒng)計(jì)特性條目的數(shù)目在時(shí)間內(nèi)成倍增長60度分布61度分布61優(yōu)先連接為了研究優(yōu)先連接,我們采用了由紐曼(2001)提出的方法

，建立一個(gè)直方圖，頂點(diǎn)的度的(k)

，每次獲得新的邊的階數(shù)t，通過一個(gè)系數(shù)n(k,t)/N(t)衡量它的貢獻(xiàn),其中:N(t)

是第t次結(jié)點(diǎn)的數(shù)量n(k,t)

是第t次度為k的結(jié)點(diǎn)的數(shù)量若(k)

有一個(gè)approximatedly線性行為,則我們可能因此可以得出存在優(yōu)先連接的結(jié)論62優(yōu)先連接為了研究優(yōu)先連接,我們采用了由紐曼(2001)提出優(yōu)先連接圓:英語三角:葡萄牙語填充:入度白色:出度63優(yōu)先連接圓:英語63維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量1.概率為R1的邊從新結(jié)點(diǎn)出發(fā)并指向一個(gè)已存在的結(jié)點(diǎn)，而這個(gè)結(jié)點(diǎn)被選擇的概率與它的入度成比例64維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量：2.概率為R2的邊指向一個(gè)新的結(jié)點(diǎn)并從一個(gè)已存在的結(jié)點(diǎn)出發(fā)，這個(gè)結(jié)點(diǎn)被選擇的概率與它的出度成比例65維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量:3.概率為R3=1–R1-R2的邊指向一個(gè)已存在概率與它的入度成比例的結(jié)點(diǎn)并從一個(gè)已存在的概率與它的出度成比例的結(jié)點(diǎn)出發(fā)。66維基百科的一個(gè)模型在每一步中我們增加一個(gè)結(jié)點(diǎn)與M條邊.邊的相關(guān)性速率方