復(fù)雜網(wǎng)絡(luò)模型課件

1、什么是網(wǎng)絡(luò)?網(wǎng)絡(luò): 一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.互為朋友的人互相鏈接的計(jì)算機(jī)互相指向的網(wǎng)頁互相作用的蛋白質(zhì)什么是網(wǎng)絡(luò)?網(wǎng)絡(luò): 一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.圖在數(shù)學(xué)世界, 網(wǎng)絡(luò)被稱作圖, 實(shí)體被稱作結(jié)點(diǎn), 而它們之間的鏈接被稱作邊。關(guān)于圖的理論研究開始于18世紀(jì)，由數(shù)學(xué)家歐拉提出康尼斯堡橋梁問題在那之后圖被更廣泛深入地研究. 圖在數(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)大量信息過去的網(wǎng)絡(luò)圖在過去被用作為現(xiàn)有網(wǎng)絡(luò)制作模型 (舉例來說

2、. 有現(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ò)不可能形象化現(xiàn)在的網(wǎng)絡(luò)更多的、更大型的網(wǎng)絡(luò)出現(xiàn)了因特網(wǎng)地圖因特網(wǎng)地圖因特網(wǎng)因特網(wǎng)網(wǎng)絡(luò)的類型社會(huì)網(wǎng)絡(luò)知識(shí) (信息) 網(wǎng)絡(luò)科學(xué)網(wǎng)絡(luò)生物網(wǎng)絡(luò)網(wǎng)絡(luò)的類型社會(huì)網(wǎng)絡(luò)社會(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ò)社會(huì)網(wǎng)絡(luò)鏈接表示社會(huì)中的互動(dòng)知識(shí)（信息）網(wǎng)絡(luò)結(jié)點(diǎn)代表信息, 鏈接是信息的聯(lián)系引文網(wǎng)絡(luò) (有向無循環(huán)的)網(wǎng)絡(luò) (有向的)點(diǎn)

3、對(duì)點(diǎn)網(wǎng)絡(luò)詞網(wǎng)絡(luò)基于信任的網(wǎng)絡(luò)圖形軟件知識(shí)（信息）網(wǎng)絡(luò)結(jié)點(diǎn)代表信息, 鏈接是信息的聯(lián)系科學(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ò)公路，鐵路，行人交通 科學(xué)網(wǎng)絡(luò)為商品分配所建的網(wǎng)絡(luò)生物網(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ò)生物網(wǎng)絡(luò)網(wǎng)絡(luò)代表生物系統(tǒng)理解大型的圖關(guān)于現(xiàn)實(shí)生活網(wǎng)絡(luò)的數(shù)據(jù)有哪些？?我們可以解釋網(wǎng)絡(luò)是怎樣產(chǎn)生的嗎？理解大型的圖關(guān)于現(xiàn)實(shí)生活網(wǎng)絡(luò)的數(shù)據(jù)有哪些？?關(guān)于網(wǎng)絡(luò)性質(zhì)的研究1999年左右Watts and Strogatz, Dynamics and small-world phenomeno

4、n（動(dòng)力學(xué)和小世界現(xiàn)象）Faloutsos3, On power-law relationships of the Internet Topology（基于權(quán)利-法律關(guān)系的互聯(lián)網(wǎng)拓?fù)洌㎏leinberg et al., The Web as a graph（作為一張圖的互聯(lián)網(wǎng)）Barabasi and Albert, The emergence of scaling in real networks（現(xiàn)實(shí)網(wǎng)絡(luò)中標(biāo)度的出現(xiàn)）關(guān)于網(wǎng)絡(luò)性質(zhì)的研究1999年左右現(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,那

5、么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)一的基本生成過程？ 現(xiàn)實(shí)網(wǎng)絡(luò)的性質(zhì)大多數(shù)結(jié)點(diǎn)只有少數(shù)的鄰居 (度), 但也有一些小世界網(wǎng)絡(luò)例如：六度分離理論但是有超過六十億人口生存在這個(gè)世界上！小世界網(wǎng)絡(luò)例如：六度分離理論但是有超過六十億人口生存在這個(gè)世小世界網(wǎng)絡(luò)(a) 蛋白質(zhì) (b) 神經(jīng)元 (c) 互聯(lián)網(wǎng)小世界網(wǎng)絡(luò)(a) 蛋白質(zhì) (b) 神經(jīng)元 (c) 互生成隨機(jī)圖經(jīng)典圖形理論模型 (Erds-Renyi)每條邊的獨(dú)立產(chǎn)生概率為P很好的研究模型，但是:大多數(shù)頂點(diǎn)的度大致上相同兩個(gè)結(jié)

