【畢業(yè)學位論文】（Word原稿）基于三種學科源流和視角的一種綜合性網絡計量和解釋框架的構建和應用

碩士研究生學位論文 題 目： 基于三種學科源流和視角的一種綜合性網絡計量和解釋框架的構建和應用 姓 名： 學 號 ： 院 系： 信息科學技術學院 專 業(yè)： 計算機 體系 結構 研究方向： 搜索引擎與網上數據挖掘 導 師： 教授 二 八 年五月 版權聲明 任何收存和保管本論文各種版本的單位和個人，未經本論文作者同意，不得將本論文轉借他人，亦不得隨意復制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權之問題，將可能承擔法律責任。 I 摘 要 近年來隨著信息技術的飛速發(fā)展和普及， 的超鏈互聯現象吸引了來自越來越多學科的學者的關注。作者發(fā)現，在這其中，除了專業(yè)的計算機網絡科學學者之外，最活躍和受人關注的學術群體來自以下三個學科流派：以物理學、生物學、統(tǒng)計力學等自然科學學者為代表的復雜網絡分析流派（ 以圖書館學、情報學等信息計量學學者為代表的諸計 量學流派（ *和以社會學、傳播學等社會科學學者為代表的社會網絡分析流派 (這些流派對網絡現象的描述和解釋上的區(qū)別，不僅體現在他們的具體研究網絡對象上，更體現在他們對具體研究內容的形式化模型 抽象網絡圖的計量模式和解釋方法上。 本文系統(tǒng)論述了以上三個學派在網絡計量和解釋上的偏好和貢獻，同時，試圖整合三種學科源流的不同研究范式和取向，建立了一個統(tǒng)一的網絡計量和解釋框架。該框架宏觀上面向網絡計量和解釋，微觀上則側重超鏈 網絡 分析（ 一主要適用領域?；趫D論中的網絡描述模型，該框架發(fā) 展出了若干基本概念和范式，如網絡研究的層次結構，計量指標的三個層級，節(jié)點的向量表達等，并將網絡計量和解釋中涉及的各種要素，主要計量指標分類選取以及解釋方案納入其中。為了進一步闡釋該統(tǒng)一框架，作者使用 了 兩個超鏈 分析 領域具體的例子，展示了該框架對已有研究的概括能力和對未來研究的啟示能力。 關鍵詞 ： 網絡計量 社會網絡分析 復雜網絡 信息計量學 超鏈網絡 a I of on eb a of of of ， of ,*. in in on on up a on is in in on of of of NA to s on 錄 第一章 引言 . 1 本文論述的對象 網絡 . 1 網絡概念的具體外延到網絡概念的抽象內涵 . 1 絡內涵的一般化表述 . 2 本文研究的緣起、視角和應用 . 3 起 . 3 角 . 4 用 . 6 本文研究承繼的科學哲學傳統(tǒng) . 6 式理論 . 6 定論和還原論 . 6 本文其余部分的結構 . 7 第二章 三種學科源 流網絡研究范式及超鏈網絡分析研究綜述 . 8 三種學科源流分別的網絡研究范式 . 8 會網絡分析源流的網絡研究范式 . 8 雜網絡分析源流的網絡研究范式 . 10 計量學源流的網絡研究范式 . 17 超鏈領域的網絡研究 . 21 第三章 統(tǒng)一網絡計量和解釋框架的構建 . 24 圖論、網絡計量框架、網絡解釋框架和網絡研究應用域的關系概述 . 24 絡研究的層次模型 . 24 絡研究層次的最內層 圖論 . 26 統(tǒng)一網絡計量框架的構建 . 28 為計量對象的圖 . 28 標體系 . 33 標 應用 . 44 統(tǒng)一網絡解釋框架的構建 . 45 第四章 統(tǒng)一網絡計量和解釋框架的應用實例 . 50 已有研究的概括實例 . 50 未來研究的啟發(fā)實例 . 52 第五 章 總結和討論 . 54 歸納和總結 . 54 不足和討論 . 55 未來研究方向 . 56 參考文獻 . 57 致 謝 . 60 V 圖目錄 圖 1- 1 抽象前的中國教育網基礎結構拓撲示意圖 2 圖 1- 2 抽象網絡的拓撲結構 2 圖 1- 3 抽象后的中國教育網基礎結構拓撲示意圖 3 圖 2- 1 復雜網絡分析的一些實例 11 圖 2- 2 一些實際網絡在三個復雜網絡分析關鍵指標上的表現 12 圖 2- 4 諸計量學之間的關系 17 圖 2- 5 網絡影響因子的計算方法 20 圖 2- 6 超鏈鏈接結構示意圖 21 圖 2- 7 蝴蝶結結構 22 圖 3- 1 網絡研究的層次模型示意圖 24 圖 3- 2 邊的層級示意圖 31 圖 3- 3 對等性示意圖 32 圖 3- 4 聚 類系數的計算示意圖 38 圖 3- 5 派系示意圖 40 圖 3- 6 41 圖 3- 7 網絡解釋框架基本模型 46 圖 3- 8 主圖特征的決定 48 圖 4- 1 實例中使用的主要計量指標 51 圖 4- 2 基于超鏈接的網絡與基于底層互聯的基礎 網絡的對比 52 表目錄 表 3- 1 圖數據抽樣方法 333 表 3- 2 個體級指標的分類 377 表 3- 3 K 叢中 K 的取值 原則 422 表 3- 4 局部級指標的分類 422 1 第一章 引言 本文論述的對象 網絡 網絡概念 的具 體外延到網絡概念的抽象內涵 網絡是一個目前出現頻度很高的詞，在普通大眾話語體系和各個學科領域中，網絡一詞在各式各樣的語境中被越來越多的人們不斷提及，反復使用，比如交通網絡，電力網絡，通訊網絡，社會 網絡，神經網絡，計算機網絡等。從本文題目中可以看出，網絡的計量和解釋是本文的論述對象。那么，本文中所指網絡的具體范疇和含義究竟是什么？這是本文必須最先回答的問題。 從外延 (看，目前在漢語語境中使用的網絡一詞 1，主要有以下范疇： 1 實體網絡：這些網絡是在空間解析幾何或者拓撲學意義上物理上存在著的實在網絡，比如通信網絡，廣播網絡，交通網絡等。 2 社會網絡：這些網絡是人們用來描述人類社會中形成的各種錯綜復雜關系的抽象網絡。比如人際網絡、組織網絡等。 3 計算機網絡：狹義的計算機網絡嚴 格上可以算作實體網絡的一種，但是由于以下兩個原因，這里單獨列出。 a）信息科技的迅速發(fā)展，計算機網絡日益普及使網絡在很多情形下已經成為和計算機有關的網絡尤其是互聯網的代指。 b) 計算機網絡本身也是一個有多重指向的廣義概念，狹義的計算機網絡僅僅是指將地理位置不同，并具有獨立功能的多個計算機系統(tǒng)通過通信設備和線路而連接起來，且以功能完善的網絡軟件實現網絡資源共享的系統(tǒng)，而很多和計算機領域有關屬于廣義計算機網絡范疇的網絡并不能算作實體網絡。 圖 1中國教育網基礎結構 2005 年的拓撲示意圖，這就是一個具體的網 絡外延（數據來源： 1在英文語境中，網絡這個詞大致對應著 詞，限于篇幅和本文討論的重點，這里不再具體討論網絡的英文外延。 2 圖 1- 1抽象前的中國教育網基礎結構拓撲示意圖 絡內涵的一般化表述 作為本文研究對象的網絡，不是上述任何網絡的具體外延中的任何一個，而是網絡概念的抽象內涵 (這個抽象內涵將具有所有網絡外延的共性，而忽略掉各個具體網絡外延的個體特征 ， 從某種角度來說實際上是一個泛網絡(概念，是鑒于網絡這個概念的外延的復雜程度，為了明確本文研究的網絡概念內涵而抽象出來的概念，它具有如下 特征： 1 能夠區(qū)分實體 2 實體之間具有關系 3 可以用圖論中的無向圖、有向圖（均可以帶權）這兩個概念作為數學表示 在圖 1示意中演示了無向圖、有向圖和一個無向加權圖的拓撲結構，關于這些圖論概念和具體形式化表述請參考 節(jié)的相關內容。因為上面的第三點特征，下文中對作為本文研究對象的網絡一詞有時也用圖來指代，不再加以區(qū)分。 34976544圖 1- 2抽象網絡的拓撲結構 3 以例子來說明， 圖 1從 圖 1抽象出來的中國教育網拓撲結構，這里它被抽象成一個無向圖 。 作為 本文研究對象的網絡，將是這種被抽象之后的網絡，而不是抽象之前的任何一個具體網絡。 圖 1- 3抽象后的中國教育網基礎結構拓撲示意圖 本文研究的緣起、視角和應用 起 本文的寫作動機大致源于以下兩個事實： 1 各種網絡的普及和網絡能量的增長 網絡一詞現在頻頻被人使用，這種現象的深層次原因是隨著工業(yè)文明和信息文明在全球范圍內的不斷拓展，人類社會中的關系數量和類型大大增加，人們日益被卷入到了各種各樣的網絡之中，網絡不僅成為人們不可缺少的溝通工具， 而且成為一些人的生存方式。加拿大學者 在上個世紀六十年代就預測這種趨勢將不斷壓迫人們的原始封閉空間，使世界最終成為一個“地球村” 1。人類日益生活在各種網絡之中使認識各種網絡的共性成為一種必要。 人類本身和其他實體以各種存在形式不斷構建和加入各種網絡，使已有網絡和新產生網絡的成員數目飛速增長，各種網絡本身的能量也隨之飛速增長 2。雖2 網絡的能量可以理解為 ”好 ”的網絡的價值和 ”壞 ”的網絡的破壞力 4 然遭受了一定的質疑和爭議，但是下面的梅特卡夫定律 (s 然是許多網絡研究者的共識：網絡的價值將與成員數量的平方成正比，而網絡的成本至多 以線性速度增長 2。網絡能量驚人的的增長速度使人類對網絡本身研究的緊迫性更加突出。 2 現有網絡認識工具間的區(qū)別和隔膜 在對網絡本身的認識中，不同領域的學者發(fā)展出了不同的概念模式和認識路徑。數學學者在網絡研究的理論探討中發(fā)展出了圖論這一科學分支，其他引人注意的研究包括物理學、生物學、統(tǒng)計力學等領域的自然科學學者近年來發(fā)展出的復雜網絡分析分支，圖書館學、情報學等信息計量學學者和社會學、傳播學等社會科學學者一直以來分別對各自領域中的引文網絡和社會網絡的研究成果等。這些研究流派都是網絡的重要認識工具，但是他們之 間也有明顯的風格上的區(qū)別。這種區(qū)別不僅體現在他們自身的研究的具體網絡對象上，更體現在他們在研究過程中進行網絡分析時的方法論偏好上。本文寫作的重要動機就是整合這些 流派 在方法論上的不同偏好，形成一個統(tǒng)一的多學科視野的綜合性網絡計量和解釋框架。 角 圖這個研究概念是一個非常大的概念，我們需要闡明一個特定的視角，才能對本文的研究內容 做出 實質性限定。我們的研究視角可以概括為： 1 框架性的計量和解釋 以何為網絡和何以為網絡 2 整合多學科偏好 3 基于網絡的靜態(tài)拓撲結構 在 我們明確了本文的 研究對象，但是并沒有說明計量和解釋框架的具體含義，這主要是因為我們對計量框架和解釋框架的界定是基于網絡研究的層次模型提出的，而這部分的論述放在了第三章。概括的說，計量框架與解釋框架試圖回答這樣一個問題：給定一個可以抽象成圖的研究對象，根據以往的研究帶來的啟示，我們可以去研究圖中的哪些定量特性（網絡計量框架），這些定量特性之間通常又是如何互相影響和決定的（網絡解釋框架）。也可以說，網絡計量框架回答的是網絡以何為網絡，網絡解釋框架回答的是網絡何以為網絡。圖論、網 5 絡計量框架、網絡解釋框架和網絡研究應用域的關系見第 三部分的示意圖，有關框架的詳細內容也參見該部分。 整合多學科偏好，就是說框架只基于網絡的抽象模型，會盡可能多容納各個學科的研究風格，忽略各個學科基于研究的具體網絡對象的不同出現的差異，重視各個學科對抽象網絡模型的理解和度量。整合必然會舍棄各個學科中的一些獨特研究方向，因此需要明確一下本文不論述或不重點論述的若干方面。 本文論述的立足點為網絡的靜態(tài)拓撲結構，所以將不論述網絡的動態(tài)特征涉及的幾個方面： 傳播機理動力學 相繼故障 搜索 同步 控制 為了強化共性，將不重點論述涉及帶權圖的幾個方面： 帶權圖的特征 基 于帶權圖的算法 為什么只研究靜態(tài)結構的原因，首先是因為動態(tài)特征的復雜性和與具體網絡的緊密相關性，在一個框架中全面覆蓋這些內容并不現實 ； 其次 是因為 在自然科學的復雜網絡分析流派中對網絡動態(tài)特征的描述已形成一個相對比較完整的體系 ； 最后在于結構本身對圖研究已經具有了超出其本身覆蓋內容的重要性，結構本身的重要性我們 可以 以鏈接分析為例闡釋如下： 1 結構構成信息 。 比如 刻畫超鏈網絡圖拓撲結構本身，就可以得到分析網頁所屬或所對應的意義實體（個人、組織、國家）之間的關系信息。 2 結構輔助人們認識信息。比如著名的 助人們認識網頁的重要程度。網絡鏈接結構還可以幫助人們根據不同的主題進行網頁分類和主題提取等。 3 結構影響節(jié)點變化和節(jié)點間流動等動態(tài)功能和特征。舉個例子，在網絡鏈接結構分析中可以根據鏈接結構 設計有效率的網頁抓取方法以及結合用戶的 6 瀏覽行為 進行 分析。 用 本文的目的在于建構一個綜合性的網絡計量和解釋框架，它的作用將體現在打破學科壁壘，建立一個統(tǒng)一的網絡分析研究范式，這個研究范式對各學科內部既有研究具有比較強的概括能力，對 未來 展開的網絡研究具有比較大的參考價值。 本文研究承繼的科學哲學傳統(tǒng) 本文研究的承繼的科學哲學傳統(tǒng)指的是從科學哲學的視角來看，本文討論的問題是基于什么樣的理論基礎，探討的是哪一范疇的問題。從網絡計量和解釋框架來看，網絡計量框架的提出基于庫恩的范式理論，網絡解釋框架的構建基礎則是對決定論和還原論的直接承繼。 式理論 范式 （ 是美國學者庫恩在進行科學史的研究時提出的一個概念，他認為科學的發(fā)展不是簡單的累積式的趨向于真理的過程，而是通過科學革命對學科研究范式的不斷轉換而推動實現的。 庫恩 說明 ： “ 按既定的用法，范式就是一種公認的模型或模式。我采用這個術語是想說明，在科學實際活動中某些被公認的范例 包括定律、理論、應用以及儀器設備統(tǒng)統(tǒng)在內的范例 為某種科學研究傳統(tǒng)的出現提供了模型。 ” 3 本文中網絡計量框架本質上是對三種學科范式的一種整合，試圖形成綜合三種學科范式的一種面向抽象網絡計量領域的綜合性范式。 定論和還原論 決定論 (一種認為自然界和人類社會普遍存在客觀規(guī)律和因果聯系的學說。決定論認為，人的一切活動，都是先前某種原因 或 幾種原因導致 7 的結果，人的行為是可以根據先前的條件、經 歷來預測的。非決定論則否認自然界和人類社會普遍存在著客觀規(guī)律和必然的因果聯系，認為事物的發(fā)展、變化是由不可預測的、事物內在的“自由意志”決定的。 還原論 （ 通常指生物學中試圖把生命運動形式歸結為物理 化學運動形式，用物理 化學規(guī)律取代生物規(guī)律的一種思潮。 18紀的還原論用力學規(guī)律取代生物學規(guī)律。 20 世紀的還原論者把生物學規(guī)律還原為分子運動規(guī)律，甚至把人類活動還原為低等動物的反應，再把這些反應還原為物理 化學過程。當代分子生物學的成就支持還原論，不僅遺傳過程已還原為化學的相互作用，而且其他生物現象也將還原為化學過程。 在本文論述的網絡解釋框架中，筆者將用向量表示的意義實體作為一個封閉系統(tǒng)，向量的結構和具有的性質完全由其分量決定，這是決定論和還原論觀點的體現。 本文其余部分的結構 在本文的第二部分將系統(tǒng) 分析 以下三個學派在網絡計量和解釋上的偏好和貢獻：以物理學、生物學、統(tǒng)計力學等自然科學學者為代表的復雜網絡分析流派（ 以圖書館學、情報學等信息計量學學者為代表的諸計量學流派（ *,和以社會學、傳播學等社會科學學者為代表的社會網絡分析流派( 分析 重點在于他們對具體研究內容的數學形式化模型 網絡圖的計量模式和解釋方法上。同時，作者對超鏈網絡研究領域也會做一大體回顧。 在本文的第三部分將提出圖論、網絡計量框架、網絡解釋解釋框架和網絡研究應用域的關系理論，試圖整合三種學科源流的不同研究范式和取向，建立一個統(tǒng)一的網絡計量和解釋框架。該框架宏觀上面向網絡計量和解釋，將網絡計量和解釋中涉及的各種要素，主要計量指標分類選取以及解釋路徑納入其中。 在本文的第四部分為了進一步闡釋該統(tǒng)一框架，作者將使用兩個例子，解釋框架在超鏈鏈接分析領域的具體適用性和應用方法及 前景。 本文的第五部分是一個簡短的總結，說明了本文的貢獻和不足之處。 8 第二章 三種學科源流網絡研究范式及超鏈網絡分析研究綜述 三種學科源流分別的網絡研究范式 會網絡分析源流的網絡研究范式 首先介紹一下社會網絡分析的相關定義和理論，社會科學對網絡計量和解釋的研究是基于社會科學對網絡的帶有學科特色的界定基礎上的。社會科學領域研究的網絡被稱為社會網絡，它的定義如下： 社會網絡是一種由節(jié)點組成的社會結構，這些節(jié)點通常意義上來講是個人或者組織，而連接這些節(jié)點的則是各種類型的互相依賴關系或者 互動。比如，互相認識，朋友，親戚，喜歡，討厭，沖突，疾病傳播。 社會科學中的很多學科都涉及到了網絡計量和解釋這一研究內容，主要涉及到的學科有以下幾個學科：社會學，人類學，社會語言學，傳播學，社會心理學以及經濟學，其中由于學科研究對象的側重不同，社會學和傳播學對于社會網絡的分析比較多。 社會網絡分析的視角在社會學中很早就被使用，但是社會網絡作為一個正式的定義是由 J. A. 4在 1954 年引入的， 于英國的結構功能學派，他在分析社會結構和文化體系如何決定人類行為的過程中，用網絡這個 詞代指社會群體之間、社會成員之間，社會群體與其成員之間復雜的網狀聯系。社會網絡理論以網絡中間的個人及其關系為分析基礎，強調個人的能動性，但另一方面又注意到社會網絡所形成的社會結構以及社會制度對個人的制約。 在社會網絡分析理論發(fā)展過程中，影響非常大的一個研究是 5，在以前的社會學研究中，長期存在著微觀設社會學和宏觀社會學兩種主要流派，過去的社會學分析 中 ，微觀分析比如形象互動理論，團體動力學都是研究個體行為，很少研究社會的宏觀現象，而宏觀的分析 則視社會結構為社會群體的集合，社會群體以階級、地位、種族、年 9 齡、性別、地域和宗教加以區(qū)分。社會網絡分析的意義正如 出的那樣，是要為微觀行為與宏觀行為之間建立一座橋。 社會網絡分析在其發(fā)展過程中形成了若干計量范式，這些范式以特 定 的指標和概念存在，反映了社會網絡分析的研究方向和偏好，這里總結一下這些指標和概念，由于其中很多概念在下文框架部分還要提及，因此，具體數學表達式參見第三部分，這里只給出一些簡單介紹： 中介 中介 （ 衡量的是一個個體在網絡中對其他個體的連接程度。 網絡中很多節(jié)點沒有直接相連的邊，需要其他一些節(jié)點的中介實現連通。作為中介的節(jié)點可以使用 個指標來衡量他們對其他節(jié)點的連通帶來的貢獻程度。 接近 接近 （ 衡量的是一個個體在網絡中接近所有其他個體的程度（間接或者直接）。它反映了個體通過所在網絡獲取信息的能力。一個合理的度量手段是計算該節(jié)點到其他所有節(jié)點的最短距離的倒數。 度中心度 度中心度 （ 指的是一個節(jié)點與網絡中其他的節(jié)點存在的直接連接的個數。 流中介中心度 流中介中心度 （ 衡量的是一個節(jié)點對其他節(jié)點間連通性的貢獻。 特征向量中心度 特征向量中心度 （ 在衡量網絡中一個節(jié)點的重要性時，給每個節(jié)點賦予一個相對分數，迭代進行計算， 迭代過程遵循這樣的原則：連接到高分數 節(jié)點的節(jié)點也會因此得分較高。 中心勢 中心勢 （ 是一個衡量網絡中邊的分布狀況（集中還是分散）的一個指標。一個中心勢比較強的網絡通常被稱為中心化（ 絡，中心化網絡有 較多 的邊分布在一個或一 些節(jié)點周圍。而一個去中心化的網絡則每個 10 節(jié)點的擁有的邊的情況差不多。 聚類系數 聚類系數 （ 衡量的是與一個節(jié)點有邊相連的兩個節(jié)點之間有邊相連的可能性。較高的聚類系數說明了“物以類聚”的特性。 凝聚 凝聚 （ 在社會網絡分析中是一個沒有精確界定的概念。大體上用來描述一個呈現如下特征的子圖：在子圖內部，節(jié)點對間的連接比子圖與子圖外部節(jié)點對間連接更為緊密。 路徑長度 路徑長度（ 指的是兩個節(jié)點間的距離 3。平均路徑長度（ 所有節(jié)點對之間距離的一個平均值。 結構對等性 結構對等性（ 用來 刻畫 在網絡中兩個節(jié)點間具有相同位置 的特征 。所謂具有相同的位置，就是和圖的其他部分有相同的鏈接關系。有關對等性的詳細介紹，可以參考第三部分中邊的衍生部分的相關論述。 雜網絡分析源流的網絡研究范式 在自然科學很多子學科內部，存在著諸如通信網絡，電力網絡，生物網絡等許多復雜的網絡結構，復雜網絡分析 (下簡稱 統(tǒng) 計力學，神經生物學等 學科的學者們 探索 和處理各種看上去互不相同的復雜網絡之間的共性的 一種普適工具。由于發(fā)展和使用這一普適工具的學者主要來自數理學科、生命學科和工程學科，所以盡管這一工具本身也試圖容納社會網絡在研究范圍其中之內，復雜網絡分析還是有著很鮮明的自然科學特點 無論是從研究對象還是從研究范式上來看。 研究對象： 從復雜網絡分析的研究對象來看，分布在數理、生命、工程等各個學科，大3 這里實際上和圖論中的表達有矛盾，按照圖論通用術語，路徑（ 際上并沒有短程線（ 意味。而距離（ 的是短程線的長度。所以，這里的路徑長度實際上指的是最短路徑長度（ 均路徑長度 也指的是 ( 11 多具有如下三個特點： 6 1 結構復雜性 首先復雜網絡分析關注到如下的 網絡 結構復雜特點：節(jié)點之間的連接關系是混亂復雜無序的； 節(jié)點之間的形成的邊可能具有不同的權重和方向；網絡整體結構可能是隨時變化的。下圖是一些復雜網絡的網絡拓撲結構 7： 圖 2- 1復雜網絡分析的一些實例 2 節(jié)點復雜性 復雜網絡分析中的 網絡節(jié)點很多是具有分叉和混沌等復雜非線性行為的動力系統(tǒng)。例如，基因網絡和 陣列中每個節(jié)點都具有復雜的時間演化行為。而且，一個網絡中可能存在多個不同類型的節(jié)點。例如，控制哺乳動物中細胞分裂的生化網絡就包含各種各樣的基質和酶。 3 各種復雜性因素的相互影響 實際的復雜 網絡會受到各種各樣因素的影響和作用。例如，耦合神經元重復地被同時激活，則它們之間的連接就會加強，這被認為是記憶和學習的基礎。此外，各種網絡之間也存在密切的聯系，這使得對復雜網絡的分析變得更為困難。例如，電力網絡的故障可能會導致 量變慢、金融交易網絡故障、交通運輸網絡失去控制等一系列不同網絡之間的連鎖反應。 目前復雜網絡分析的前沿問題主要存在于： 1 網絡拓撲模型的建模 、相關性質的討論和與現實世界中相關網絡的應用擬合 。這些網絡拓撲模型主要包括：規(guī)則網絡、隨機圖、小世界網絡。 2 網絡上病毒和信 息的傳播動力學（ 12 3 網絡相繼故障（ 析。 4 復雜網絡中的搜索（ 題。 5 復雜網絡中的子結構和相關算法。 6 復雜動態(tài)網絡中的同步（ 7 復雜動態(tài)網絡中的控制（ 復雜網絡分析的 研究范式：前文已經提到，我們 會 舍棄復雜網絡中的靜態(tài)拓撲結構，而不考慮動力學問題，所以這里只對涉及到的靜態(tài)拓撲結構的網絡建模及擬合應用加以討論。 在復雜網絡分析中的網絡模型構建中，有 三個關鍵的指標：圖聚類系數，平均路徑長度和度分布。 為避免重復描述， 這三個指標的具體計量方法，在后面的框架部分加以陳述。 之所以說 這三個指標是關鍵的，是因為網絡的這三個指標決定了很多其他 復雜 網絡 分析學派關注 的重要性質。正因如此，復雜網絡分析領域里的很多研究都測量了這三個指標，下圖就是一些復雜網絡分析學者分析過的網絡在這三個基本指標上的表現 8： 圖 2- 2 一些實際網絡在三個復雜網絡分析關鍵指標上的表現 13 根據具體網絡在這三個指標上的不同表現，形成 了 若干基本 的網絡模型，這些模型是從 隨機網絡向 規(guī)則網絡的折衷： 機圖 W 小世界模型 標度網絡 1 機圖 隨機圖理論源自二十世紀六十年代，兩位匈牙利數學家 研究了隨機生成邊的概率對圖的性質的影響。假設規(guī)定網絡中 任意兩點間有一條邊的概率為固定的 p，他們系統(tǒng)探討了這樣生成的圖的性質。他們發(fā)現 p 比圖的節(jié)點總數 N 對圖的性質的影響 更 大，通過令 N ，然后變動 p 來觀察圖的其他度量指標的變化情況， 可以 發(fā)現， 機圖的許多重要的性質都是突然 涌現的，也就是說，對于任一給定的概率 p，要么幾乎每一個圖都具有某個性質，要么幾乎每個圖都不具有該性質。 機圖的關鍵指標值： 平均度 =p( 均路徑長度 L 機圖的度分布遵循泊松分布。 2 W 小世界模型 小世界（ 一個非常有名的說法，很多學術文章或非學術文章都有所提及，這里我們試圖探討它的確切含義。小世 界現象反映了網絡中平均路徑長度增加與網絡規(guī)模增長的特定關系。直覺上來講，小世界意味著隨著整個網絡規(guī)模的擴大，網絡中兩點距離的增加并不明顯，嚴格的說，小世界概念要求在網絡節(jié)點的平均度 不變的情況下，網絡中平均路徑長度 L 的增加速度至多與網絡規(guī)模 N 的對數成正比。 從關鍵指標的限定來看，小世界模型是具有小的平均路徑長度和大的圖聚類系數特性的一類網絡，有代表性的兩個小世界模型是 世界模型和 14 世界模型。 世界模型由 1998 年引入 10，其構造過程如下： a) 從規(guī)則圖開始 ：考慮一個含有 N 個點的最近鄰耦合網絡 4，它們圍成一個環(huán)。其中每個節(jié)點又都與它左右相鄰的各 K/2 節(jié)點相連， K 是偶數。 b) 隨機化重連：以概率 p 隨機地重新連接網絡中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網絡中隨機選擇的一個節(jié)點。在隨機化重連的過程中為保持簡單圖 5的性質，規(guī)定任意兩個不同的節(jié)點之間至多只能由一條邊，并且每一個節(jié)點都不能有邊與自身相連。 世界模型由 1999 年提出 11，其構造過程如下： a) 從規(guī)則圖開始：考慮一個含有 N 個點最近鄰耦合網絡，它們圍成一 個環(huán)，其中每個節(jié)點都與它左右相鄰的各 K/2 個節(jié)點相連， K 是偶數。 b) 隨機化加邊：以概率 p 在隨機選取的一對節(jié)點之間加上一條邊。同樣，為了保持簡單圖的性質，其中任意兩個不同的節(jié)點之間最多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。 W 小世界模型的關鍵指標值如下 (這里都沒有給出具體推導，請參見各參考文獻 ) ： 世界圖聚類系數：3)1()1(4 )2(3)( 12 世界圖聚類系數：)2(4)1(4 )2(3)( 世界平均路徑長度： )2/(2)( N K 11 其中 1u u /ln 當）（常數當 世界度分布： 2/ 時： 2/2/2/