復(fù)雜網(wǎng)絡(luò):模型Lecture2幻燈片制作：xxx翻譯者：武漢大學(xué)xxx整理ppt什么是網(wǎng)絡(luò)? 網(wǎng)絡(luò):一個(gè)通過鏈接互相關(guān)聯(lián)的實(shí)體的集合.互為朋友的人互相鏈接的計(jì)算機(jī)互相指向的網(wǎng)頁互相作用的蛋白質(zhì)整理ppt圖在數(shù)學(xué)世界,網(wǎng)絡(luò)被稱作圖,實(shí)體被稱作結(jié)點(diǎn),而它們之間的鏈接被稱作邊。關(guān)于圖的理論研究開始于18世紀(jì)，由數(shù)學(xué)家歐拉提出康尼斯堡橋梁?jiǎn)栴}在那之后圖被更廣泛深入地研究.

整理ppt過去的網(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)大量信息整理ppt現(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ò)不可能形象化整理ppt因特網(wǎng)地圖整理ppt因特網(wǎng)整理ppt網(wǎng)絡(luò)的類型社會(huì)網(wǎng)絡(luò)知識(shí)(信息)網(wǎng)絡(luò)科學(xué)網(wǎng)絡(luò)生物網(wǎng)絡(luò)整理ppt社會(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ò)整理ppt知識(shí)（信息）網(wǎng)絡(luò)結(jié)點(diǎn)代表信息,鏈接是信息的聯(lián)系引文網(wǎng)絡(luò)(有向無循環(huán)的)網(wǎng)絡(luò)(有向的)點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)詞網(wǎng)絡(luò)基于信任的網(wǎng)絡(luò)圖形軟件整理ppt科學(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ò)公路，鐵路，行人交通整理ppt生物網(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ò)整理ppt理解大型的圖關(guān)于現(xiàn)實(shí)生活網(wǎng)絡(luò)的數(shù)據(jù)有哪些？?我們可以解釋網(wǎng)絡(luò)是怎樣產(chǎn)生的嗎？整理ppt關(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)）整理ppt現(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)一的基本生成過程？整理ppt小世界網(wǎng)絡(luò)例如：六度分離理論但是有超過六十億人口生存在這個(gè)世界上！整理ppt小世界網(wǎng)絡(luò)(a)蛋白質(zhì)(b)神經(jīng)元(c)互聯(lián)網(wǎng)整理ppt生成隨機(jī)圖經(jīng)典圖形理論模型(Erd?s-Renyi)每條邊的獨(dú)立產(chǎn)生概率為P很好的研究模型，但是:大多數(shù)頂點(diǎn)的度大致上相同兩個(gè)結(jié)點(diǎn)相連的概率與它們是否共有一個(gè)鄰居結(jié)點(diǎn)無關(guān)平均路徑短整理ppt現(xiàn)實(shí)網(wǎng)絡(luò)建模現(xiàn)實(shí)生活網(wǎng)絡(luò)不是隨機(jī)的我們是否可以定義一個(gè)模型，它能夠產(chǎn)生與現(xiàn)實(shí)生活中相似的具有統(tǒng)計(jì)性能的圖?一系列關(guān)于隨機(jī)圖的模型整理ppt網(wǎng)絡(luò)的作用過程理解網(wǎng)絡(luò)的結(jié)構(gòu)為什么重要?流行病學(xué):病毒在無標(biāo)度網(wǎng)絡(luò)中傳播地更快隨機(jī)接種疫苗的結(jié)點(diǎn)無法正常工作，但有針對(duì)性的疫苗接種是非常有效的整理ppt網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)整理ppt網(wǎng)絡(luò)結(jié)構(gòu)隨機(jī)網(wǎng)絡(luò)VS無標(biāo)度網(wǎng)絡(luò)整理ppt網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)整理ppt網(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!整理ppt萬維網(wǎng)萬維網(wǎng)是一個(gè)文件之間互相指向的網(wǎng)絡(luò)結(jié)點(diǎn)指網(wǎng)頁而邊指網(wǎng)頁間的鏈接邊是有指向的：鏈接可以從它們出發(fā)或者到達(dá)它們整理ppt萬維網(wǎng)整理ppt網(wǎng)絡(luò)的未來網(wǎng)絡(luò)現(xiàn)在看上去是這樣的越來越多系統(tǒng)被網(wǎng)絡(luò)模型化不同學(xué)科的科學(xué)家致力于對(duì)網(wǎng)絡(luò)的研究(物理學(xué)家,計(jì)算機(jī)學(xué)家,數(shù)學(xué)家,生物學(xué)家,社會(huì)學(xué)家,經(jīng)濟(jì)學(xué)家)還有許多問題尚未被理解.整理ppt數(shù)學(xué)工具圖理論概率論線性代數(shù)整理ppt圖理論GraphG=(V,E)V=頂點(diǎn)的集合E=邊的集合12345無向圖E={(1,2),(1,3),(2,3),(3,4),(4,5)}整理ppt圖理論GraphG=(V,E)V=頂點(diǎn)的集合E=邊的集合12345有向圖E={?1,2?,?2,1?

?1,3?,?3,2?,?3,4?,?4,5?}整理ppt無向圖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)]整理ppt有向圖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]整理ppt路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的路徑:一段連續(xù)的邊(有向或無向從結(jié)點(diǎn)i到結(jié)點(diǎn)j的連接)路徑長(zhǎng)度:路徑上的邊數(shù)結(jié)點(diǎn)i和結(jié)點(diǎn)j是相連的循環(huán):一段初始和結(jié)束結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)的路徑1234512345整理ppt最短路徑從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑也被稱作BFS路徑,或短線程路徑1234512345整理ppt直徑途中距離最長(zhǎng)的一條最短路徑1234512345整理ppt無向圖12345連通圖:任意兩個(gè)結(jié)點(diǎn)都存在連接的圖非連通圖:一個(gè)無連接的圖連通區(qū)域:包含相連頂點(diǎn)的子圖整理ppt完全連通圖CliqueKn一個(gè)最多有n(n-1)/2條邊的圖（n為頂點(diǎn)數(shù)）12345整理ppt連通圖12345強(qiáng)連通圖:任意兩個(gè)頂點(diǎn)之間存在一條路徑弱連通圖:邊沒有指向時(shí)圖就是連通的整理ppt子圖12345子圖:給定V’

