網路科學中的度量分析與應用

第1章 複雜系統與複雜網路
1.1 複雜系統與複雜網路簡介
1.1.1 複雜系統
1.1.2 複雜網路
1.2 隨機圖模型
1.3 小世界網路
1.4 無標度網路
1.5 社團結構的網路
1.6 網路的網路
1.7 大數據時代的網路分析
1.8 複雜網路度量簡介
參考文獻

第2章 圖論簡介
2.1 基本概念和符號
2.2 度和距離
2.3 圖矩陣
2.4 圖的連通性
2.5 樹
2.5.1 樹的概念和基本性質
2.5.2 深度和寬度優先搜索
2.5.3 最小生成樹
2.6 獨立集與匹配
2.7 控制集
2.7.1 連通控制集
2.7.2 弱連通控制集
2.7.3 r-步控制集
參考文獻

第3章 距離相關的度量
3.1 圖的距離和與平均距離
3.2 距離計數度量
3.2.1 幾類基於距離的拓撲指數
3.2.2 幾類距離度量的一些性質
3.3 冪律隨機圖的平均距離和直徑
參考文獻

第4章 聚類和圈
4.1 聚類係數
4.2 圈係數
4.3 無標度隨機圖的聚類係數
參考文獻

第5章 度分佈及相關關係
5.1 度分佈
5.2 度相關性
5.3 度相關的度量
5.3.1 幾類度相關的度量
5.3.2 度相關度量的推廣
5.4 關於廣義Randic指標的給定度序列的極值樹
參考文獻

第6章 網路熵
6.1 網路熵簡介
6.2 基於度的熵
6.3 基於距離的熵
6.4 基於子圖結構的熵
6.5 基於特徵值的熵
6.6 加權網路的熵
6.7 隨機圖的馮·諾依曼熵
參考文獻

第7章 譜度量
7.1 網路的特徵值
7.1.1 網路的譜密度分析
7.1.2 特徵譜在網路的中心性和二分性中的應用
7.2 分子網路的能量
7.3 隨機圖的譜
參考文獻

第8章 相似性度量
8.1 相似性度量介紹
8.2 圖同構
8.3 圖相似
8.3.1 編輯距離
8.3.2 路長的差
8.3.3 子圖比對
8.4 基於拓撲指數的相似度量
8.5 鏈路預測
參考文獻

第9章 其他度量
9.1 中心度量
9.2 網路複雜性
9.3 統計度量
9.3.1 度量集中趨勢的平均指標
9.3.2 度量離散程度的指標
9.3.3 度量偏差程度的指標
9.3.4 度量兩種數值變量關係的指標
9.4 社團等同度量
9.4.1 非重疊社團度量
9.4.2 重疊社團度量
9.5 同步現象
參考文獻

第10章 複雜網路度量的相關應用
10.1 網路度量的極值問題
10.1.1 具有極值Randic指標的圖
10.1.2 關於基於度的廣義圖熵的極值
10.1.3 關於HOMO-LUMO指標圖的極值
10.2 網路度量在分子網路中的應用
10.2.1 胡克分子軌道理論
10.2.2 苯系統和亞苯基的廣義Randic指標
10.3 網路度量在社會網路中的應用
參考文獻

 

序

　　人類社會是由複雜網路交織而成的，我們生活中處處都有網路的存在，如網路、交通網路、代謝網路、社交網路、合作網路、生物網路、電力網路、智慧物聯網路、智慧製造網路等，複雜網路的研究是當今科學研究中的一個焦點，與現實中各類高複雜性系統的研究有密切關係。複雜網路的研究可以追溯到1736年的哥尼斯堡七橋問題，複雜網路研究的熱潮源於兩篇著名的文章。1998年，Nature發表了兩位年輕的物理學家D. J. Watts和S. H. Strogatz關於網路的一篇論文。一年多之後，Science發表了另外兩位年輕的物理學家A. L. Barabasi和R. Albert關於網路的另一篇論文。這兩篇論文引發了關於複雜網路的研究熱潮，這個熱潮迅速席捲全球，涉及數學、物理學、計算科學、控制科學、管理科學、社會科學、金融經濟科學等許多科學領域和通信、交通、能源、製造等工程技術領域。

　　複雜網路的表示、分析、比較和建模都十分依賴於對網路拓撲結構的屬性進行定量地刻畫，這些定量的描述和刻畫，就是所謂的複雜網路度量。基於不同的研究目的和研究需求，引入了很多的度量，Costa等於2007年年初在Advances in Physics上發表了一篇文章，全面系統地綜述了複雜網路中的各種度量。隨著學者們對網路研究的不斷深入，越來越多的度量被挖掘、定義和研究，但是目前還沒有見到有一本專門介紹複雜網路度量的專著。

　　本書共分10章，第1章介紹了網路相關的基本概念以及常見的複雜網路模型，並對複雜網路度量進行了簡要闡述。第2章叙述了進行複雜網路研究所需的圖論領域的基礎知識。第3章介紹了與距離相關的一些度量，並對特殊的距離度量：平均距離和直徑，給出了幂律隨機圖的一些經典結果。第4章提出了一些為研究網路的聚類和圈結構而建立的度量，並討論了一個無標度隨機圖的聚類係數。度分布是網路的一個重要拓撲特徵，第5章主要研究了網路的度分布及相關關係，並總結了與度相關的度量。熵在離散數學、通信科學、電腦科學、資訊理論、統計學、化學、生物學等不同領域有著重要的應用，學者們引進網路熵來衡量網路和圖的性質，第6章我們將簡要介紹網路熵的相關内容。第7章首先概述了近年來在網路特徵譜方面的進展，然後利用特徵譜來研究網路的一些特性。在機器學習和數據挖掘中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類别。相似性度量，即為綜合評定兩個事物之間相近程度的一種度量。第8章介紹一些常見的衡量網路相似性的度量。第9章進一步叙述了一些常見的複雜網路度量。第10章列舉了複雜網路度量的一些相關應用，包括網路度量的極值問題、網路度量在分子網路中的應用、網路度量在社會網路中的應用等。

　　本書在前人工作的基礎上，從圖論和數學的角度為大家呈現一個網路度量的深入描繪，全面系統地介紹複雜網路的各種度量及其性質，對於從事圖論、網路科學以及相關工程領域的研究人員和工程技術人員具有很好的參考價值。