復雜網絡分析方法.ppt

《復雜網絡分析方法.ppt》由會員分享，可在線閱讀，更多相關《復雜網絡分析方法.ppt（54頁珍藏版）》請在裝配圖網上搜索。

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