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