復雜網(wǎng)絡分析方法.ppt

第3節(jié)復雜網(wǎng)絡分析方法 復雜網(wǎng)絡理論與方法簡介應用實例 區(qū)域氣候變化的復雜網(wǎng)絡分析 復雜網(wǎng)絡 complexnetwork 是復雜系統(tǒng)研究的拓撲基礎 近幾年發(fā)展起來的復雜網(wǎng)絡方法 是現(xiàn)代復雜性科學的一個重要分支 它為人們認識系統(tǒng)復雜性提供了一個新的視角 該分支 以具有自組織 自相似 吸引子 小世界 無標度中部分或全部性質的網(wǎng)絡為研究對象 主要研究網(wǎng)絡的幾何性質 拓撲結構 研究網(wǎng)絡的結構穩(wěn)定性 網(wǎng)絡演化的統(tǒng)計規(guī)律 以及網(wǎng)絡形成與演化的動力學機制等 一 復雜網(wǎng)絡理論與方法簡介 一 復雜網(wǎng)絡的概念簡而言之 所謂復雜網(wǎng)絡即呈現(xiàn)高度復雜性的網(wǎng)絡 其復雜性主要表現(xiàn)在以下幾個方面 1 結構復雜 表現(xiàn)在節(jié)點數(shù)目巨大 網(wǎng)絡結構呈現(xiàn)多種不同特征 2 網(wǎng)絡進化 表現(xiàn)在節(jié)點或連接的產生與消失 例如WorldwideNetwork 網(wǎng)頁或鏈接隨時可能出現(xiàn)或斷開 導致網(wǎng)絡結構不斷發(fā)生變化 3 連接多樣性 節(jié)點之間的連接權重存在差異 且有可能存在方向性 4 動力學復雜性 節(jié)點集可能屬于非線性動力學系統(tǒng) 節(jié)點狀態(tài)隨時間發(fā)生復雜變化 5 節(jié)點多樣性 復雜網(wǎng)絡中的節(jié)點可以代表任何事物 例如 人際關系構成的復雜網(wǎng)絡節(jié)點代表單獨個體 萬維網(wǎng)組成的復雜網(wǎng)絡節(jié)點代表不同網(wǎng)頁 6 多重復雜性融合 多重復雜性相互影響 導致更為難以預料的結果 二 復雜網(wǎng)絡與傳統(tǒng)網(wǎng)絡的區(qū)別復雜網(wǎng)絡與傳統(tǒng)的圖論網(wǎng)絡相比較 具有幾個方面的顯著不同之處 1 以節(jié)點的數(shù)量來說 傳統(tǒng)的網(wǎng)絡皆屬于小網(wǎng)絡 節(jié)點數(shù)不過數(shù)十個至上百個 特殊情況才會到百個點 但復雜網(wǎng)絡的節(jié)點數(shù) 少則數(shù)千個多則達百萬個 數(shù)量的增加使得網(wǎng)絡的復雜度大大的提高 2 復雜網(wǎng)絡給人們帶來了一種新視野 讓人們發(fā)掘出在復雜的點邊關系中所潛伏的規(guī)律或普遍存在的特性 以及其物理學 社會學或生物學意義 這是以往的傳統(tǒng)網(wǎng)絡所不及的 3 從研究方法來說 傳統(tǒng)的網(wǎng)絡研究 主要依賴數(shù)理推導和作圖技巧研究小網(wǎng)絡 但是面對數(shù)量級倍增的復雜網(wǎng)絡 必須借助于計算機完成大量的計算和作圖任務 4 從研究議題而言 復雜網(wǎng)絡所涵蓋的議題相當廣泛 橫跨了自然科學和社會科學等領域 三 復雜網(wǎng)絡的基本統(tǒng)計指標復雜網(wǎng)絡的基本統(tǒng)計指標 包括 度及其分布特征 平均路徑長度 群聚系數(shù) 介數(shù)等 1 度與度分布數(shù)學圖論中定義 網(wǎng)絡中一個節(jié)點的度 指該節(jié)點擁有的邊的個數(shù) 度分布 是指不同的度在網(wǎng)絡中出現(xiàn)的概率分布 通常我們定義網(wǎng)絡的度分布 為網(wǎng)絡中度數(shù)為k的節(jié)點個數(shù)占節(jié)點總個數(shù)的比例 也等于在隨機一致的原則下挑選出具有節(jié)點度為k的概率 對任一給定的網(wǎng)絡 可用直方圖來表示 而這直方圖就是網(wǎng)絡的度分布 以下簡稱度分布 網(wǎng)絡的度分布的基礎上 可以進一步定義網(wǎng)絡的累計度分布 圖8 3 1給出了泊松度分布和冪律度分布 其中 泊松分布是一個山峰形的分布 其平均度在網(wǎng)絡中擁有最大的出現(xiàn)概率 而隨著偏離平均度的程度越大 它出現(xiàn)概率越小 冪律度分布 則呈現(xiàn)出胖尾的直線分布 表示隨著度數(shù)的增加 擁有這樣度數(shù)的節(jié)點數(shù)將隨之減少 圖8 3 1兩種度分布 泊松分布 a 與冪律分布 b 2 距離與平均路徑長度在網(wǎng)絡研究中 一般定義 兩個節(jié)點之間的距離 路徑長度 為兩個節(jié)點間最短路徑的長度 網(wǎng)絡的直徑為任意兩個節(jié)點之間的最大距離 網(wǎng)絡的平均路徑長度則是所有節(jié)點對之間距離的平均值 它描述了網(wǎng)絡中節(jié)點之間的分離程度 網(wǎng)絡的平均路徑長度的計算公式為式中 表示從節(jié)點i到節(jié)點j的最短路徑長度 N表示節(jié)點總數(shù) 式中的定義包含了從每個節(jié)點到其自身的距離 為0 且排除了網(wǎng)絡中存在孤立點的問題 8 3 7 3 群聚系數(shù)群聚系數(shù) 也稱集群系數(shù) 是用來衡量一個網(wǎng)絡中的節(jié)點之間結集成團的程度的指標 節(jié)點i的群聚系數(shù)的定義如下 網(wǎng)絡的群聚系數(shù) 被定義為各節(jié)點群聚系數(shù)的平均值 即 賦權網(wǎng)絡 對邊賦權 其節(jié)點i的群聚系數(shù)被定義為 4 介數(shù)介數(shù) 分為兩種 即節(jié)點介數(shù)和邊介數(shù) 節(jié)點 邊 的介數(shù) 是指網(wǎng)絡中所有的最短路徑中經(jīng)過該節(jié)點 邊 的數(shù)量比例 介數(shù)反映了相應的節(jié)點或邊在整個網(wǎng)絡中的作用和影響力 節(jié)點k的介數(shù) 可以通過下式計算 式中 為連接節(jié)點i和j 且通過節(jié)點k的最短路徑數(shù) 為連接節(jié)點i和j的最短路徑數(shù) 四 小世界網(wǎng)絡與無標度網(wǎng)絡復雜網(wǎng)絡 一般具有兩個共性 即小世界網(wǎng)絡與無標度網(wǎng)絡 1 小世界網(wǎng)絡小世界網(wǎng)絡 描述了許多復雜網(wǎng)絡的一個共性 即 大多數(shù)網(wǎng)絡盡管規(guī)模很大 但是任意兩個節(jié) 頂 點間卻存在一條相當短的路徑 例如 在龐大的人際關系網(wǎng)絡中 人與人相互認識的很少 但是任何一個人卻可以找到一條相當短的路徑 去結識他不認識的距他很遠的其他人 這正如麥克盧漢所說 地球變得越來越小 地球村 就是對 小世界 的形象描述 小世界網(wǎng)絡的判定準則有兩個 1 平均路徑長度短 2 高集聚系數(shù) 許多復雜網(wǎng)絡盡管節(jié)點數(shù)目巨大 但節(jié)點之間的特征路徑長度則非常小 集聚系數(shù)則是用來描述 抱團 現(xiàn)象的 也就是 你朋友之間相互認識的程度 數(shù)學上來說 一個節(jié)點的集聚系數(shù)等于與它相連的節(jié)點中相互連接的點對數(shù)與總點對數(shù)的比值 高集聚系數(shù)實際上保證了較小的特征路徑長度 2 無標度網(wǎng)絡無標度網(wǎng)絡 是指網(wǎng)絡的度分布滿足冪律分布 也就是說無標度網(wǎng)絡的度分布滿足冪律性質 即 式中 表示度的概率 為冪指數(shù) 冪律分布這一性質 正說明了無標度網(wǎng)絡的度分布與一般隨機網(wǎng)絡的不同 隨機網(wǎng)絡的度分布屬于正態(tài)分布 因此有一個特征度數(shù) 即大部分節(jié)點的度數(shù)都接近它 無尺度網(wǎng)絡的度分布是呈集散分布 大部分節(jié)點之間只有比較少的連接 而少數(shù)節(jié)點有大量的連接 由于不存在特征度數(shù) 因此得名 無尺度 二 應用實例 區(qū)域氣候變化的復雜網(wǎng)絡分析總步驟 運用粗粒化方法 將塔里木河流域的氣候因子序列轉化為由5個特征字符 R r e d D 構成的符號序列 然后以符號序列中的125種3字串組成的氣候因子波動模態(tài)為網(wǎng)絡的節(jié)點 并按照時間順序連邊 構建了有向加權的波動網(wǎng)絡 進而計算三種網(wǎng)絡的度與度分布 聚群系數(shù) 最短平均路徑長度等動力學統(tǒng)計量 分析網(wǎng)絡的復雜性特征 一 氣候波動網(wǎng)絡的構建對塔里木河流域23個氣象臺站的日平均氣溫和日降水量 以粗?；椒ò阎鹑掌骄鶜鉁嘏c日降水量序列轉化為由5個特征字符 R r e d D 構成的符號序列 以符號序列中的125種3字串組成的氣溫和降水量的波動模態(tài)為網(wǎng)絡的節(jié)點 即連續(xù)3日的因子波動組合 并按照時間順序連邊 構建一個有向加權的氣溫波動網(wǎng)絡 簡記為TFN 和降水波動網(wǎng)絡 簡記為PFN 進而將氣溫與降水的波動模態(tài)信息蘊含于網(wǎng)絡的拓撲結構之中 下面以日降水量序列為例 簡要地介紹TFN和PFN網(wǎng)絡的構建步驟 第一步 資料準備 以塔里木河流域23個氣象臺站1961 2011年的逐日降水量 構造時間序列 其中 t代表時間 日期 序號 n代表臺站編號 即 t 1 2 3 18626 n 1 2 23 計算23個氣象臺站平均的日降水量序列的值 即 8 3 13 第二步 粗?；?計算因子序列的波動序列 即式中 為序列的時間間隔尺度 在本項研究中 取 2 即任意連續(xù)的3天之間的降水量波動情況 8 3 14 運用最小二乘法擬合出降水量時間序列P t 中連續(xù)3日的變化斜率k 即 8 3 15 計算降水量序列可能出現(xiàn)的波動值的概率式中 為對應一種降水量波動模態(tài)x發(fā)生的次數(shù) 為降水量序列可能出現(xiàn)的波動值的概率 8 3 16 將降水量波動劃分為5個等概率區(qū)間 把落在這5個區(qū)間的分別用符號表示為R r e d D 即 8 3 17 8 3 17 式中 符號R r e d D所代表的含義如圖8 3 2所示 圖8 3 2符號R r e d D的含義 按照上述思想 可把日降水量序列轉化為相應的符號序列 對于日平均氣溫序列 進行類似處理 可以得到其符號序列 把氣溫和降水數(shù)值序列轉換為符號序列過程中 時間間隔尺度參數(shù)的大小代表著時間序列的不同分辨率 對于日平均氣溫序列和日降水量序列 分別在不同的時間間隔尺度下 對所構件的字符序列中的 進行統(tǒng)計分析 顯示它們均與時間間隔尺度滿足冪律關系 這反映了氣候波動的無標度性 第三步 構建網(wǎng)絡引入一個加權網(wǎng)絡來描述降水量序列中各波動模態(tài)之間的關聯(lián)性和作用 其中網(wǎng)絡的節(jié)點就是125個3元字符串的波動模態(tài) 網(wǎng)絡的邊為前一個節(jié)點指向它的下一個節(jié)點 即一種模態(tài)向下一個模態(tài)轉換 表征了一種降雨過程向另一種降雨過程的轉變 連接兩個節(jié)點的邊的權重為它們之間多條互不相交的并聯(lián)連接通路數(shù) 例如 在所構建的降水量波動網(wǎng)絡中 其符號序列為 eRdDeRdrdeDDDreDDDrDedDdDdedrRreeRrreRedrrDdredDrDDedDereDdDeeRdeeRedrdeDdD 以3元字符串的元結構 eRd DeR drd eDD Dre DDD rDe 作為網(wǎng)絡的節(jié)點 則網(wǎng)絡節(jié)點的有向連接形式為 Rd DeR drd eDD Dre DDD rDe dDd Dde drR ree Rrr eRe drr Ddr edD rDD edD ere DdD eeR dee Red rde DdD 根據(jù)上述步驟 可構建體現(xiàn)日平均氣溫與日降水量序列各波動模態(tài)間相互作用的有向含權網(wǎng)絡圖 圖8 3 3給出了TFN和PFN網(wǎng)絡中部分節(jié)點的關聯(lián)圖像 圖8 3 3 a TFN和 b PFN網(wǎng)絡中部分節(jié)點的關聯(lián)圖像 圖8 3 3 a 刻畫了TFN網(wǎng)絡中部分節(jié)點之間的聯(lián)系 其中節(jié)點之間線連的粗細反映了節(jié)點之間關聯(lián)程度的強弱 例如 節(jié)點RRR與dRR之間的連線最粗 表示這兩種氣溫波動模態(tài)之間的關聯(lián)程度最強 圖8 3 3 b 刻畫了PFN網(wǎng)絡中部分節(jié)點之間的聯(lián)系 例如 節(jié)點DDD與RDD之間的連線最粗 表示這兩種降水波動模態(tài)之間的關聯(lián)程度最強 二 氣溫與降水波動網(wǎng)絡的統(tǒng)計特征分析1 度與度分布在構建的TFN和PFN網(wǎng)絡中 節(jié)點之間的邊是按照時間順序連接的 所以除了首尾兩個節(jié)點 其它節(jié)點的出度和入度必定是相等的 因此只研究擇節(jié)點的出度 即一種波動模式和向另一種模式間的轉換 中間沒有其它節(jié)點的中轉 所以各種波動模態(tài)之間具有短程記憶性 記憶性的強弱可以由度值的大小表示 表8 3 1和表8 3 2給出了TFN和PFN網(wǎng)絡節(jié)點的度大小的排序 結果為TFN網(wǎng)絡中的節(jié)點RRR dRR ReR 及PFN網(wǎng)絡中的節(jié)點rre rrr eee err 它們的度比較大 這說明在TFN和PFN網(wǎng)絡網(wǎng)絡中 這些節(jié)點所代表的波動模態(tài)在氣候變化中起到了重要的直接關聯(lián)作用 各種波動模態(tài)向這幾個重要模態(tài)轉換 或被這幾個重要模態(tài)轉換的頻率較高 所以 塔里木盆地的容易發(fā)生極端高溫 異常干旱的氣候事件 表8 3 1TFN網(wǎng)絡中各種節(jié)點的度的排序 表8 3 2PFN網(wǎng)絡中各節(jié)點的度的排序 對TFN和PFN網(wǎng)絡的節(jié)點度進行字頻統(tǒng)計 結果在度較大的前17個節(jié)點中 TFN中代表急劇上升的網(wǎng)絡字符R出現(xiàn)的頻率非常高 而代表急劇下降的網(wǎng)絡字符D非常缺 從這一側面可以反映出在全球變暖的大背景之下 急劇上升的氣溫波動在氣溫變換中出現(xiàn)的次數(shù)越來越多 而在PFN中 代表緩慢上升的字符r出現(xiàn)的頻率卻很高 說明塔里木河流域的降水總體上呈現(xiàn)出一個較弱的上升趨勢 圖8 3 4給出了TFN和PFN網(wǎng)絡節(jié)點的度分布及累計度分布 可看出氣溫和降水波動網(wǎng)絡中 節(jié)點的度分布整體或部分滿足冪律分布 且?guī)в兄匚舶?這是隨機連接造成的 但只要確定性占有一定的比例 所有冪律分布的隨機重尾巴就會被抑制 TFN的節(jié)點的度近似服從三段冪率分布 圖8 3 4a 1 因此TFN具有無標度特性 但其度的分布極不均勻 各氣溫波動模態(tài)間的重要度相差較大 a 1 和b 1 分別為TFN和PFN節(jié)點的度分布 a 2 和b 2 分別為TFN和PFN節(jié)點的累積度分布圖8 3 4TFN和PFN網(wǎng)絡節(jié)點的度分布及累積度分布 經(jīng)過擬合和統(tǒng)計計算 截斷點分別為60 100 第一段指數(shù) 第二段指數(shù) 第三段指數(shù) PFN的節(jié)點的度近似服從冪律分布 圖8 3 4b 1 近似呈現(xiàn)線性關系 對線性部分進行擬合可得到指數(shù) 這些結果表明 氣溫和降水波動網(wǎng)絡 即TFN和PFN具有無標度網(wǎng)絡的特性 在半對數(shù)坐標系下 TFN和PFN網(wǎng)絡近似服從衰減的指數(shù)分布 見圖8 3 4a 2 和圖8 3 4b 2 說明氣溫和降水波動模態(tài)的發(fā)生帶有一定的隨機性 進一步表明它們具有混沌特征 然而 雖然TFN和PFN網(wǎng)絡都服從衰減的指數(shù)分布 但它們的衰減速率明顯不同 TFN快 而PFN慢 這說明氣溫系統(tǒng)的漲落快 而降水系統(tǒng)的漲落慢 綜上結果 PFN兼有無標度特性和小世界效應 均既是無標度網(wǎng)絡由為小世界網(wǎng)絡 而TFN具有分層性的無標度特性和小世界效應 二者為具有無標度特性的小世界網(wǎng)絡 這些特性說明 氣候過程既具有確定性特征 又具有混沌特征 其自然變化過程既具有統(tǒng)一性有具有多樣性 2 集群系數(shù)及平均路徑長度TFN和PFN網(wǎng)絡的平均路徑長度體現(xiàn)了氣溫和降水波動模態(tài)向另一種模態(tài)轉換經(jīng)過的節(jié)點數(shù) 在以時間順序連邊的氣溫和降水波動網(wǎng)絡中 節(jié)點代表的波動模態(tài)反映了連續(xù)3天的氣溫和降水變化 若兩種波動模態(tài)之間轉換所經(jīng)過的節(jié)點數(shù)越多 則這兩種模態(tài)轉換所需要的時間也就越長 因此 網(wǎng)絡的平均路徑長度體現(xiàn)出了網(wǎng)絡中任意兩種模態(tài)之間的轉換所要經(jīng)過的平均時間 網(wǎng)絡的平均路徑長度越長 表明任意兩個模態(tài)之間的轉換 經(jīng)過中間模態(tài)的過渡越多 氣候變化過程越復雜 表8 3 3給出了TFN和PFN網(wǎng)絡的群聚系數(shù)C 平均路徑長度L及平均節(jié)點度 TFN和PFN網(wǎng)絡的節(jié)點平均度分別約為22 6124和85 616 表明它們大約分別平均與23和86個節(jié)點有相互關系 TFN和PFN的平均路徑長度分別為4 523和2 667 即TFN和PFN網(wǎng)絡中的任意1個節(jié)點 分別通過4 5和2 3節(jié)點就能影響到其它的節(jié)點 TFN和PFN均具有較高的群聚系數(shù) 較小的平均路徑長度 具有良好 小世界 典型特征 這進一步印證了上述的結論 表8 3 3TFN和PFN網(wǎng)絡的群聚系數(shù) 平均路徑長度和平均節(jié)點度 3 節(jié)點的介數(shù)TFN和PFN網(wǎng)絡中各個節(jié)點的介數(shù)排序結果 分別見表8 3 4表8 3 5 可以看到 TFN和PFN網(wǎng)絡中 各節(jié)點的介數(shù)值之間的存在一定的差異性 在TFN網(wǎng)絡中 節(jié)點RRR DDD ReR RRd DDd Ree的中介性能力均在3 以上 這6個節(jié)點對整個網(wǎng)絡的影響達到了19 71 這意味著 在TFN網(wǎng)絡中 這6個節(jié)點具有樞紐性的作用 在PFN網(wǎng)絡中 節(jié)點rre rr eee err的中介性能力均在3 以上 這4個節(jié)點對整個網(wǎng)絡的影響到了13 64 這意味著在PFN網(wǎng)絡中 這4個節(jié)點具有樞紐性的作用 另外 還發(fā)現(xiàn)在PFN網(wǎng)絡中 介數(shù)在3 以上的節(jié)點中 代表緩慢上升的字符r出現(xiàn)的次數(shù)較多 表8 3 4TFN網(wǎng)絡節(jié)點的介數(shù)排序 表8 3 5PFN網(wǎng)絡節(jié)點的介數(shù)排序 三 基本結論總結如下基本結論 1 氣溫和降水波動網(wǎng)絡 即TFN和PFN均表現(xiàn)出較高的集群性和較短的平均路徑長度 氣溫波動網(wǎng)絡 TFN 的度分布服從三段和雙段冪律分布 是具有無標度特性的小世界網(wǎng)絡 降水波動網(wǎng)絡 PFN 兼具有無標度特性和小世界效應 既是無標度網(wǎng)絡又是小世界網(wǎng)絡 2 TFN中的節(jié)點RRR dRR ReR 以及PFN中的節(jié)點rre rrr eee err 具有較高的度 說明這些節(jié)點代表的氣溫和降水波動模態(tài)發(fā)生概率較大 在TFN和PFN的重要節(jié)點中分別大都包含了R r和r e兩種符號 這說明塔里木河流域的氣溫和降水波動 主要以上升為主 3 TFN中的節(jié)點RRR DDD ReR RRd DDd Ree和PFN中的節(jié)點rre rr eee err是關鍵性的樞紐節(jié)點 分別承擔了TFN和PFN網(wǎng)絡的19 71 和13 64 的中介性功能 這些節(jié)點對理解氣溫和降水波動的內在規(guī)律有一定物理意義