V,E’E,圖

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

V,E’E是V’中結(jié)點(diǎn)連成的邊的集合.則圖G’=(V’,E’),是G的一個(gè)生成子圖整理ppt樹沒有循環(huán)的無向連通圖12345整理ppt二分圖集合V可以被分割成兩個(gè)集合L和R的圖,而所有的邊由L和R的結(jié)點(diǎn)連接而成，在集合L和R內(nèi)部不存在邊。整理ppt線性代數(shù)鄰接矩陣對(duì)稱矩陣的無向圖12345整理ppt線性代數(shù)鄰接矩陣非對(duì)稱矩陣的無向圖12345整理ppt特征值與特征向量若值λ是矩陣A的特征值，且存在不為零向量的向量X，使得,Ax=λx.向量x是矩陣A的一個(gè)特征向量最大的特征向量被稱為主特征值對(duì)應(yīng)的特征向量被稱為主特征向量對(duì)應(yīng)最大值方向的變動(dòng)整理ppt特征值整理ppt隨機(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è)向量。整理ppt隨機(jī)游動(dòng)平穩(wěn)分布:標(biāo)準(zhǔn)鄰接矩陣左邊的主特征向量x=xP無向圖的度分布12345整理ppt概率論概率空間:給定一對(duì)?Ω,P?Ω:樣本空間P:Ω的子集的測(cè)量概率隨機(jī)變量X:Ω→R概率分布函數(shù)P[X=x]數(shù)學(xué)期望整理ppt隨機(jī)圖的類隨機(jī)圖的類被定義為一對(duì)?Gn,P?

，Gn

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

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

p=1/2時(shí),我們得到一個(gè)統(tǒng)一的分布整理ppt漸近符號(hào)對(duì)于兩個(gè)函數(shù)f(n)和g(n)若存在正數(shù)c

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

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

若存在正數(shù)c

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

則對(duì)于所有的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))整理pptP

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

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

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

A(x)≥cOPT(x)(最大化問題)整理ppt復(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(巴西)整理ppt維基百科的復(fù)雜網(wǎng)絡(luò)網(wǎng)絡(luò)描述維基百科的統(tǒng)計(jì)分析模型與解釋整理ppt整理ppt整理ppt整理ppt維基百科是怎樣工作的？多虧了維基科技,一個(gè)用戶可以

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

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

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

整理ppt維基百科中的結(jié)點(diǎn)與邊網(wǎng)絡(luò)的邊是百科全書的條目邊是條目間的引用整理ppt統(tǒng)計(jì)特性條目的數(shù)目在時(shí)間內(nèi)成倍增長(zhǎng)整理ppt度分布整理ppt優(yōu)先連接為了研究?jī)?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é)論整理ppt優(yōu)先連接圓:英語三角:葡萄牙語填充:入度白色:出度整理ppt維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量1.概率為R1的邊從新結(jié)點(diǎn)出發(fā)并指向一個(gè)已存在的結(jié)點(diǎn)，而這個(gè)結(jié)點(diǎn)被選擇的概率與它的入度成比例整理ppt維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量：2.概率為R2的邊指向一個(gè)新的結(jié)點(diǎn)并從一個(gè)已存在的結(jié)點(diǎn)出發(fā)，這個(gè)結(jié)點(diǎn)被選擇的概率與它的出度成比例整理ppt維基百科的一個(gè)模型在每一步中我們?cè)黾右粋€(gè)結(jié)點(diǎn)與M條邊.邊的方向是一個(gè)隨機(jī)變量:3.概率為R3=1–R1-R2的邊指向一個(gè)已存在概率與它的入度成比例的結(jié)點(diǎn)并從一個(gè)已存在的概