復(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ò)的表示方法 圖提供了一種用抽象的點(diǎn)和線表示各種實(shí)際網(wǎng)絡(luò)的統(tǒng)一方法 因而成為目前研究復(fù)雜網(wǎng)絡(luò)的一種共同的語言 例子 國際互聯(lián)網(wǎng) 節(jié)點(diǎn) 路由器連接 光纖 科學(xué)引用網(wǎng) 節(jié)點(diǎn) 文章連接 文章引用 社會網(wǎng)絡(luò) 節(jié)點(diǎn) 個體人連接 人際關(guān)系 復(fù)雜網(wǎng)絡(luò)的表示方法 按照圖中的邊是否有向和是否有權(quán) 可以有四種類型的圖 復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計(jì)算機(jī)表示 鄰接矩陣鄰接矩陣描述了節(jié)點(diǎn)與節(jié)點(diǎn)之間的鄰接關(guān)系 通常會用一個方陣A來表示 方陣中的元素用aij表示 復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計(jì)算機(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)實(shí)世界的網(wǎng)絡(luò)大部分都不是隨機(jī)網(wǎng)絡(luò) 少數(shù)的節(jié)點(diǎn)往往擁有大量的連接 而大部分節(jié)點(diǎn)卻很少 節(jié)點(diǎn)的度數(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é)點(diǎn)往往也呈現(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é)點(diǎn)i的度ki定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目 對于有向網(wǎng)絡(luò)分為出度和入度 直觀上看 一個節(jié)點(diǎn)的度越大就意味著這個節(jié)點(diǎn)在某種意義上越 重要 能力大 網(wǎng)絡(luò)的平均度 網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度和的平均值 記作 并且 2M N M為網(wǎng)絡(luò)中的邊數(shù) N為節(jié)點(diǎn)數(shù) 度分布函數(shù)p k 隨機(jī)選定節(jié)點(diǎn)的度恰好為k的概率 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 度分布函數(shù)p k 隨機(jī)選定節(jié)點(diǎn)的度恰好為k的概率 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 節(jié)點(diǎn)的聚類系數(shù) 簇系數(shù) 在簡單圖中 設(shè)與節(jié)點(diǎn)v相鄰的節(jié)點(diǎn)有ki個 則節(jié)點(diǎn)v的聚類系數(shù)定義為這ki個節(jié)點(diǎn)之間存在邊數(shù)Ei與總的可能邊數(shù)ki ki 1 2之比 即 Ci 2Ei ki ki 1 包含節(jié)點(diǎn)i的三角形數(shù)目 以節(jié)點(diǎn)i為中心的連通三元組的數(shù)目 網(wǎng)絡(luò)的聚類系數(shù)C 所有節(jié)點(diǎn)i的聚類系數(shù)Ci的平均值 0 C 1 C 0 網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是孤立點(diǎn)C 1 網(wǎng)絡(luò)中任意節(jié)點(diǎn)間都有邊相連 網(wǎng)絡(luò)節(jié)點(diǎn)間聯(lián)系的密切程度 體現(xiàn)網(wǎng)絡(luò)的凝聚力 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 節(jié)點(diǎn)的介數(shù) 邊的介數(shù) 式中 Njl表示節(jié)點(diǎn)vj和vl之間的最短路徑條數(shù) Njl i 表示節(jié)點(diǎn)vj和vl之間的最短路徑經(jīng)過節(jié)點(diǎn)vi的條數(shù) 式中 Nlm表示節(jié)點(diǎn)vl和vm之間的最短路徑條數(shù) Nlm eij 表示節(jié)點(diǎn)vl和vm之間的最短路徑經(jīng)過邊eij的條數(shù) 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 許多大規(guī)模的實(shí)際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng) 事實(shí)上 在很多類型的網(wǎng)絡(luò) 如社會關(guān)系網(wǎng)絡(luò) 中 你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個非零常數(shù) 即當(dāng)N 時 C O 1 這意味著這些實(shí)際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的 而是在某種程度上具有類似于社會關(guān)系網(wǎng)絡(luò)中 物以類聚 人以群分 的特性 二 復(fù)雜網(wǎng)絡(luò)中的基本概念 最短路徑 Shortestpath 兩個節(jié)點(diǎn)之間邊數(shù)最少的路徑 最短路徑的長度稱為兩點(diǎn)間的距離 用dij 平均路徑長度 特征路徑長度 L 所有節(jié)點(diǎn)對之間的距離的平均值 研究發(fā)現(xiàn) 盡管許多實(shí)際復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(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é)點(diǎn)以及連邊概率p 2 隨機(jī)連邊 選擇一對沒有邊相連的不同的節(jié)點(diǎn) 生成一個隨機(jī)數(shù)r 如果r p 那么在這對節(jié)點(diǎn)之間添加一條邊 否則就不添加邊 重復(fù)步驟 直到所有的節(jié)點(diǎn)對都被選擇過一次 三 復(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)站 計(jì)算用戶查詢關(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ù)這種方法來評價(jià) 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算法 算法證明 于是計(jì)算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é)點(diǎn)重要性分析 機(jī)械化戰(zhàn)爭時代 在通信手段和指揮控制手段受限的情況下 作戰(zhàn)體系 形成了一種樹狀結(jié)構(gòu) 隨著指揮信息系統(tǒng)的功能越來越強(qiáng) 作戰(zhàn)體系任何兩個節(jié)點(diǎn)之間均可以根據(jù)需要建立聯(lián)系 逐步形成網(wǎng)絡(luò)化結(jié)構(gòu) 作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系結(jié)構(gòu)的網(wǎng)絡(luò)描述 依據(jù)復(fù)雜網(wǎng)絡(luò)理論 可以定義作戰(zhàn)體系由節(jié)點(diǎn)集合V和邊集合E組成的圖G V E 其中 V v1 v2 vn 代表組成作戰(zhàn)體系的指揮控制節(jié)點(diǎn) 預(yù)警偵察節(jié)點(diǎn) 包括戰(zhàn)場態(tài)勢信息源節(jié)點(diǎn)和目標(biāo)信息源節(jié)點(diǎn) 攻防交戰(zhàn)節(jié)點(diǎn)等 E e1 e2 em 代表節(jié)點(diǎn)之間信息傳遞關(guān)系 作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系節(jié)點(diǎn)重要性的度量指標(biāo) 度指標(biāo) 描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)所產(chǎn)生的直接影響力 介數(shù)指標(biāo) 描述網(wǎng)絡(luò)中最短路徑通過某節(jié)點(diǎn)的數(shù)量 反映的是該節(jié)點(diǎn)在網(wǎng)絡(luò)中的樞紐性 緊密度指標(biāo) 緊密度指標(biāo)用于刻畫網(wǎng)絡(luò)中的節(jié)點(diǎn)通過網(wǎng)絡(luò)到達(dá)網(wǎng)絡(luò)中其它節(jié)點(diǎn)的難易程度 作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系受損程度的度量指標(biāo) 作戰(zhàn)體系節(jié)點(diǎn)重要性分析