6、點(diǎn)相連的概率與它們是否共有一個(gè)鄰居結(jié)點(diǎn)無關(guān)平均路徑短生成隨機(jī)圖經(jīng)典圖形理論模型 (Erds-Renyi)現(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ī)圖的模型現(xiàn)實(shí)網(wǎng)絡(luò)建?，F(xiàn)實(shí)生活網(wǎng)絡(luò)不是隨機(jī)的網(wǎng)絡(luò)的作用過程理解網(wǎng)絡(luò)的結(jié)構(gòu)為什么重要?流行病學(xué): 病毒在無標(biāo)度網(wǎng)絡(luò)中傳播地更快隨機(jī)接種疫苗的結(jié)點(diǎn)無法正常工作，但有針對(duì)性的疫苗接種是非常有效的網(wǎng)絡(luò)的作用過程理解網(wǎng)絡(luò)的結(jié)構(gòu)為什么重要?網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)VS無標(biāo)度網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)VS無標(biāo)度網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)搜索第一代

7、搜索引擎: 萬維網(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!網(wǎng)絡(luò)搜索第一代搜索引擎: 萬維網(wǎng)只是作為一個(gè)文件的集合萬維網(wǎng)萬維網(wǎng)是一個(gè)文件之間互相指向的網(wǎng)絡(luò)結(jié)點(diǎn)指網(wǎng)頁而邊指網(wǎng)頁間的鏈接邊是有指向的：鏈接可以從它們出發(fā)或者到達(dá)它們?nèi)f維網(wǎng)萬維網(wǎng)是一個(gè)文件之間互相指向的網(wǎng)絡(luò)萬維網(wǎng)萬維網(wǎng)網(wǎng)絡(luò)的未來網(wǎng)絡(luò)現(xiàn)在看上去是這樣的越來越多系統(tǒng)被網(wǎng)絡(luò)模型化不同學(xué)科的科學(xué)家致力于對(duì)網(wǎng)絡(luò)的研究

8、(物理學(xué)家,計(jì)算機(jī)學(xué)家, 數(shù)學(xué)家, 生物學(xué)家, 社會(huì)學(xué)家, 經(jīng)濟(jì)學(xué)家)還有許多問題尚未被理解.網(wǎng)絡(luò)的未來網(wǎng)絡(luò)現(xiàn)在看上去是這樣的數(shù)學(xué)工具圖理論概率論線性代數(shù)數(shù)學(xué)工具圖理論圖理論Graph G=(V,E)V = 頂點(diǎn)的集合E = 邊的集合12345無向圖E=(1,2),(1,3),(2,3),(3,4),(4,5)圖理論Graph G=(V,E)12345無向圖圖理論Graph G=(V,E)V = 頂點(diǎn)的集合E = 邊的集合12345有向圖E=1,2, 2,1 1,3, 3,2, 3,4, 4,5圖理論Graph G=(V,E)12345有向圖無向圖12345結(jié)點(diǎn)i的度數(shù)dd(i) 與結(jié)點(diǎn)i相連

