復(fù)雜網(wǎng)絡(luò)概述.ppt

復(fù)雜網(wǎng)絡(luò)概述 王馳 為什么要研究復(fù)雜網(wǎng)絡(luò) 關(guān)于復(fù)雜性 大量個體 更典型的是具有適應(yīng)性的主體 所組成的復(fù)雜系統(tǒng) 在沒有中心控制 非完全信息 僅僅存在局域相互作用的條件下 通過個體之間的非線性相互作用 可以在宏觀層次上涌現(xiàn)出一定的結(jié)構(gòu)和功能 為什么要研究復(fù)雜網(wǎng)絡(luò) 復(fù)雜系統(tǒng)不能夠用分析的方法去研究 必須考慮個體之間的關(guān)聯(lián)和作用 復(fù)雜網(wǎng)絡(luò)是構(gòu)成復(fù)雜系統(tǒng)的基本結(jié)構(gòu) 每個復(fù)雜系統(tǒng)都可以看作是單元或個體之間的相互作用網(wǎng)絡(luò) 復(fù)雜網(wǎng)絡(luò)在刻畫復(fù)雜性方面的重要性是由于結(jié)構(gòu)決定功能的 理解復(fù)雜系統(tǒng)的行為應(yīng)該從理解系統(tǒng)相互作用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)開始 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息是構(gòu)建系統(tǒng)模型 研究系統(tǒng)性質(zhì)和功能的基礎(chǔ) 為什么要研究復(fù)雜網(wǎng)絡(luò) 復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法 它關(guān)注系統(tǒng)中個體相互關(guān)聯(lián)的作用的拓?fù)浣Y(jié)構(gòu) 是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ) 復(fù)雜網(wǎng)絡(luò)研究所關(guān)心的問題 如何定量刻畫復(fù)雜網(wǎng)絡(luò) 網(wǎng)絡(luò)結(jié)構(gòu)的描述及其性質(zhì)網(wǎng)絡(luò)是如何發(fā)展成現(xiàn)在這種結(jié)構(gòu)的 網(wǎng)絡(luò)演化模型網(wǎng)絡(luò)特定結(jié)構(gòu)的后果是什么 網(wǎng)絡(luò)結(jié)構(gòu)的魯棒性網(wǎng)絡(luò)上的動力學(xué)行為和過程 復(fù)雜網(wǎng)絡(luò)的表示方法 航空網(wǎng) 道路交通網(wǎng) 城市公共交通網(wǎng) 復(fù)雜網(wǎng)絡(luò)的表示方法 WWW 電力網(wǎng) 因特網(wǎng) 復(fù)雜網(wǎng)絡(luò)的表示方法 圖提供了一種用抽象的點和線表示各種實際網(wǎng)絡(luò)的統(tǒng)一方法 因而成為目前研究復(fù)雜網(wǎng)絡(luò)的一種共同的語言 例子 國際互聯(lián)網(wǎng) 節(jié)點 路由器連接 光纖 科學(xué)引用網(wǎng) 節(jié)點 文章連接 文章引用 社會網(wǎng)絡(luò) 節(jié)點 個體人連接 人際關(guān)系 復(fù)雜網(wǎng)絡(luò)的表示方法 按照圖中的邊是否有向和是否有權(quán) 可以有四種類型的圖 復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計算機(jī)表示 鄰接矩陣鄰接矩陣描述了節(jié)點與節(jié)點之間的鄰接關(guān)系 通常會用一個方陣A來表示 方陣中的元素用aij表示 復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計算機(jī)表示 一 復(fù)雜網(wǎng)絡(luò)的定義 錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個較嚴(yán)格的定義 具有自組織 自相似 吸引子 小世界 無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò) 一 復(fù)雜網(wǎng)絡(luò)的定義 小世界特性又被稱之為是六度空間理論或者是六度分割理論 小世界特性指出 社交網(wǎng)絡(luò)中的任何一個成員和任何一個陌生人之間所間隔的人不會超過六個 小世界特性 一 復(fù)雜網(wǎng)絡(luò)的定義 無標(biāo)度特性 現(xiàn)實世界的網(wǎng)絡(luò)大部分都不是隨機(jī)網(wǎng)絡(luò) 少數(shù)的節(jié)點往往擁有大量的連接 而大部分節(jié)點卻很少 節(jié)點的度數(shù)分布符合冪率分布 而這就被稱為是網(wǎng)絡(luò)的無標(biāo)度特性 將度分布符合冪律分布的復(fù)雜網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò) 一 復(fù)雜網(wǎng)絡(luò)的定義 社團(tuán)結(jié)構(gòu)特性 人以類聚 物以群分 復(fù)雜網(wǎng)絡(luò)中的節(jié)點往往也呈現(xiàn)出集群特性 例如 社會網(wǎng)絡(luò)中總是存在熟人圈或朋友圈 其中每個成員都認(rèn)識其他成員 集群程度的意義是網(wǎng)絡(luò)集團(tuán)化的程度 這是一種網(wǎng)絡(luò)的內(nèi)聚傾向 連通集團(tuán)概念反映的是一個大網(wǎng)絡(luò)中各集聚的小網(wǎng)絡(luò)分布和相互聯(lián)系的狀況 例如 它可以反映這個朋友圈與另一個朋友圈的相互關(guān)系 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 度 degree 節(jié)點i的度ki定義為與該節(jié)點連接的其他節(jié)點的數(shù)目 對于有向網(wǎng)絡(luò)分為出度和入度 直觀上看 一個節(jié)點的度越大就意味著這個節(jié)點在某種意義上越 重要 能力大 網(wǎng)絡(luò)的平均度 網(wǎng)絡(luò)中所有節(jié)點的度和的平均值 記作 并且 2M N M為網(wǎng)絡(luò)中的邊數(shù) N為節(jié)點數(shù) 度分布函數(shù)p k 隨機(jī)選定節(jié)點的度恰好為k的概率 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 度分布函數(shù)p k 隨機(jī)選定節(jié)點的度恰好為k的概率 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 節(jié)點的聚類系數(shù) 簇系數(shù) 在簡單圖中 設(shè)與節(jié)點v相鄰的節(jié)點有ki個 則節(jié)點v的聚類系數(shù)定義為這ki個節(jié)點之間存在邊數(shù)Ei與總的可能邊數(shù)ki ki 1 2之比 即 Ci 2Ei ki ki 1 包含節(jié)點i的三角形數(shù)目 以節(jié)點i為中心的連通三元組的數(shù)目 網(wǎng)絡(luò)的聚類系數(shù)C 所有節(jié)點i的聚類系數(shù)Ci的平均值 0 C 1 C 0 網(wǎng)絡(luò)中所有節(jié)點都是孤立點C 1 網(wǎng)絡(luò)中任意節(jié)點間都有邊相連 網(wǎng)絡(luò)節(jié)點間聯(lián)系的密切程度 體現(xiàn)網(wǎng)絡(luò)的凝聚力 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 節(jié)點的介數(shù) 邊的介數(shù) 式中 Njl表示節(jié)點vj和vl之間的最短路徑條數(shù) Njl i 表示節(jié)點vj和vl之間的最短路徑經(jīng)過節(jié)點vi的條數(shù) 式中 Nlm表示節(jié)點vl和vm之間的最短路徑條數(shù) Nlm eij 表示節(jié)點vl和vm之間的最短路徑經(jīng)過邊eij的條數(shù) 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 許多大規(guī)模的實際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng) 事實上 在很多類型的網(wǎng)絡(luò) 如社會關(guān)系網(wǎng)絡(luò) 中 你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個非零常數(shù) 即當(dāng)N 時 C O 1 這意味著這些實際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的 而是在某種程度上具有類似于社會關(guān)系網(wǎng)絡(luò)中 物以類聚 人以群分 的特性 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 最短路徑 Shortestpath 兩個節(jié)點之間邊數(shù)最少的路徑 最短路徑的長度稱為兩點間的距離 用dij 平均路徑長度 特征路徑長度 L 所有節(jié)點對之間的距離的平均值 研究發(fā)現(xiàn) 盡管許多實際復(fù)雜網(wǎng)絡(luò)的節(jié)點數(shù)巨大 網(wǎng)絡(luò)的平均路徑長度卻小的驚人 小世界效應(yīng) 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 四種結(jié)構(gòu)模型 規(guī)則網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)小世界網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò) 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 規(guī)則網(wǎng)絡(luò) a 全局耦合網(wǎng)絡(luò) b 最近鄰耦合網(wǎng)絡(luò) c 星形耦合網(wǎng)絡(luò) 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 規(guī)則網(wǎng)絡(luò)拓?fù)湫再|(zhì) 最近鄰耦合網(wǎng)絡(luò) 一般情況下 聚集系數(shù)較大 平均最短路徑較長 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 隨機(jī)網(wǎng)絡(luò) 1 初始化 給定N個節(jié)點以及連邊概率p 2 隨機(jī)連邊 選擇一對沒有邊相連的不同的節(jié)點 生成一個隨機(jī)數(shù)r 如果r p 那么在這對節(jié)點之間添加一條邊 否則就不添加邊 重復(fù)步驟 直到所有的節(jié)點對都被選擇過一次 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 隨機(jī)網(wǎng)絡(luò)拓?fù)湫再|(zhì) 度分布 邊數(shù)分布 聚類系數(shù) C p N 1 平均路徑長度 lnN ln 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 小世界網(wǎng)絡(luò) 三 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型 小世界網(wǎng)絡(luò) C p 平均聚集系數(shù)L p 平均最短路徑 PageRank算法 通過人工進(jìn)行網(wǎng)頁分類并整理出高質(zhì)量的網(wǎng)站 計算用戶查詢關(guān)鍵詞與網(wǎng)頁內(nèi)容的相關(guān)程度來返回搜索結(jié)果 算法來源 PageRank算法 谷歌的兩位創(chuàng)始人 當(dāng)時還是美國斯坦福大學(xué)研究生的佩奇和布林開始了對網(wǎng)頁排序問題的研究 借鑒了學(xué)術(shù)界評判學(xué)術(shù)論文重要性的通用方法 那就是看論文的引用次數(shù) 由此想到網(wǎng)頁的重要性也可以根據(jù)這種方法來評價 PageRank算法 如果一個網(wǎng)頁被很多其他網(wǎng)頁鏈接到的話說明這個網(wǎng)頁比較重要 也就是PageRank值會相對較高 如果一個PageRank值很高的網(wǎng)頁鏈接到一個其他的網(wǎng)頁 那么被鏈接到的網(wǎng)頁的PageRank值會相應(yīng)地因此而提高 PageRank算法 算法原理 PageRank算法總的來說就是預(yù)先給每個網(wǎng)頁一個PR值 PR值物理意義上為一個網(wǎng)頁被訪問概率 所以一般是1 N 其中N為網(wǎng)頁總數(shù) 另外 所有網(wǎng)頁的PR值的總和為1 預(yù)先給定PR值后 通過不斷迭代 直至達(dá)到平穩(wěn)分布為止 PR A PR B 2 PR C PageRank算法 算法證明 于是計算PR值的過程就變成了一個Markov過程 那么PageRank算法的證明也就轉(zhuǎn)為證明Markov過程的收斂性證明 如果這個Markov過程收斂 那么存在 且與P0的選取無關(guān) PageRank算法 算法證明 狀態(tài)轉(zhuǎn)移矩陣A需要滿足 1 A為隨機(jī)矩陣 2 A是不可約的 3 A是非周期的 作戰(zhàn)體系節(jié)點重要性分析 機(jī)械化戰(zhàn)爭時代 在通信手段和指揮控制手段受限的情況下 作戰(zhàn)體系 形成了一種樹狀結(jié)構(gòu) 隨著指揮信息系統(tǒng)的功能越來越強(qiáng) 作戰(zhàn)體系任何兩個節(jié)點之間均可以根據(jù)需要建立聯(lián)系 逐步形成網(wǎng)絡(luò)化結(jié)構(gòu) 作戰(zhàn)體系節(jié)點重要性分析 作戰(zhàn)體系結(jié)構(gòu)的網(wǎng)絡(luò)描述 依據(jù)復(fù)雜網(wǎng)絡(luò)理論 可以定義作戰(zhàn)體系由節(jié)點集合V和邊集合E組成的圖G V E 其中 V v1 v2 vn 代表組成作戰(zhàn)體系的指揮控制節(jié)點 預(yù)警偵察節(jié)點 包括戰(zhàn)場態(tài)勢信息源節(jié)點和目標(biāo)信息源節(jié)點 攻防交戰(zhàn)節(jié)點等 E e1 e2 em 代表節(jié)點之間信息傳遞關(guān)系 作戰(zhàn)體系節(jié)點重要性分析 作戰(zhàn)體系節(jié)點重要性的度量指標(biāo) 度指標(biāo) 描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點所產(chǎn)生的直接影響力 介數(shù)指標(biāo) 描述網(wǎng)絡(luò)中最短路徑通過某節(jié)點的數(shù)量 反映的是該節(jié)點在網(wǎng)絡(luò)中的樞紐性 緊密度指標(biāo) 緊密度指標(biāo)用于刻畫網(wǎng)絡(luò)中的節(jié)點通過網(wǎng)絡(luò)到達(dá)網(wǎng)絡(luò)中其它節(jié)點的難易程度 作戰(zhàn)體系節(jié)點重要性分析 作戰(zhàn)體系受損程度的度量指標(biāo) 作戰(zhàn)體系節(jié)點重要性分析