9、的邊數(shù)度序列d(i),d(2),d(3),d(4),d(5)2,2,2,1,1度分布(1,2),(2,3)無向圖12345結(jié)點(diǎn)i的度數(shù)dd(i) 度序列度分布有向圖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有向圖12345結(jié)點(diǎn)i的入度結(jié)點(diǎn)i的出度入度序列路徑從結(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)的路徑1234512345路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑: 一段連續(xù)的邊 (有向或無向從結(jié)最短路徑從結(jié)

10、點(diǎn)i到結(jié)點(diǎn)j的最短路徑也被稱作BFS路徑, 或短線程路徑1234512345最短路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑1234512345直徑途中距離最長的一條最短路徑1234512345直徑途中距離最長的一條最短路徑1234512345無向圖12345連通圖: 任意兩個(gè)結(jié)點(diǎn)都存在連接的圖非連通圖: 一個(gè)無連接的圖連通區(qū)域: 包含相連頂點(diǎn)的子圖無向圖12345連通圖: 任意兩個(gè)結(jié)點(diǎn)都存在連接的圖完全連通圖Clique Kn一個(gè)最多有 n(n-1)/2 條邊的圖（n為頂點(diǎn)數(shù)）12345完全連通圖Clique Kn12345連通圖12345強(qiáng)連通圖: 任意兩個(gè)頂點(diǎn)之間存在一條路徑弱連通圖: 邊沒有指向時(shí)圖

11、就是連通的連通圖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è)生成子圖子圖12345子圖: 給定V V, E E, 樹沒有循環(huán)的無向連通圖12345樹沒有循環(huán)的無向連通圖12345二分圖集合V可以被分割成兩個(gè)集合L和R的圖, 而所有的邊由L和R的結(jié)點(diǎn)連接而成，在集合L和R內(nèi)部不存在邊。二分圖集合V可以被分割成兩個(gè)集合L和R的圖, 而所有的邊由L線性代數(shù)鄰接矩陣對(duì)稱矩陣的無向圖12345線性代數(shù)鄰接矩陣123

12、45線性代數(shù)鄰接矩陣非對(duì)稱矩陣的無向圖12345線性代數(shù)鄰接矩陣12345特征值與特征向量若值 是矩陣A的特征值，且存在不為零向量的向量X，使得, Ax=x. 向量 x 是矩陣A的一個(gè)特征向量最大的特征向量被稱為主特征值對(duì)應(yīng)的特征向量被稱為主特征向量對(duì)應(yīng)最大值方向的變動(dòng)特征值與特征向量若值 是矩陣A的特征值，且存在不為零向量的特征值特征值隨機(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è)向量。隨機(jī)游動(dòng)從一個(gè)結(jié)點(diǎn)開始,它的連接結(jié)點(diǎn)一律是隨機(jī)的。隨機(jī)游動(dòng)平穩(wěn)分布:

13、 標(biāo)準(zhǔn)鄰接矩陣左邊的主特征向量x = xP無向圖的度分布12345隨機(jī)游動(dòng)平穩(wěn)分布: 標(biāo)準(zhǔn)鄰接矩陣左邊的主特征向量12345概率論概率空間: 給定一對(duì),P: 樣本空間P: 的子集的測量概率隨機(jī)變量 X: R概率分布函數(shù) PX=x數(shù)學(xué)期望概率論概率空間: 給定一對(duì),P隨機(jī)圖的類隨機(jī)圖的類 被定義為一對(duì) Gn,P ，Gn 是 所有大小為n的圖的集合, P 是集合Gn的概率分布Erds-Renyi 圖: 每條邊出現(xiàn)的概率為 p當(dāng) p=1/2時(shí), 我們得到一個(gè)統(tǒng)一的分布隨機(jī)圖的類隨機(jī)圖的類 被定義為一對(duì) Gn,P ，Gn 是漸近符號(hào)對(duì)于兩個(gè)函數(shù) f(n)和g(n)若存在正數(shù) c 和 N, 使得 f(n

14、) c g(n), 則對(duì)于所有的 nN，有f(n) = O(g(n) 若存在正數(shù) c 和 N, 使得 f(n) c g(n), 則對(duì)于所有的 nN，有 f(n) = (g(n) 若f(n)=O(g(n)并且f(n)=(g(n) ，則有f(n) = (g(n)若 lim f(n)/g(n) = 0, 則隨著 n，有f(n) = o(g(n) 若 lim f(n)/g(n) = , 則隨著 n，有f(n) = (g(n)漸近符號(hào)對(duì)于兩個(gè)函數(shù) f(n)和g(n)P 與 NPP: 在多項(xiàng)式時(shí)間內(nèi)可以得到解決的一類問題NP: 在多項(xiàng)式時(shí)間內(nèi)可以得到驗(yàn)證的一類問題NP-hard:至少與NP中任何問題一樣困

15、難的問題P 與 NPP: 在多項(xiàng)式時(shí)間內(nèi)可以得到解決的一類問題近似算法NP-優(yōu)化問題: 給定一個(gè)問題的實(shí)例, 找到一個(gè)能將目標(biāo)函數(shù)最小化或最大化的解決方法 。算法 A 是一個(gè)問題的系數(shù)c的近似值, 若對(duì)于每一個(gè)輸入值xA(x) c OPT(x) (最小化問題)A(x) c OPT(x) (最大化問題)近似算法NP-優(yōu)化問題: 給定一個(gè)問題的實(shí)例, 找到一個(gè)能將復(fù)雜網(wǎng)絡(luò)的實(shí)際應(yīng)用維基百科F. Colaiori, V. Servedio, G. Caldarelli, 交流物理學(xué)部., “La Sapienza”, 羅馬 (意大利)D. Donato, S. Leonardi計(jì)算機(jī)科學(xué)學(xué)部., “

16、La Sapienza”, 羅馬(意大利)L. Salete Buriol計(jì)算機(jī)科學(xué)學(xué)部., University of Porto Alegre, Rio Grande do Sul (巴西)復(fù)雜網(wǎng)絡(luò)的實(shí)際應(yīng)用維基百科F. Colaiori, V維基百科的復(fù)雜網(wǎng)絡(luò) 網(wǎng)絡(luò)描述 維基百科的統(tǒng)計(jì)分析 模型與解釋維基百科的復(fù)雜網(wǎng)絡(luò) 網(wǎng)絡(luò)描述復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型維基百科是怎樣工作的？多虧了維基科技, 一個(gè)用戶可以 增加新的條目到百科全書中 修改已存在條目的內(nèi)容 修改其鏈接在萬維網(wǎng)中，每個(gè)用戶只對(duì)從他的網(wǎng)頁發(fā)出的指令負(fù)責(zé) 維基百科是怎樣工作的？多虧了維基科技, 一個(gè)用戶可以 維基百科中的

17、結(jié)點(diǎn)與邊網(wǎng)絡(luò)的邊是百科全書的條目邊是條目間的引用維基百科中的結(jié)點(diǎn)與邊網(wǎng)絡(luò)的邊是百科全書的條目統(tǒng)計(jì)特性條目的數(shù)目在時(shí)間內(nèi)成倍增長統(tǒng)計(jì)特性條目的數(shù)目在時(shí)間內(nèi)成倍增長度分布度分布優(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é)論優(yōu)先連接為了研究優(yōu)先連接, 我們采用了由紐曼(2001)提出優(yōu)先連接圓:

18、 英語三角: 葡萄牙語填充: 入度白色: 出度優(yōu)先連接圓: 英語維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的方向是一個(gè)隨機(jī)變量1. 概率為 R1 的邊從新結(jié)點(diǎn)出發(fā)并指向一個(gè)已存在的結(jié)點(diǎn)，而這個(gè)結(jié)點(diǎn)被選擇的概率與它的入度成比例維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的方向是一個(gè)隨機(jī)變量：2. 概率為 R2 的邊指向一個(gè)新的結(jié)點(diǎn)并從一個(gè)已存在的結(jié)點(diǎn)出發(fā) ，這個(gè)結(jié)點(diǎn)被選擇的概率與它的出度成比例維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的方向是一個(gè)隨機(jī)變量:3. 概率為 R3 = 1 R1 - R2的邊指向一個(gè)已存在概率與它的入度成比例的結(jié)點(diǎn) 并從一個(gè)已存在的概率與它的出度成比例的結(jié)點(diǎn)出發(fā)。維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊. 邊的相關(guān)性速率方程允許我們也計(jì)算入